Formalising the Proximate Semantics of XML Languages with UML, OWL and GRDDL

Defining the middle level

Nothing beats coloured pens and a whiteboard for designing object models, which is what this is really all about, but the step from there to XML is a bit under-supported at this point, so the next best thing is a drawing program. Not a general-purpose drawing program, but rather one intended for drawing object models. And one that outputs XML. And it should be free.

UML is one obvious candidate -- it's designed for graphical use, and there are free tools available for sketching simple UML diagrams easily. The one I found and have used for the work reported here is Violet [Horst05]. It's important to emphasise that I'm not really using UML in this exercise. Rather I'm using a UML drawing tool and a limited subset of the UML conventions for drawing object models:

1. The class hierarchy (with implied inheritance);

2. The property/attribute distinction;

3. Property cardinality and directionality annotations.

Each of these is illustrated in the following diagram for a very-much simplified subset of XProc [Wal07], the XML pipeline language currently under development by the W3C's XML Processing Model Working Group:

Figure 1. Simplified class diagram

• Each box is a class, and arrows ending in open triangles indicate sub-class:super-class relations. So for example there are two kinds of Components, namely Steps and Constructs, and four kinds of Constructs, namely Pipelines, Groups, For-eaches and Viewports.

• Attributes are given within class boxes, with types in parentheses and optionality indicated with a final '?'

• Properties are notated with simple arrows. Cardinalities are given at the far end, so for example a Subpipeline has a connect property, which may be present zero or more times, and whose value is a Connect.

• A double-headed arrow indicates a bi-directional property. For example a Connect has a single destination, which is an Input Port, and this relation is 1-to-1 and can be reversed, that is, an Input Port has a destination port as well, whose value is the Connect.

Violet uses Java's XML serialiser to dump its pictures, and the next step is accordingly to convert this format to something more congenial. I use a pipeline (!) of three XSLT steps to transform the Violet output into an OWL [OWL04] ontology. The figure below illustrates (selectively) how various aspects of the object model are translated:

    <rdf:RDF xml:base="http://www.w3.org/2007/03/xproc">

[1]  <owl:Class rdf:ID="Component">
      <rdfs:subClassOf>
[5]    <owl:Restriction>
        <owl:onProperty rdf:resource="#name"/>
[7]     <owl:maxCardinality
             rdf:datatype="&xsd;#int">1</owl:cardinality>
       </owl:Restriction>
      </rdfs:subClassOf>
      <rdfs:subClassOf>
       <owl:Restriction>
        <owl:onProperty rdf:resource="#container"/>
[7]     <owl:maxCardinality
            rdf:datatype="&xsd;#integer">1</owl:maxCardinality>
       </owl:Restriction>
      </rdfs:subClassOf>
     </owl:Class>

[2]  <owl:DatatypeProperty rdf:ID="name">
      <rdfs:domain> rdf:resource="#Component"/>
      <rdfs:range rdf:resource="&xsd;.xsd#NCName"/>
     </owl:DatatypeProperty>

[3]  <owl:ObjectProperty rdf:ID="input">
      <rdfs:domain> rdf:resource="#Component"/>
      <rdfs:range rdf:resource="#InputPort"/>
     </owl:ObjectProperty>

[3]  <owl:ObjectProperty rdf:ID="container">
      <rdfs:domain> rdf:resource="#Component"/>
      <rdfs:range rdf:resource="#Construct"/>
     </owl:ObjectProperty>

[1]  <owl:Class rdf:ID="Construct">
[4]  <rdfs:subClassOf rdf:resource="#Component"/>
      <rdfs:subClassOf>
       <owl:Restriction>
        <owl:onProperty rdf:resource="#subpipeline"/>
[6]     <owl:cardinality
             rdf:datatype="&xsd;#int">1</owl:cardinality>
       </owl:Restriction>
      </rdfs:subClassOf>
     </owl:Class>

     <owl:ObjectProperty rdf:ID="subpipeline">
      <rdfs:domain rdf:resource="#Construct"/>
      <rdfs:range rdf:resource="#Subpipeline"/>
     </owl:ObjectProperty>

    </rdf:RDF>

All the key aspects of the OWL representation of the data model, as translated automatically from the quasi-UML diagram, are illustrated in this extract (the items below are keyed by number to the figure above):

1. Classes are . . . owl:Classes

2. Attributes are owl:DatatypePropertys

3. Properties are owl:ObjectPropertys

4. The class hierarchy is drawn using rdfs:subClassOf

5. Cardinality constraints are handled using subclassing and owl:Restriction

6. Required attrs/props have owl:cardinality restricted to 1 (see section ??? below for some discussion of this)

7. Optional attrs/props have owl:maxCardinality restricted to 1

Note that no cardinality constraints are present for e.g. the input property, as the UML range 0..* in the diagram means there is no constraint.

Working with the middle level

There are a number of free tools available for browsing and, to a limited extent, checking OWL ontologies. I've found SWOOP [SWOOP05], Protégé [Prot07] and Pellet [Pellet07] helpful in various ways (see also section ??? below). I also found it helpful to write a simplified version of the middle-level construction pipeline to simply extract and display all the properties from a Violet UML diagram, for example:

