XML Linking Technologies

October 4, 2000

Eric van der Vlist

Defining relationships between nodes of a tree is always an involved topic. During the 1990s we saw the success of relational databases, tabular data being an extreme solution to defining these relationships. In bringing hierarchical structures back to center stage, XML has revived the linking problem and presents multiple ways to solve it.

In this article, we explore some of the ways to express links. We'll focus on linking nodes in a single document. Using the example of book cataloging, for each technology we will show how the example can be represented, explain how this representation can be expanded using XSLT into the most simple model, see how the document could be validated using XML Schemas, and weigh the benefits of each approach against its complexity.

We take XSLT transformation as the typical XML processing scenario, using it to gauge the complexity of each linking scenario. Please note that the XML Schemas and XPointer technologies used below are still works in progress and lack production-quality implementations.

Containment

The first and most natural way to express a relationship between nodes is to use the containment of XML tree nodes and to model the structure of the XML document after the structure you wish to represent.

For example, to describe my library, I can define a containment-based structure.

<library>

    <book>

        <isbn>0836217462</isbn>

        <title>Being a Dog Is a Full-Time Job</title>

        <author>

            <name>Charles M. Schulz</name>

            <nickName>SPARKY</nickName>

            <born>November 26, 1922</born>

            <dead>February 12, 2000</dead>

        </author>

        <character>

            <name>Peppermint Patty</name>

            <since>Aug. 22, 1966</since>

            <qualification>bold, brash and tomboyish</qualification>

        </character>

        <character>

            <name>Snoopy</name>

            <since>October 4, 1950</since>

            <qualification>extroverted beagle</qualification>

        </character>

.../...

    </book>

</library>

(library1.xml)

This structure is easy to query if you want to retrieve all the information related to a book, since you'll find it in the child nodes of the book node.

Unfortunately, it isn't scalable and becomes messily redundant as soon as we add a second book into our library.

<library>

    <book>

        <isbn>0836217462</isbn>

        <title>Being a Dog Is a Full-Time Job</title>

        <author>

            <name>Charles M. Schulz</name>

            <nickName>SPARKY</nickName>

            <born>November 26, 1922</born>

            <dead>February 12, 2000</dead>

        </author>

        <character>

            <name>Peppermint Patty</name>

            <since>Aug. 22, 1966</since>

            <qualification>bold, brash and tomboyish</qualification>

        </character>

        <character>

            <name>Snoopy</name>

            <since>October 4, 1950</since>

            <qualification>extroverted beagle</qualification>

        </character>

.../...

    </book>

    <book>

        <isbn>0805033106</isbn>

        <title>Peanuts Every Sunday </title>

        <author>

            <name>Charles M. Schulz</name>

            <nickName>SPARKY</nickName>

            <born>November 26, 1922</born>

            <dead>February 12, 2000</dead>

        </author>

        <character>

            <name>Sally Brown</name>

            <since>Aug, 22, 1960</since>

            <qualification>always looks for the easy way out</qualification>

        </character>

        <character>

            <name>Snoopy</name>

            <since>October 4, 1950</since>

            <qualification>extroverted beagle</qualification>

        </character>

.../...

    </book>

</library>

(library2.xml)

The information about the author and some of the characters needs to be duplicated to fit this simple model, which would thus rapidly grow into an unwieldy unmaintainable document. Also, it complicates some queries, like locating the books written by a particular author or the books in which a particular character appears.

Handling Links in Applications

What we've seen is that characters and authors need to be separate objects, stored under different nodes trees, and linked to and from the book. XML is flexible enough that we don't need any external standard to define these links, we can just flatten our structure.

<library>

    <book>

        <isbn>0836217462</isbn>

        <title>Being a Dog Is a Full-Time Job</title>

        <author>Charles M. Schulz</author>

        <character>Peppermint Patty</character>

        <character>Snoopy</character>

        <character>Schroeder</character>

        <character>Lucy</character>

    </book>

    <book>

        <isbn>0805033106</isbn>

        <title>Peanuts Every Sunday </title>

        <author>Charles M. Schulz</author>

        <character>Sally Brown</character>

        <character>Snoopy</character>

        <character>Linus</character>

        <character>Lucy</character>

    </book>   

    <author>

        <name>Charles M. Schulz</name>

        <nickName>SPARKY</nickName>

        <born>November 26, 1922</born>

        <dead>February 12, 2000</dead>

    </author>



    <character>

        <name>Snoopy</name>

        <since>October 4, 1950</since>

        <qualification>extroverted beagle</qualification>

    </character>

    <character>

        <name>Sally Brown</name>

        <since>Aug, 22, 1960</since>

        <qualification>always looks for the easy way out</qualification>

    </character>

    <character>

        <name>Linus</name>

        <since>Sept. 19, 1952</since>

        <qualification>the intellectual of the gang</qualification>

    </character>

