Towards a repair for our override problems

Henry S. Thompson
10 Mar 2011

1. Managing circularity: a graph-based sketch of an approach

Our goal is to construct a tree of include and overide connections with no duplicate leaves. However we will speak as if we're dealing with a graph, because the fact that we're building a tree is something that eventually will need to be proved, not just assumed/asserted. The nodes of the graph (which we'll call G) are schema documents, identified by their base URIs, which we take to be the URIs of the schema documents as retrieved after all redirection has occurred.

Notation:

1.1. Algorithm I: include only

This algorithm reconstructs XSV's handling of re-entrant and circular includes.

Without loss of generality, assume we start with a single 'root' schema document whose URI as retrieved is root
  1. Add r = Node(root) to G
  2. Initialise a set of nodes to be processed Q = {r} and a set of nodes already processed P = {}
  3. If Q is empty, we're done
  4. Otherwise let n be a node removed from Q
  5. If there exists m in P such that m.uri = n.uri and m.markers = n.markers, then
    1. Remove n from G
    2. For all edges e such that e.to = n, remove e from G
  6. Otherwise
    1. Add n to P
    2. For each include EII or import EII with a schemaLocation attribute (call that EII i) in n.sd.[children]
      1. Add m = Node(i/@schemaLocation) to G
      2. If i is an include, add all the members of n.markers to m.markers
      3. If i is an include and its inclusion of m.sd is a chameleon inclusion, then add tns(n.sd) to m.markers
      4. Add m to Q
      5. Add Edge(n,m,"include" or "import" as appropriate) to G
  7. Go to step 3

There is slightly more mechanism here than is needed (edge labels are not used, 6.b.ii and 6.b.iii are mutually exclusive and the marker set of a node is always either empty or consists of a single URI). This is to prepare the way for handling override as well.

On the other hand, the treatment of import is oversimplified, and redefine is not mentioned at all.

I think it's reasonably obvious that the result of the above is a tree rooted at r and that the leaves are unique. Representation checking and schema construction can then proceed bottom-up with respect to that tree. That doesn't mean that a given schema document will only be processed once: if is chameleon-included with multiple including namespaces, or is both chameleon and non-chameleon included, it will occur at multiple leaves (with different values for its markers) and be processed multiple times, but necessarily so, and with different results in each case.

(In XSV (vintage Schema 1.0), the actual algorithm dispenses with Q, and simply recurses at 6.b.iv. This means that once it gets to the end of the include [children] in step 6, it can check and process the rest of the [children] and add the corresponding components to the schema component for the appropriate namespace, and no spurious duplicates will ever by encountered.)