Developing the UML and inspecting and checking the corresponding OWL ontology interacted positively with the design process of the XProc language itself. When I couldn't determine exactly what to put in the model at certain points, I could sometimes identify under-specification in the language definition. I could then feed questions back to the Working Group to get the uncertainty resolved in a subsequent draft. I also was able to detect several places in which terminology was used in inconsistent or conflicting ways in different parts of the specification.

On the other hand, a simple class hierarchy with attributes and properties is a pretty modest modelling tool, and it is not surprising that not every difficulty in modelling represents a problem with the language being modelled. In particular, it is easy to state exceptions in the prose of a specification, but not always easy to capture them in a model. For example, the model, even in its simplified form, suggests that the 'container' property of Components is optional. If fact, it is obligatory for all components except the top-level pipeline. It would have been possible to express this in the model, but the resulting multiplication of classes would have been a very high price to pay in terms of perceived complexity.

The complete model in both Violet/UML and OWL, as well as the stylesheets needed to produce one from the other, are available online:

Mapping from XML (using GRDDL) -- Some design principles

The idea that the (in our case proximate) semantic content of an XML document can be mechanically derived from the document itself is the core proposition of the Gleaning Resource Descriptions from Dialects of Languages work [GRDDL07]. GRDDL provides conventions, both at the individual document level and at the level of namespaces or languages, for associating information about how to map from XML documents to their semantic content as notated using RDF. Although GRDDL singles out XSLT as the obvious means for expressing such mappings, it also mentions that pipelines of XSLT and other steps may be appropriate in complex cases, and we will indeed suggest that multiple steps are often appropriate.

"Divide and conquer" is an excellent software engineering design principle to use when confronted with what is, essentially, a compilation task. Breaking the overall transformation down into smaller steps not only facilitates debugging and maintenance, but also can shorten development time by facilitating understanding. In the particular case of the XProc language, the pipeline which effects the mapping, discussed briefly below, consists of six steps, all currently expressed using XSLT.

Two examples will suffice to illustrate the benefits of decomposing the mapping into stages:

• The very first step in the pipeline operates solely on elements with attributes whose value is a QName. All it does is add two additional attributes in every such case, one with the local name and the other the namespace name, if any, resulting from looking up the appropriate namespace binding. This enables all the subsequent steps to operate on that pair of attributes, instead of having to reproduce the moderately complex testing, string surgery and lookup code whenever it was needed. This considerably improves readability.

• XProc provides for quite a lot of defaulting of the connections between steps, by appeal to an environment which is recursively specified. The mapping process approaches this by constructing the environment in one step, and the connections in a subsequent step, appealing to the environment as necessary.

Another design principle which proved very useful was to organise the main mapping from the XML notation of pipeline steps into their RDF equivalents in terms of the class hierarchy itself. Named templates were defined for all but the lowest level of the class hierarchy, to carry out those aspects of the mapping which were appropriate to that level. Looking back at Figure ???, what this means is processing e.g. an p:for-each would involve not only a template which matches that element alone, but also a call to a named template for Constructs, and then in turn a call to a named template for Components.

The first, middle and last templates in this chain (and this would generalise to greater depth as needed) have a regular (and similar) structure:

<xsl:template match="[some element name]">
 <correspondingClassName>
  [add attributes as appropriate to this level alone]
  <xsl:call-template name="[superClass]"/>
  [add children as appropriate to this level alone]
 </correspondingClassName>
</xsl:template>
      
<xsl:template name="[intermediate Class]">
 [add attributes as appropriate to this level alone]
 <xsl:call-template name="[superClass]"/>
 [add children as appropriate to this level alone]
</xsl:template>

<xsl:template name="[top Class]">
 [add attributes as appropriate to top level]
 [add children as appropriate to top level]
</xsl:template>

So for instance in the p:for-each case, this would play out ore or less as follows:

<xsl:template match="p:for-each">
 <For-each>
  <xsl:call-template name="Construct"/>
  <xsl:if test="@select"><select><xsl:value-of select="@select"/></select></xsl:if>
 </For-each>
</xsl:template>
      
<xsl:template name="Construct">
 <xsl:call-template name="Component"/>
 <subpipeline>
  <Subpipeline>...</Subpipeline>
 </subpipeline>
</xsl:template>

<xsl:template name="Component">
 <xsl:attribute name="rdf:about">...<xsl:value-of select="@name"/>...</xsl:attribute>
 . . .
</xsl:template>

The standard pattern is reflected here. The element in the document itself determines the RDF class to create the instance, the Construct class template handles the subpipeline relation which is common to all constructs, and the Component class template gives the instance its RDF identity.

Checking

The mapping process provides the opportunity to check language constraints both using XSLT at the syntactic level for constraints which may not have been captured in a schema, and using ontology processors and/or SPARQL on the resulting RDF instance.

PREFIX owl: <http://www.w3.org/2002/07/owl#>
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
 SELECT ?x ?p
 WHERE {
  ?r a owl:Restriction .
  { ?r owl:cardinality 1 } UNION { ?r owl:minCardinality 1 } .
  ?r owl:onProperty ?p .
  ?p rdfs:domain ?c .
  ?x a ?c .
  OPTIONAL {?x ?p ?y}
  FILTER (!bound(?y)) }

Mapping stylesheets and example

The stylesheets for mapping from instances to models, along with an example based on Figure 1 of the XProc draft, are available: