Balisage Paper: Schema Component Paths for Schema Analysis

Comparison with Extended XPaths

Coates and Dui Coates10 present the idea of using "extended XPaths" for XML Schema differencing. As with schema component paths, these extended XPaths use an XPath-like syntax to traverse the component model for an assembled schema. The paper presents how these paths can be used to compare schemas for changes.

A key difference between the extended XPaths and schema component paths is simply that there is no specification of the rules for generation and interpretation of the extended XPaths, while schema component paths are defined in a public formal specification.

Still, some differences are clear:

There are strengths and weaknesses to both approaches.

In the sections that follow we will look at how to apply SCPs to perform various schema analysis tasks, with some comparison to extended XPaths.

Schema Signatures

The set of canonical SCPs for a given schema provides a useful schema signature. This signature can be identify schemas that are functionally the same, robustly in the face of differences in physical organization of the schema documents, ordering of declarations within those schema documents and the presence of extraneous information such as comments. Furthermore, the text format of a list of canonical SCPs is simple enough that it can be processed with simple tools, such as Unix command line tools, to analyze the schema and compare it with other schemas.

 
      canonicals example.xsd | sort -f/ -s -k2,2 
      

This schema signature procedure performs a stable sort on the second field only (which is to say, the first step after the root), so top level schema components will appear with their names in order by component type, while model groups will not be reshuffled. In the case of sequence model groups, it is important to preserve the order of the particles because a change in the ordering constitutes a significant difference. However, this means that ordering changes in choice or all groups will produce different signatures even though these changes do not materially affect the schema. Similarly the reordering of attributes would also produce a different signature. Alternatively, a global sort could be used, with the opposite weakness of giving equivalent signatures to two schemas that differ in the order of particles in a sequence model group.

Schema Differences

Determining what has changed between two versions by looking at the schema documents themselves can be a daunting task. Simple file differencing can include lots of irrelevant detail, or can be stymied by a reorganization of the partitioning of the schema across multiple schema documents. A comparison of the two schema signatures is much easier to grasp and doesn't suffer from these problems.

 
      canonicals example_v1.xsd | sort -f/ -s -k2,2 > 1.out
      canonicals example_v2.xsd | sort -f/ -s -k2,2 > 2.out
      echo "*********** New in $xsd2"
      diff -w 1.out 2.out | grep '>' | sed 's/^> //'
      echo "*********** Removed from $xsd2"
      diff -w 1.out 2.out | grep '<' | sed 's/^< //'
      

 
*********** New in example_v2.xsd
/schemaElement::p:cluster
/schemaElement::p:clustering
/schemaElement::p:clustering/type::0
/schemaElement::p:clustering/type::0/model::choice
/schemaElement::p:complete
/schemaElement::p:max-terms
/schemaElement::p:min-weight
/schemaElement::p:options
/schemaElement::p:options/type::0
/schemaElement::p:options/type::0/model::choice
/schemaElement::p:score
/schemaElement::p:term/type::0/model::sequence
/schemaElement::p:term/type::0/schemaAttribute::fitness
/schemaElement::p:term/type::0/schemaAttribute::confidence
/schemaElement::p:use-db-config
/type::p:cluster
/type::p:cluster/schemaAttribute::id
/type::p:cluster/schemaAttribute::parent-id
/type::p:cluster/schemaAttribute::label
/type::p:cluster/schemaAttribute::count
/type::p:cluster/schemaAttribute::nodes
/type::p:nodes
/type::p:nodes/facet::finite
/type::p:score-kind
/type::p:score-kind/facet::enumeration
*********** Removed from example_v2.xsd
      

A schema difference based on a canonical schema component path signature will be sensitive to additions and deletions of elements and attributes, the introduction of new named types or groups, or a switch in compositor type. A change in base type will be seen as a second order effect: by what impact it has on the derived type. Such a schema difference will be insensitive to changes in occurrence or value constraints, or in facet values.

A schema difference based on extended XPaths will also be sensitive to additions and deletions of elements and attributes and switches in compositor types. It will also pick up differences in occurrence and value constraints and in facet values. A change in base type will be directly visible, but the introduction of new types will be visible as a second order effect and only if the new type is actually used within the schema. The introduction or removal of named model group and attribute groups, or the switching of an element from being local to being global will be invisible.

From the point of view of knowing what the changes are that materially affect the set of valid documents, the extended XPath approach is clearly preferable. The lack of non-component properties on schema component paths is a serious weakness in this respect. Facet values and occurrence constraints have an obvious effect on validation and changes to them count as important changes. Augmenting the schema component path model to make such values manifest as predicates, as extended XPaths do, would be a good step forward. On the other hand, from the point of view of knowing about substantive changes to the usability of the schema by other schemas or for non-validation purposes, the schema component path approach of enumerating canonical paths for all components makes sense. When an XML Schema is imported into an XQuery module, for example, all the types are present and available, even ones not used in any content model. Augmenting extended XPaths to capture information about all components would be a positive step forward for that technique.

Schema Metrics

Schema signatures can be used to calculate schema complexity metrics. Compared to the large body of work on software metrics, little has been done on schema metrics. Neither is there clear consensus of what the useful metrics should be.