.../...

</library>

(library3.xml).

We have replaced the author and character elements in the book element by a reference to the author and character elements using application-specific identifiers (in this case, the contents of the name elements). While we gain scalability, the downside of this approach is that the applications processing this format need to know how to handle these links.

The most common way to implement this kind of structure is to embed the knowledge of the new XML layout within the application design. We can also try to avoid hard-coding the link processing into an application, either by transforming a document before handing it to the application or by providing providing hints sufficient to manage the links.

We can help our applications by transforming the new format to the original, expanded one. The XSLT template that replaces a reference to an author or a character by its full node structure takes exactly two instructions:

<xsl:template match="author">

    <xsl:variable name="name" select="normalize-space()"/>

    <xsl:copy-of select="/library/author[normalize-space(name)=$name]"/>

</xsl:template>

(expand3.xsl)

XSLT can be used to present the application with a logical structure based on containment, while the actual serialized structure of the source document may be different.

XML Schemas

We can also try providing the application with enough information about the data structure for it to be able to handle it by itself. XML Schemas look like the perfect way of doing by using the key and keyref instructions.

   <xsd:key name="authorKey">

        <xsd:selector xpath="author"/>

        <xsd:field xpath="name"/>

    </xsd:key>

    <xsd:keyref refer="authorKey" name="book2author">

        <xsd:selector xpath="book/author"/>

        <xsd:field xpath="."/>

    </xsd:keyref>

(library3.xsd)

Done within the definition of the library element, these declarations define that the author's name is a key (unique identifier), and that this key is referenced in a book's author element.

At the time of writing, the W3C online validator is the only tool I have found which accepts this XML Schema. Not all is lost, though, as the primary benefit of taking the pain to write a schema should be that you can now validate the document.

That said, the more ambitious goal of XML Schemas is to provide a means for defining the structure, content and semantics of XML documents. I wouldn't be surprised to see more projects and products producing all kind of interesting things using XML Schemas -- things like classes, bindings, transformations, or RDBMS mappings.

We can anticipate, then, that Schema-aware tools will be able to supply applications with the necessary information to facilitate the processing of such links.

ID and IDREF

In the third revision of our book catalog document, we used natural identifiers (the name of the author or characters), and the matching is done at an application level by comparing the values.

XML provides another way to identify nodes in a document through the ID and IDREF datatypes implemented in DTDs (also implemented by XML Schemas). Using these identifiers introduces constraints, though -- the values need to be carried by attributes, they must be valid XML tokens, and they must be declared in the DTD.

<!DOCTYPE library [

<!ATTLIST author id ID #IMPLIED>

<!ATTLIST book id ID #IMPLIED>

<!ATTLIST character id ID #IMPLIED>

]>

(library4.xml)

The identifiers need to be XML tokens and so cannot begin with a numeric character. Furthermore, they are global to a document and must identify a node independently of its context. To avoid conflicts between identifiers used for different elements, we can prefix the identifier with the name of the element which is identified.

   <book id="book_0836217462">

.../...

    <author id="author_Charles-M.-Schulz">

.../...

    <character id="character_Snoopy">

(library4.xml)

The references to these elements can be done with attributes.

   <book id="book_0805033106">

        <isbn>0805033106</isbn>

        <title>Peanuts Every Sunday </title>

        <author href="author_Charles-M.-Schulz"/>

        <character href="character_Sally-Brown"/>

        <character href="character_Snoopy"/>

        <character href="character_Linus"/>

        <character href="character_Lucy"/>

    </book>

(library4.xml)

The transformation needed to expand such references is still more simple than the previous example, and it can be generalized under the assumption that we want to expand all the elements having an href attribute.

