Home Books Software Projects Forums

XSLT by Example

Using XSL keys for performance.

Table of Contents

Why do we need XSL keys?

We owe much of the speed improvements in the revised xmi-to-html.xsl stylesheet to the effective use of XSL keys.

XMI for UML heavily leverages the use of XMI ID's for identifying elements in a UML model. Since most elements in a given UML model have interdependencies, the use of XMI ID's for cross-referencing within an XMI document is essential for brevity and conciseness. Examples of dependencies are association links between classes, attributes of a class, parameters of methods, interfaces, superclasses, and subclasses.

XSL keys provide a mechanism to use XMI ID's for rapid searching of the document for a model in order to find a particular element or references to the element.

What's an example of an XMI ID?

Let's take a look at some XML from our XMI project, graphics.xmi:

<!-- Abridged class definition -->
<Foundation.Core.Class xmi.id="xmi.28">

This fragment from the XML for the Circle class demonstrates the use of the 'xmi.id' attribute, here assigned the value of "xmi.28", as a form of identification for this node in the XML tree.

Looking ahead, our challenge is to use the XMI ID to find the element which it identifies in order to extract information about the element, such as its name.

How is an XMI ID used as a reference?

The following XML fragment shows a generalization relationship between the Circle class, which is the child, and the Ellipse class, which is the parent. In other terminology, Circle is a subclass of Ellipse. The Circle class is identified through its XMI ID, "xmi.28", and the Ellipse class, also shown below, is identified through its XMI ID, "xmi.11".

As you can see, an XMI ID is employed as a reference when it appears as the value of the 'xmi.idref' attribute for a Foundation.Core.Class element.

<Foundation.Core.Generalization xmi.id="xmi.13">
        <Foundation.Core.Class xmi.idref="xmi.28"/>
        <Foundation.Core.Class xmi.idref="xmi.11"/>

<!-- Abridged class definition -->
<Foundation.Core.Class xmi.id="xmi.11">

These XML fragments demonstrate how a Class may either be fully specified when it has the 'xmi.id' attribute, or used as a short-hand reference when it has the 'xmi.idref' attribute. The goal is to use the latter to find the former. And this is what we want to accomplish using XSL keys.

How are keys defined?

Towards the beginning of our stylesheet can be found the definitions for several XSL keys. Let's look at the definition for the XSL key which is used to find the name for a Classifier in a UML model:

    match="//Foundation.Core.Class |
           //Foundation.Core.Interface |

Before looking at specifics, let's try to understand what this key is used for at a high level. This key is used to find the node which contains the specification for either a Class, Interface or DataType. Remember, an element with an 'xmi.id' attribute is a specification. We will use the value of an 'xmi.idref' attribute to find the specification.

As for the specifics, the xsl:key element has the following attributes:

  • name - a string used to refer to the key when we want to do a key-based search.
  • match - an XSL Pattern which is used to search the document tree for nodes with matching path names and attributes.
  • use - an XSL Expression which identifies a (usually) unique value in the matching nodes

In our case, we want to match any element which is a Class, Interface or DataType and has an 'xmi.id' attribute. We will use the value of the 'xmi.id' attribute as the unique identifier for the node which contains the element.

References: [XSLT Programmer's Reference, xsl:key pp. 222-229]

What does the XSLT processor do with XSL key declarations?

In order to speed up processing, a good XSLT processor will create an index for each key declaration. The index is analogous to an index created for a column in a relational database, also used to speed up searching.

In our case, the XSLT processor will create an index wherein the values are taken from the 'xmi.id' attributes of Classes, Interfaces and DataTypes. The result of a lookup on this index is to return the associated node in the document. We are not so much concerned with how the XSLT processor accomplishes this - just that it works!

The following table is a visualization of a possible lookup index that an XSLT processor could create for our example:

Index Node
xmi.11 Ellipse
xmi.28 Circle

How are keys used?

Now comes the interesting part: how keys are actually used to search a document. XSL defines a key() function to accomplish this job. The syntax of the function is as follows:

key ( name, value ) => node-set
  • name - the name of a key declared in an xsl:key definition.
  • value - the value used to search for the key
  • node-set - the set of document nodes returned from the key function

In our graphics project, the following stylesheet fragments demonstrate how keys are used. When processing a Class we want to find the possible subtypes. If a class has a generalization relationship then we can get the 'xmi.idref' attribute which identifies the child and then use it to retrieve the specification for the child.

From the xsl:template with the name "subtypes":

<xsl:variable name="target"
<xsl:call-template name="classify">
    <xsl:with-param name="target" select="$target"/>

Here an XSL variable named "target" is assigned the value of the XMI ID retrieved from the 'xmi.idref' attribute for the child class. (Note the use of the wildcard match, '*', here. This is used because inheritance can also take place with interfaces.)

The work of creating the HTML for a Classifier is then accomplished in the xsl:template named "classify". It takes one parameter, "target", which is the 'xmi.idref' used for searching.

From the xsl:template with the name "classify":

<xsl:variable name="classifier"
              select="key('classifier', $target)"/>
<xsl:variable name="classifier_name"

Here the key() function is invoked with the name of our xsl:key described earlier - "classifier". The value passed in is the 'xmi.idref' for the child.

The result of calling the key() function is the node which contains the specification for the child. This is assigned to the xsl:variable named "classifier". We then extract the name for the Classifier and use it to create the appropriate HTML (not shown here).

References: [XSLT Programmer's Reference, key() pp. 469-473]

Is it fast?

Using the Xalan 1.2 XSLT processor the current version of our XSL stylesheet takes under 2 seconds to read in the graphics.xmi file and under 1 second to perform the transformation and create the output XHTML file. These benchmarks were taken on a 700 Mhz Pentium III class machine using JDK 1.3. That's fast. Without the use of keys it was significantly slower.

Valid XHTML 1.0!