A paper by Lammel, Kitsis, and Remy Lammel05 examines a number of counts and metrics and computes them against a corpus of actual schemas, as an attempt to characterize the usage patterns found in practice. The paper begins with basic counts against the XML document, and then to XML Schema aware counts of the number of global element and attribute declarations, global complex and simple type definitions, and named model group and attribute group definitions. The paper argues against the simple sum of global element declarations and global complex type definitions as a metric of schema size on the grounds that this measure is sensitive to schema construction styles: a Russian Doll schema would always rank as small (one global element declaration) no matter how deeply nested its inner element declarations became. The paper moves on to counts of local element declarations and type definitions, and proposes a simple size metric that is purely the count of all complex type definitions.

The authors then attempt to apply define something akin to McCabe McCabe76 complexity measures for XML Schemas. The metric combines the number of branches in choice model groups, the number of non-default occurrence constraints (minOccurs or maxOccurs something other than 1), the number of references to a substitution group head, the number of references to a global type definition, the number of nillable attributes, and the number of global element declarations.

Additional metrics are defined for code-oriented and instance-oriented breadth and depth. The depth metrics incorporate such features as the number of particles in content models or the number of "parties": the difference is that the code-oriented depth metric counts a reference to a named model group as 1, but the instance-oriented depth metric counts all the particles obtained by the reference. The code-oriented depth metric counts the amount of nesting of element declarations in the schema.

A paper by McDowell, Schmidt, and Yue McDowell04 proposes various schema complexity and quality metrics: counts of complex type declarations (broken down by the type of the content model), simple type declarations, annotations, derived complex types, global type declarations, the average number of attributes per type declaration, the number of references to global types, the number of unbounded elements, the average range in bounds for bounded elements ("multiplicity"), the average number of restrictions per simple type, and the fan-in and fan-out of element declarations.

Overall complexity and quality indexes apply weighting factors to various measures to give an overall score. The quality index combines the ratio of simple to complex type declarations, the percentage of annotations over total number of element declarations, the average restrictions per simple type declaration, percentage of derived complex type declarations of the total number of complex type declarations, the average bounded multiplicity size, and the average number of attributes per type declaration. The complexity index combines the number of unbounded elements, the element fanning, the number of complex type declarations, the number of simple type declarations, and the average number of attributes per complex type declaration.

There is some overlap in these metrics, such as basic counts in the number of different kinds of components, but in the main these are two very different takes on what kind of information might be interesting or useful to measure.

Many of these metrics can be readily calculated from the schema signature. For example the number of element declarations can be determined by counting the number of canonical SCPs containing 'schemaElement::' as the last step, the number of global element declarations is the number of canonical SCPs beginning with '/schemaElement::' but not containing two slashes, and the number of local element declarations is the number of canonical SCPs containing 'schemaElement::' somewhere other than at the start.

# Total number of global element declarations
canonicals example.xsd | grep '^/schemaElement::[^/]*$' | wc -l
# Total number of local element declarations
canonicals example.xsd | grep '[^/].*/schemaElement::[^/]*$' | wc -l
# Total number of element declarations
canonicals example.xsd | grep 'schemaElement::[^/]*$' | wc -l
# Type definitions
canonicals example.xsd | grep 'type::[^/]*$' | wc -l
# Attribute declarations
canonicals example.xsd | grep 'schemaAttribute::[^/]*$' | wc -l
# Named model group definitions
canonicals example.xsd | grep 'group::[^/]*$' | wc -l
# Attribute group definitions
canonicals example.xsd | grep 'attributeGroup::[^/]*$' | wc -l
# Notation declarations
canonicals example.xsd | grep 'notation::[^/]*$' | wc -l
# Identity constraint definitions
canonicals example.xsd | grep 'identityConstraint::[^/]*$' | wc -l
# Total number of components
canonicals example.xsd | wc -l 
      

Many of the metrics listed above to not lend themselves well to a simple schema-signature-based approach. Certain kinds of metrics do not lend then well to a SCP-based approach at all: certainly those that rely on the XML representation of the schema rather than the schema itself such as the number of XML nodes, for example.

SCPs do not distinguish directly between simple and complex type definitions because they form a single symbol space in XML Schema: one can have both an element declaration and a type definition named 'example', but not both a simple and complex type definition with that name. If there is a canonical SCP where a facet axis follows a type definition, we know that the type is a simple type; if there is a canonical SCP where a model axis or attribute axis follows a type definition, we know that the type is a complex type. Otherwise, we can't tell from the SCPs alone.

Another class of metrics that are not readily computable from canonical SCPs are certain kinds of inbound counts: the number of uses of global element declarations, the number of uses of a substitution group head, and so forth. Similarly, statistics that distinguish particles that derive from references to named model groups from the rest cannot be computed with canonical SCPs alone, as the schema component model records that information through through the scope property. In any case, if the content model has a reference to a global element declaration, this will not create a canonical SCP for that particle: the canonical SCP for the element declaration is the top-level one.

