Structural Patterns in XML

September 4, 2002

Pattern recognition is fundamental to the human intellect. In pursuits as varied as art appreciation, home repair, and software engineering, patterns naturally inform our thinking and help us to mature. The practice of pattern recognition and use was first formalized with respect to object-oriented analysis and design (see GoF) and is for many people closely associated with OOP languages such as C++ and Java. As we will see, W3C XML Schema design can benefit from patterns, too.

Recognizing and Expressing XML Patterns

Since XML has no native behavioral aspect, the most useful patterns will naturally be structural in nature. We'll consider three such patterns in this article, and it should quickly become apparent that there are many more patterns ghosting about in our various XML systems, as yet latent and unnamed. Specifically, we'll consider:

Composite
Abstract Model
Peer Specialization

Skeptics of pattern-friendly design often see patterns as overwrought cookie cutters: they ask why one's creativity as applied to the unique problems at hand should be replaced by the careless application of a one-size-fits-all template. Though these concerns don't form an indictment of pattern-based practices, they are valid and are, perhaps, best taken as a statement of how not to apply patterns. When used well, which often means not overused, patterns should help to crystallize one's thinking about a design problem and should save time in reaching a detailed and robust solution.

Flexibility of application is especially important. The patterns below are not for cookie-cutting, by any means, and none of the diagrams or examples should be extrapolated to a concrete solution without considering what's unique about the concrete problem. It's better to adapt patterns to specific uses than it is to blindly apply them.

Composite

Motivation

XML is naturally compositional: a whole A is understood to have a part or parts B. Most element types occupy a predestined position in a document's hierarchy. They always act as children of some other type and parents of some third or fourth.

In some models, a type is seen to act as its own parent. A tree of instances of this type then has no prescribed depth: it might have one, two, or a hundred levels. Further analysis often reveals basic differences between the instances with and without children. Yet the two are closely related; how should these be modeled as WXS types, and how can derivation be best applied?

Common examples include files and folders, users and groups, and windowing systems in which certain, sometimes all types of widget are known to include and to control child widgets.

Composite is a well-known OOP pattern, most of whose interesting aspects are behavioral. It's worth challenging the value of this pattern for a purely stateful system such as an XML document. In the solution described below even the basic task of accurately encapsulating state elements justifies the minimal weight of the pattern.

Solution

