First Draft, 13 July 1999.
Linking XML documents has been complicated by an apparent mismatch between several categories of information that are involved in creating links. Stepping back from the particulars of linking and exploring the abstract structures involved may help resolve the outlines of a practical set of solutions and provide a cleaner vocabulary for discussing intersections between different aspects of linking. Please send comments to Simon St.Laurent.
Extensible Markup Language (XML) provides a syntax oriented toward hierarchically-organized material. Its hierarchical structures can be used to represent a wide variety of other data structures, including lists, tables, sets, and graphs, as well as semi-structured information like traditional documents. XML is extraordinarily flexible, readily transformed, and (mostly) easily processed. The need for links among documents has raised some key issues regarding XML document structures, their content, and the way that they represent it. Rather than addressing the problems of XLink directly, this document takes a more abstract look at the three types of structures XLink is trying to reconcile: trees, graphs, and sets.
Tree structures are largely defined by containment relationships. Parent structures contain child structures directly and child structures are directly contained by parent structures. Ancestor structures contain descendant structures and descendant structures are contained by ancestor structures. Siblings are structures that share a container but don't contain each other.
XML's hierarchical structures form trees and are often described using metaphors based on that similarity, like root and leaf elements of documents. Pretty much every structure in XML is a container for other structures, contained by structures, or both. (The document boundaries themselves are the ultimate container, even more fundamental than the root element.) Every character in an XML document is either part of a container (at least a potential container) or contained itself by another structure. (The prolog and whitespace after the root element are contained by the document boundaries.)
Graphs can achieve many levels of sophistication, but the basic graph described here is fairly simple, connecting an origin to a target with a label describing the nature of the connection. Any relationship that can be described as Resource X has Relation Y to Resource Z can be described with directed labeled graphs. All of the containment relationships described above can be described as graphs, for example, as can HTML links, and an enormous number of other programming structures.
The W3C's Resource Description Framework (RDF) and Gabe Beged-Dov's XArc focus on representing graph structures. Some of the W3C's XLink working draft also provides tools for creating simple links, essentially labelled graphs.
Sets are groups of resources that share a common property. That property may be a container, a name, a value - any common property. Sets may be ordered (in which case they are also lists) or structured (in which case they may form a tree or other structure.)
The W3C's XLink working draft provides tools for describing links (specifically extended links) as sets of resources.
Trees can be described as a connected set of graphs, while graphs can be represented in a wide variety of ways within a tree structure. Containment relationships can be used to express connections, naming conventions can establish connections, and built-in XML features like ID and IDREF can also also be used.
Sets can be expressed within tree structures in a number of ways. As with graphs, naming conventions and XML features like IDREF can be used to group information inside of an XML document into sets. The containment relationships that are fundamental to XML structures, however, provide a much easier set of tools for establishing sets. This may require identifying which containers hold sets that are relevant to a particular kind of processing (XLink, for instance) and establishing rules for which of the contents of that container are members of the set. (Labelling using naming conventions is one possibility, while simple rules like 'all children' or 'all descendants' is another. Combinations, limiting the set to descendants with a particular attribute name-value pair, are another option.)
Moving from sets to graphs and vice-versa is a much more complicated task, and the one that seems to have caused the most argument in public discussions of XLink. Simple links use naming conventions to establish unidirectional links, basically directed graphs with labeling information, while extended links use containment and naming conventions to establish sets of resources, leaving it up to the application (in the 3/3/98 draft) to figure out what connections (graphs), if any, may exist between the members of the set. No set of rules is provided for converting the more abstract extended links into the well-understood and commonly implemented simple links. Similarly, creating sets (extended links) from groups of graphs (simple links) can be a complex process requiring considerable human intervention.
This doesn't have to mean that graphs and sets are irreconcilable. It does suggest, however, that a well-understood mechanism for converting sets to graphs (the easier problem, and likely to be more common in the XLink context) could be a very useful tool, cleaning up the apparent disjunction between the two sorts of links and providing developers a framework on which to base their assumptions about application design.
XLink provides a set of tools for connecting information stored primarily in tree structures. In doing so, it makes use of both sets and graphs, represented by particular configurations of tree structures. While the description of how to create sets and graphs from within a tree structure is a very useful beginning, some reconciliation between those two possible end products is needed to increase XLink's coherence and simplify the task of integrating XLink with other layers in XML application design.
Copyright 1999 by Simon St.Laurent.