[Bug 4639] Allow cycle checking on element graphs as well as document graphs

http://www.w3.org/Bugs/Public/show_bug.cgi?id=4639





------- Comment #2 from james.lynn@hp.com  2007-10-03 21:26 -------
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.

Received on Wednesday, 3 October 2007 21:26:31 UTC