<xsl:template match="*[@href]">

    <xsl:copy-of select="id(@href)"/>

</xsl:template>

(expand4.xsl)

This scheme reflects the SGML legacy of XML, and this is the only case in the possible implementations discussed in this article where the complete document validation -- including the check of the uniqueness of the identifiers and the validity of the references -- could be done using a DTD.

This is possible in a similar fashion within a XML Schema, where the declaration can be written as

  <xsd:attribute name="id" type="xsd:ID"/>

(library4.xsd)

   <xsd:attribute name="href" type="xsd:IDREF"/>

(library4.xsd)

Logical or Physical Links?

The difference between these first two linking schemes is that in the first case we defined links which were implemented logically, that is, comparing the values of abstract properties (the name of an author or a character, the ISBN of a book); while in the second case, we use identifiers that are located in our documents.

We will encounter this distinction repeatedly on our tour across linking technologies. The distinction between a physical link pointing to a node location and a logical link relying on the matching of values or combination of values is fundamental.

RDF

Let's see how simple an RDF variant of our book catalog document can be. First we have to replace the root element by the mandatory rdf:RDF root element and then define a namespace for our vocabulary.

<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"

    xmlns="http://my.library/rdf/syntax#">

(library5.rdf)

Next we use an rdf:about attribute to identify the element we are describing, using URIs as unique identifiers.

   <book rdf:about="http://my.library/book/0836217462">

   <character rdf:about="http://my.library/character/Snoopy">

(library5.rdf)

The third and final step is to use rdf:resource to identify the elements to which we want to link.

   <book rdf:about="http://my.library/book/0836217462">

        <isbn>0836217462</isbn>

        <title>Being a Dog Is a Full-Time Job</title>

        <author rdf:resource="http://my.library/author/Charles-M.-Schulz"/>

        <character rdf:resource="http://my.library/character/Peppermint-Patty"/>

        <character rdf:resource="http://my.library/character/Charlie-Brown"/>

        <character rdf:resource="http://my.library/character/Snoopy"/>

        <character rdf:resource="http://my.library/character/Schroeder"/>

        <character rdf:resource="http://my.library/character/Lucy"/>

    </book>

(library5.rdf)

That's all that's required to convert to a minimal but conforming RDF document with a syntax that is similar to the original.

We have added a second level of abstraction on top of our document, but we can still use it as an ordinary XML document. It can still be expanded using two instructions in an XSLT template.

<xsl:template match="lib:author">

    <xsl:variable name="resource" select="@rdf:resource"/>

    <xsl:copy-of select="/rdf:RDF/lib:author[@rdf:about=$resource]"/>

</xsl:template>

(expand5.xsl)

And you can still define a XML Schema on top of it.

The schema, which we have split into two files (library5-rdf.xsd for the rdf namespace and library5.xsd for our vocabulary), can still contain the key and keyref constraints.

   <xsd:key name="characterKey">

        <xsd:selector xpath="character"/>

        <xsd:field xpath="@rdf:about"/>

    </xsd:key>



    <xsd:keyref refer="characterKey" name="book2character">

        <xsd:selector xpath="book/character"/>

        <xsd:field xpath="@rdf:resource"/>

    </xsd:keyref>

(library5-rdf.xsd)

While we still have an ordinary and (relatively) simple XML file, which works with our preferred XML tools, we have also evolved this document into the basis of a semantic layer. Since this document is now a valid RDF document, it can be read by RDF tools, which will see it as a set of predicates (called triples) that can be inserted into databases and be used for logical programming applications.

The triples, which can be visualized using the W3C online service, are basic assertions that look like

triple('http://my.library/rdf/syntax#character',

       'http://my.library/book/0836217462',

       'http://my.library/character/Schroeder').

(lib5-triples.html)

This triple indicates that the book http://my.library/book/0836217462 is linked to http://my.library/character/Schroeder through a relation of type http://my.library/rdf/syntax#character.

In addition to the availability of the links, all the information in the document is available as triples for RDF applications.

triple('http://my.library/rdf/syntax#qualification',

'http://my.library/character/Lucy',

'bossy, crabby and selfish').

(lib5-triples.html)

One should note that the two layers (XML and RDF) are not equivalent. RDF is an abstract layer on top of XML. It doesn't care about the syntax that has been used to describe the triples, nor does it care that these triples can't be serialized back in the same XML format (since the structure of the input document has been lost).