In addition, since non-component properties of schema components are not reflected in the SCPs, any statistic that depends on the value of such a property cannot be computed with SCPs alone. The the unbounded element multiplicity from McDowell04 and the cyclomatic complexity from Lammel05, which look at the minOccurs and maxOccurs, fall into this class.

Coates and Dui Coates10 did not look at metrics in their paper, but surely many metrics can be calculated using their extended XPaths as well. Counts of components of various types would be difficult: the distinction between element and attribute declarations seems to be manifest only in the how the type predicates are represented, the apparent loss of information about named groups suggests that not only will named groups not be counted at all, but some over-counting of element and attribute declarations is likely. Similarly, types cannot be accurately counted. In general the extended XPath approach is not conducive to measuring component reuse, which is an important aspect of schemas to measure. On the other hand, extended XPaths provide information that can be used to compute metrics that depend on occurrence constraints.

At this point, the reader will be excused for thinking that things are looking grim for the use of SCPs for obtaining serious schema metrics. All is not lost, however. First, many of these statistics can be computed by using non-canonical SCPs to select a particular set of components, and counting against that set. Where the metrics need the values of properties of particular components, the ability to select components using a non-canonical SCP needs to be augmented with an ability to inspect or query the properties. For example, the particle axis can be used to count number of particles in content models, the scope axis can be used to distinguish particles derived from named model groups from local ones, and the substitutionGroup axis can be used to count references to substitution group heads. Second, since it is far from clear which statistics to use to examine schema size, complexity, or quality, a more fruitful approach may be to see what statistics we can compute from SCPs and see what they show us. Some metrics can be replaced by similar metrics that are more amenable to calculation via SCPs. For example, looking at the ratio of SCPs containing a type definition as an intermediate step against the number of SCPs representing a type definition (that is, whose final step is a type axis) gets at similar schema characteristics as element fanning.

The simplest measure obtainable from the schema signature is a simple count of how many canonical paths there are for a particular schema. A schema with a high level of reuse of global declarations and definitions will result in fewer canonical paths. Suppose there are two schemas, one of which defines a global element declaration and uses it in two places, and one of which defines a local element declaration in each place. The first schema will have one canonical SCP for the global element declaration, while the second will have a canonical SCP for each local element declaration. Each reuse of the global declaration leads to one less canonical SCP in the schema. If two schemas have a similar number of declarations, the one with fewer paths is the simpler.

An interesting extension of the path count can be obtained by generating SCPs along the canonical axes to a particular depth, but not worrying about the other whether the SCP is canonical or not. For example, if a content model references a global element declaration, a SCP that extends the content model's SCP through the schemaElement axis would not be a canonical one (the canonical SCP is the one directly from the root to the global element declaration), but it would be a level 1 extension to a canonical SCP. A level 2 extension to a canonical SCP is the addition of one more step through a canonical axis to a level 1 extension to a canonical SCP, and so on. In some simple data-oriented schemas, the set of canonical SCPs is no different from the set of level 1 extensions. At the other extreme, schemas where content models for different elements recursively refer to each other can have a set of level 1 extensions substantially larger than the set of canonical SCPs. The growth in the number of paths as the level increases is a measure of the inter-relatedness of the components in the schema, and high growth can be the sign of a schema that has many dependencies and is therefore more complex.

Calculation of the total and average number of steps in the SCPs can also be computed readily. A higher average path length indicates less component reuse and more local definitions, more complex content models, or more additional constraints on simple type. In short: a more complex schema. Again, the growth of this measure for level N extensions gives some indication of the inter-relatedness of the components in the schema.

Table IV shows some metrics for an assortment of schemas. XMLSpec (the vocabulary used to write W3C specifications) and XHTML are relatively simple document-oriented vocabularies and measured as the sum of element declarations, attribute declarations, and type declarations they are of roughly comparable size. Simplified DocBook, a somewhat more extensive document-oriented vocabulary, is about twice as large by this measure. In terms of paths, however, DocBook is smaller than XHTML and about only about one and a half times the size of XMLSpec.

GML and FpML are both highly structured data-oriented schemas. Which is more complex? FpML has more elements, but GML has a larger E+T+A count. FpML has more paths and a larger average path length. E+T+A speaks to what one needs to know about a schema to fully make use of it in a processing environment such as XSLT or XQuery, while the path count speaks to the burden on a schema maintainer.

While the average path length for canonical SCPs does not vary greatly, the growth in average path length for level 10 paths is quite substantial. The differences in level 10 extensions is astonishing, however: simplified DocBook produces two orders of magnitudes more level 10 extensions than XMLSpec and one order of magnitude more than XHTML, despite the fact that XMLSpec is larger in terms of the element/type/attribute count and not drastically smaller in terms of the canonical SCP count and XHTML is larger in terms of the canonical SCP count. It appears that the main reason for this is that XMLSpec and XHTML make use of substitution groups and named model and attribute groups, while simplified DocBook uses large choice groups instead.

As we can see in Table V, there is a wide range in the utilization of reusable schema components. Global elements and types are broadly used, but global attributes are rare. Where attribute reuse is desired, it is accomplished (in these schemas at least), through named attribute groups. Substitution groups and named model groups seem to restrict both level 10 path counts and lengths.