A primary solution pattern and two variations exist. In all solutions, a Composite type is recognized that has the responsibility of collecting children, and a Leaf type encapsulates some state unique to childless nodes in the instance tree. (We'll ignore the degenerate case in which it is not even worth separating Composite and Leaf types.) The major differences have to do with the direction of specialization: who should extend or restrict whom?

The primary pattern is the full expression and includes a Base type to capture common state. Here the roles of the three types are completely segregated:

(The UML notation in use here is spelled out in the previous XML Schema Clinic article. See "UML for XML Schema Design)".

Variations are best applied when there is no concrete motivation for the Base type. The remaining choice is almost one of taste: should Composite specialize Leaf by adding a child collection, or should Leaf specialize Composite with a constraint that it have no children? The latter approach is a bit more work in WXS, as the specialization combines extension and restriction:

Example

In this toy astronomy schema, the Composite pattern is expressed in three types, since both celestial bodies and orbital systems have position and velocity, but only bodies have mass and only systems have children. (Note that if systems could only have bodies as children, this would not be the Composite pattern at all.)

Abstract Model (Instance Specialization)

Motivation

Ordinary type extension distinguishes base from derived type, and allows for the base type to be instantiable. Thus an instance can be of either type, although clearly not of both.

Some systems call for "instance specialization,", if you will: that is, two distinct instances must exist at some single time, one of which clarifies or completes the other. The motivation for the existence of both instances is often related to the presence of either multiple producers or consumers of data, each with different responsibilities. The more limited producer or consumer needs to see some of the relevant data, but does not need to see (or needs not to see) the more specialized information. A complex tree of information may need to be specialized in this way, resulting in two trees of similar shape, one referencing the other at several points.

A key example is found in EJB deployment descriptors, in which various EJB-defined roles such as "bean provider", "application assembler", and "deployer" require access to data at different levels of abstraction. Another is the WSDL specification, which allows its abstract model describing Web-service semantics to be realized as a concrete messaging model via bindings to SOAP, HTTP and MIME.

Solution

The abstract model and the concrete model are expressed as separate compositional trees. Referenceable elements of the abstract model must define WXS keys, and various elements in the concrete model attach to these elements via WXS key references. Precise expression will vary widely, and the following diagram is only a prototype:

This allows an instance of the abstract model to be available to one type of producer or consumer, and the concrete model to be available to another. There are many dimensions for variation on the core pattern -- too many to investigate in detail here:

Levels of abstraction: there may be more than just the two steps from abstract to concrete discussed so far. EJB, for instance, has at least three interesting levels, each applicable to one of the roles mentioned earlier.
Separate documents: if the motivation indicates the existence of multiple producer and consumer types, then it's likely that they will want to work with separate documents. WSDL descriptors are often broken into two documents, one of which includes the other. WXS import and XLink-XPointer are possible participants here, or multiple documents may be associated by application-level mechanisms.
Intra-model structure: each model may be purely compositional, or may itself include key-reference associations, as the following example does.

Example

A simple workflow model assumes all participants are humans with inboxes and outboxes. Workflow agents can be directed to carry out processes by passing information from one actor to the next via e-mail or automated phone messaging and voice- or menu-driven responses. The abstract model, then, is the workflow definition: actors, data endpoints, flows, connections, and process. This might be useful to monitoring and control software. The concrete model applies the abstract model to a specific context by naming the actors. See the schema and an instance document; note that in this example abstract and concrete models are expressed in one document.

The resulting object trees are thus distinct, but related as shown below.

Peer Specialization

Motivation

A derived type often leverages a composition or association defined for a base type but needs to constrain the part or referenced instances to some corresponding subtype. That is, where B1 is composed of B2, D1 needs to consist only of D2 instances; a D1 instance with a B2 child would be invalid.

This is a common problem for programming-language type models as well as for WXS. Programming languages have the benefit of procedural code, of course, and can assert constraints such as "D1 parts must be instances of type D2" at runtime. WXS describes structure incrementally, by segments from B1 to B2, for example, and D1 to B1. Thus there is no simple way to declare a refined relationship between D1 and D2, which are (prior to a solution) three segments distant. (Pattern-based languages like Schematron and RELAX NG have much less trouble with this, as we'll see in a moment.)

One very common example of this is the specialization of a generic container type, such as a SOAP array. The derived type wants to assert that it contains only elements of a certain type.

Solution

WXS shows off some advantages over most OOP type models here. The constraint described above is essentially a restriction of base-type content; it is not additive as most type extension mechanisms would be. WXS, of course, defines a relationship just for such constraints. The first of two examples, below, shows this technique in its purest and simplest form, as does the pattern UML:

Peer Specialization -- UML class diagram

Things get a little stickier when the base-type relationship is less direct. Say A has B has C has D: for each intervening assembly of parts a separate subtype will be required. This can get complicated, although the intervening types can at least be kept locally-scoped and anonymous, as the second example shows.

Still, past a certain point the expression of these sorts of constraints via WXS becomes unwieldy at best. Schema languages and adjunct validating approaches that are based on constraint languages really shine here. A Schematron schema would have no trouble expressing any of the constraints described thus far. A simple validating XSLT stylesheet is shown for the second example, illustrating how XPath can say in a single expression what WXS needs many nested complex types to say. (Using generic transformation technologies for validation is treated in an earlier article: see "XPath and XSLT for Validation".)

Example 1

Example 2

News articles are hierarchically decomposed into sections and paragraphs. The last hold mixed content, allowing certain proper nouns to be highlighted in the article text, perhaps for later statistical analysis. Since there are so many types between Article and ProperNoun, the Gossip restriction is quite complex, as seen in the schema. A valid and invalid instance document observe this schema.

Finally, note that the schema could be simplified greatly if the constraint were instead expressed in XPath, as shown in this validating transform.