Building RDF on top of XML results in the same loss of low-level detail as in building XML on top of raw text (which I have described in "Processing Inclusions with XSLT"). It could be interesting to define an RDF representation of an XML document (i.e., preserving its exact structure), just as XML representations of text documents can be defined. This is also one of the reasons why, though most existing RDF tools can read RDF documents to extract and work on triples, they do not provide a programmatic way to write triples back as RDF.

RDF Tradeoffs

The tradeoffs between added complexity (which can be minimal, as we've seen) and the potential applications (available or in development) makes using RDF to define the links between elements in our applications an interesting option.

One of the criticisms of RDF is that it's a disruptive technology: in order to be RDF compliant, we had to change the root element of our application. If we'd wanted to carry more information, such as the order of the links between a book and the characters, we would have included them in RDF sequences, which would've further modified its structure. Although this disruption can be acceptable when defining a new vocabulary, it may be a limitation when using or extending existing standards.

Simple XLinks

In contrast to the changes required to document structure for RDF, the latest XLink CR has chosen to locate most of the linking information in attributes. These attributes, placed in a separate namespace, are usable with minimal impact as an addition to XML vocabularies.

However, XLink is still a Candidate Recommendation, its list of public implementations is very limited, and many areas of possible usage are unexplored.

The next revision of our book catalog vocabulary will use so-called XLink "simple links," which are very similar in principle to XHTML's "<a href=..." link. XLink uses XPointer syntax, which, according to the current CR, lets us choose between three different addressing schemes.

For the purposes of this article, we will ignore the child-sequence scheme in which the nodes are accessed through their sequence order in the document. It's very sensitive to document changes. We'll also ignore the full XPointer scheme, which, relying on XPath expressions, cannot be processed by XSLT processors without XPointer support -- which don't exist yet -- or proprietary extensions to evaluate variable XPath expressions. Instead we'll use the last addressing scheme, which is called as bare-names scheme.

The bare-names scheme is the most similar in its syntax to the XHTML anchors, and it's based on the IDs that we have already used above as physical user links. Since the DTD is currently the only mechanism supported by XPointer, we will add a minimal DTD to declare the IDs used in our document

<!DOCTYPE library [

<!ATTLIST author id ID #IMPLIED>

<!ATTLIST book id ID #IMPLIED>

<!ATTLIST character id ID #IMPLIED>

]>

(library6.xml)

This DTD is sufficient for non-validating parsers. We have declared the IDs as optional (#IMPLIED) because we are using the author and character elements both as resources and links, and DTDs do not offer different attribute lists based on the context.

The declaration of the target nodes is done by using the id attribute defined above.

   <author id="author_Charles-M.-Schulz">

      .../...

   <character id="character_Snoopy">

(library6.xml)

The references are defined using XLink simple link syntax.

   <book id="book_0836217462">

        <isbn>0836217462</isbn>

        <title>Being a Dog Is a Full-Time Job</title>

        <author xlink:href="#author_Charles-M.-Schulz" 

           xlink:type="simple">Charles-M. Schulz</author>

        <character xlink:href="#character_Peppermint-Patty" 

           xlink:type="simple">Peppermint Patty</character>

        <character xlink:href="#character_Snoopy" 

           xlink:type="simple">Snoopy</character>

        <character xlink:href="#character_Schroeder" 

           xlink:type="simple">Schroeder</character>

        <character xlink:href="#character_Lucy" 

           xlink:type="simple">Lucy</character>

    </book>

(library6.xml)

Since we are using bare-names XPointers, we are just specifying the values of the IDs we use as targets after the # separator used to separate the document URI from the fragment identifier. Additionally we could have altered the appearance of the link in a user agent using the XLink behavior attributes xlink:show (new, replace, embed, other or none) and xlink:actuate (onLoad, onRequest, other or none).

The expansion of the links can now be done by a template with a single instruction general to all nodes in our documents containing non-null xlink:href attributes.

<xsl:template match="*[@xlink:href]">

    <xsl:copy-of select="id(substring-after(@xlink:href, '#'))"/>

</xsl:template>

(expand6.xsl)

Link Validation

The situation is less appealing when we want to validate these links. Since the id value (character_Snoopy) doesn't match the reference (#character_Snoopy) because of the "#" separator, none of the DTD or XML Schema technologies can be used.

XML Schema's keyref is highly flexible, but unfortunately its field element must specify an XPath expression pointing to a node of the document. In this case, we would need to give the result of a function -- substring-after(@xlink:href, '#').

Checking the validity of XLink links is a tricky issue, mentioned in the XPointer requirements, which the XML Linking WG has avoided. In our case it should be possible, as indicated by Eve Maler, to use rule-based validators such as Schematron to perform this kind of validity check or to use a stylesheet using a similar approach as our expander (expand6.xsl).

The main benefit of using XLink simple links is the future ability of rendering tools to present these links to the users when using the XLink behavior attributes. An XLink-enabled processor might also automatically expand the document for us when xlink:show is set to embed and xlink:actuate is set to onLoad.

What we've lost by using simple XLink links is a level of abstraction, since we are again relying on physical IDs. When we write xlink:href="#character_Peppermint-Patty" we specify the node from the current document whose id is "character_Peppermint-Patty," regardless of whatever content this node might have -- we're not specifying either the character whose name is "Peppermint Patty" (user-defined logical links), or even the resource whose identifier is http://my.library/character/Peppermint-Patty (RDF).

Extended XLinks

The loss of abstraction suffered with simple XLinks is inherited from the HTML a/@href links that simple XLinks are meant to replace, and it's one of the reasons why XLink extended links have been introduced. The other reason is to allow links to live independently of the structures they link.

Please note that I don't know of any validation tool or services for extended XLinks, and that the following example has only been validated through a thorough reading of the XLink CR.

Since we will remove the links from the structure, the book elements can be simplified.

   <book id="book_0836217462">

        <isbn>0836217462</isbn>

        <title>Being a Dog Is a Full-Time Job</title>

   </book>

(library7.xml)

The character and author elements are the same as in our previous example.

For each extended link, XLink requires that we declare the participating resources. These can either local or external to the extended link. We also need to define the relations (arcs) between these resources.

To keep things simple in our example, we'll define a single extended link with all the relations between the books, author, and characters in our book catalog.

The link container is defined as

   <links xlink:type="extended">

(library7.xml)

A common characteristic of all the XLink components is that the names of the elements are not significant for XLink. The specification shows how one can take advantage of this by defining default values for the attributes, allowing a terser syntax. In this case, we could have declared in the DTD that the default value of the xlink:type attribute in the links element is extended and, thus, avoided the pain of writing it here.

While I agree that it can aid in the authoring of such documents, I have found that it makes the examples more difficult to read and understand, and I have chosen to keep a complete syntax in the example presented here.

The participants in the link are all external resources (where "external" means external to the extended link, even if in our case they are located in the same document) and the xlink:type to declare them has to be "locator." The declaration of the resources requires assigning a local label to each of them, and we'll reuse the identifier to keep things simple.

The declaration of a book is

   <book xlink:type="locator"

         xlink:href="#book_0836217462"

         xlink:role="http://my.library/roles/book"

         xlink:label="book_0836217462"/>

(library7.xml)

Similar declarations need to be made for authors.

   <author xlink:type="locator"

           xlink:href="#author_Charles-M.-Schulz"

           xlink:role="http://my.library/roles/author"

           xlink:label="author_Charles-M.-Schulz"/>

(library7.xml)

And for characters:

   <character xlink:type="locator"

              xlink:href="#character_Snoopy"

              xlink:role="http://my.library/roles/character"

              xlink:label="character_Snoopy"/>

(library7.xml)

After all the resources have been declared, we can describe all the relations between them, including relations between the books and their author.

   <arc xlink:type="arc"

        xlink:arcrole="http://my.library/roles/writen-by"

        xlink:from="book_0836217462"

        xlink:to="author_Charles-M.-Schulz"/>

(library7.xml)

And those between the books and the characters,

   <arc xlink:type="arc"

        xlink:arcrole="http://my.library/roles/featuring"

        xlink:from="book_0836217462"

        xlink:to="character_Lucy"/>

(library7.xml)

We see that we can mix physical pointers (xlink:href="#book_0836217462") with metadata which provides more information about the pointers (xlink:role="http://my.library/roles/character", or (xlink:arcrole="http://my.library/roles/featuring").

We could also have added more metadata through xlink:title attributes and used the behavior attributes (xlink:show and xlink:actuate) to provide additional information to rendering agents.

Of course, we are still using bare-names XPointers, and we need to keep the same minimal DTD then we had in our previous document.

<!DOCTYPE library [ 

<!ATTLIST author id ID #IMPLIED>

<!ATTLIST book id ID #IMPLIED>

<!ATTLIST character id ID #IMPLIED>]>

(library7.xml)

Expanding the Extended Link

Expansion is still possible using XSLT, but it requires us to go through the different steps of indirection. I have chosen to use a short XSLT template for each of these steps. Since the same element and attribute names are used at several locations in the structure with different meaning, we are using a mode (links1, link2 and links3) for each of these steps.

First, we need to go from the book node to the XLink locator that defines its label, using the book ID as a link.

<xsl:template match="lib:book">

    <xsl:copy>

        <xsl:apply-templates/>

        <xsl:variable name="id" select="concat('#', @id)"/>

        <xsl:apply-templates 

           select="/lib:library/lib:links/lib:book[@xlink:href=$id]" 

           mode="links1"/>

    </xsl:copy>

</xsl:template>

(expand7.xsl)

Then we need to go from the book locator to the different arcs in which it is involved.

<xsl:template match="lib:book" mode="links1">

    <xsl:variable name="label" select="@xlink:label"/>

    <xsl:apply-templates 

       select="../lib:arc[@xlink:from=$label]"

       mode="links2"/>

</xsl:template>

(expand7.xsl)

Then to the locators defining the resource that is linked.

<xsl:template match="lib:arc" mode="links2">

    <xsl:variable name="label" select="@xlink:to"/>

    <xsl:apply-templates 

       select="../*[@xlink:label=$label and @xlink:type='locator']"

       mode="links3"/>

</xsl:template>

(expand7.xsl)

And finally, we can copy the resource itself.

<xsl:template match="*[@xlink:type='locator']" mode="links3">

    <xsl:copy-of

       select="id(substring-after(@xlink:href, '#'))"

       mode="links"/>

</xsl:template>

(expand7.xsl)

We could have eliminated two of the four steps by using our knowledge that the labels were equal to the IDs, but we would have been dependent on this design, which would have been more error prone in the long run.

We see that, even though more complex, the manipulation of these links is still possible using conventional XML tools such as XSLT.

The validation of the links is impossible using a DTD or XML Schema because of the XPointer syntax itself. The benefit of this way of defining our links is that we have completely dissociated the elements from the links, just as we would have done in the entity-relation models used in relational databases. This dissociation has been made without losing the semantics carried by RDF: an interesting study available as a W3C Note has shown how RDF statements can be extracted from extended XLinks.

The ability to define links between nodes without modifying these nodes is key for defining links between resources you don't own on the Web. This is one of the reasons why extended XLinks is the technology of choice for topic maps. This ability can be shared by RDF though, and we could have designed our RDF example to achieve this separation between objects and relations -- we could even have used XPointers in RDF.

The difference between the extended links and RDF appears to be mostly a subtle difference of focus. RDF focuses on assertions about links; XLink on links carrying assertions.

Acknowledgements and References

Many thanks to Henry Thompson and Eve Maler for their patient answers to my emails on the W3C mailing lists, to Didier Martin whose presentation during XML Europe 2000 was the starting point of this work, and to the contributors to the RSS-DEV mailing list for their enlightening messages about RDF related issues.

Related links:

• Validating Link/XPointer local 'bare names'discussion on www-xml-linking-comments@w3.org.
• Specifying key/keyrefs constraints for Link/XPointer 'bare names'discussion on www-xml-schema-comments@w3.org.
• The Whole-Parts Information Set presentation by Didier PH Martin (XML Europe 2000).
• XML Pointer Language (XPointer) W3C Candidate Recommendation 7 June 2000
• XML Linking Language (XLink) Version 1.0 W3C Candidate Recommendation 3 July 2000
• XML Schema Part 0: Primer W3C Working Draft, 22 September 2000
• Resource Description Framework (RDF) Model and Syntax Specification W3C Recommendation 22 February 1999
• RSS 1.0 Specification Working Group
• The Official Peanuts Web Site