[w3c sml][Action 21] Make a proposal for the definition of an element based cycle.

This is a proposed definition of cycles in an SML Model where elements are the domain. This is related to SML Bugzilla bug 4639.

The proposed definition is quite brief and is marked as Normative below. I felt this also warranted some explanation of my thinking and is marked as Non-normative. I believe that some of the non-normative text, or something like it, should also be included in the spec, just enough to make the intent clear.

Normative:
A path is defined as a set of elements connected by SML References of the same type.
An element which has a path back to itself is a cycle.


Non-normative: Since the sole purpose of SML is to represent a model, I think it helps to be clear on what scenario we are trying to describe in the model. In simple graph terminology, a path is a set of nodes connected by an edge, or arc. A cycle can be defined as a path from a node back to itself. For the purposes of this proposal, the distinction between undirected graphs and directed graphs is ignored.

Start with the simplest and easy to understand Use Case. This makes counterexamples, etc., easier:
Model Domain: Genealogy
Our nodes are people, our edges or arcs are the relationship "isParentOf". We want to ensure that our model does not allow a scenario where John isParentof Sue, Sue isParentof Sam, and Sam isParentof John.
            Note that this does not preclude the same scenario but where in the last clause we have Sam isFriendof John. This is because the relationship(i.e., the edge or arc) is different. So the key in detecting cycles is that the path must be made up of edges of the same type to be a cycle.
            It is sometimes desirable to have type constraints on the nodes themselves, for example in the relationship isMotherof, the first node must be of type female but the second node may be either male or female. This can be accomplished in general by SML type constraints, including SML reference targetType, but is not considered as a criterion for cycle checking.


James Lynn
HP Software
610 277 1896