davidbau.com

Theory of Compatibility (Part 3)

In the first two articles of this series, we introduced a theoretical approach to versioning compatibility:

1. The Theorem of Compatible Extensions - this theorem explains how, if contracts specify pairs of distinct rules for message producers and consumers, both forward and backward compatibility can be easily achieved. This is a departure from the typical approach of defining a single validation mode for both producers and consumers, but it is extremely powerful.
2. Versioned Contract Languages - this concept pins down the "must-ignore" rule as a way of applying compatible extensions on top of a schema language that has a single concept of validity instead of two. This is the approach taken by both HTTP and HTML (and arguably is the reason for the power of both standards), and in this second article, we analyzed how HTTP deals with version compatibility in detail.

The discussion so far has been theoretical, but our careful theorems and definitions have given us a solid foundation on which we can build permanent full compatibility between versions. This third article in the series is a practical article. We apply these theoretical ideas to versioning XML and XML Schema.

The Idea of XML Projection

In discussions with my colleague David Orchard, we have been calling the Versioned Contract Language approach to XML Schema "Validation By Projection". What does this mean?

A "projection" of an XML document is a partial copy of the document that selects out a subset of the elements and attributes, but doesn't otherwise modify the order or the content of the data.

For example, we can project an XML document by removing all elements other than the specific set of element names we want to pay attention to. For example, suppose we were interested only in the "first" and "last" and "age" elements within "customer" elements. Then our projection could begin with the following XML document:

<customer> <id>19035422</id> <first>Adam</first> <middle>L<middle> <last>Bosworth</last> <age>42</age> <since>2001-09-11</since> </customer>

And then our projection would end up producing the following stripped down document:

<customer> <first>Adam</first> <last>Bosworth</last> <age>42</age> </customer>

In practice, you may not want to select the same element names throughout the entire document. For example, while we might be interested in <age> within <customer>, we might not be interested in <age> if it apears within <wine>. So we can certainly define projections that select elements and attributes based on their context as well as their name.

That's all there is to the idea. Projection is simple enough.

Schema-Aware XML Projection

Why is XML projection interesting? Because it gives us a nice clean way to apply the "must-ignore" rule to XML. (In Part 2, we examined the theory behind the must-ignore rule.)

In other words, projection is a way to ignore the "unrecognized" parts of an XML document. Any schema defines a set of elements and attributes, and in particular, it defines the specific schema types within which those elements and attributes are recognized. So there is an interesting projection for every schema that simply removes every unrecognized element and attribute.

For example, here is a simple schema that defines the <first> and <last> and <age> elements within a customer-type

<xs:schema xmlns:...> <xs:element name="customer" type="customer-type"/> <xs:complexType name="customer-type"> <xs:sequence> <xs:element name="first" type="xs:token"/> <xs:element name="last" type="xs:token"/> <xs:element name="age" type="xs:int"/> </xs:sequence> </xs:complexType> </xs:schema>

From this schema, we can make a catalog of recognized elements:

Context	Recognized element name
globally	<customer>
inside customer-type	<first>
inside customer-type	<last>
inside customer-type	<age>

A projection that selects out these specific elements and removes others works as we would expect - it projects exactly like the first projection example above.

Projection and Validation

Notice that, since projection removes "unrecognized" elements, it helps make a document "more valid" in a way. For example, the original document (reproduced below) is invalid according to our schema, because it contains several illegal elements such as <id> and <middle> and <since>:

<customer> <id>19035422</id> <first>Adam</first> <middle>L<middle> <last>Bosworth</last> <age>42</age> <since>2001-09-11</since> </customer>

But the projected document has become valid according to our schema:

<customer> <first>Adam</first> <last>Bosworth</last> <age>42</age> </customer>

However, a projection isn't meant to guarantee validity by any means. For example, if our original document was the following:

<customer> <category>Prospect</category> <visited>Mall office</visited> <first>Yesterday</first> <age>New</age> </customer>

Then the projected document would look like this:

<customer> <first>Yesterday</first> <age>New</age> </customer>

This document is invalid according to our schema on two counts:

1. It is missing the required <last> element.
2. The <age> element is supposed to contain an int, but this one does not.

So although projection can help make some instances valid that were previously not valid, it clearly does not make all instances valid. And it is not supposed to: the purpose of projection is to ignore the parts of the document that you do not recognize. If a part of a document is recognizable, it is certainly fair to apply strict validation rules to the recognized part.

The idea that projection only eliminates unrecognized parts of a document is is similar to the way HTTP requires you to ignore completely unrecognized HTTP headers, but still requires that if you use a recognized header, you must use it correctly.

Pinning down Recognizability

To pin down projection to "recognized elements and attributes", it is necessary to pin down exactly what it means for an element or attribute to be "recognized". I propose that the most reasonable thing to do is to follow the lead of the XML Schema Specifications "element declarations consistent" rule and say that:

1. An attribute is "recognized" within a complex schema type if the attribute's name is permitted via an optional or required attribute declaration in the type, or if the attribute's name is permitted by an attribute wildcard in the type.
2. Similarly, an element is "recognized" within a complex schema type the there is a matching element particle declaration anywhere within the content model of the element (including the unified content model of the base type of an extension), or if the element name is permitted by an element wildcard in the content model, or if the element name corresponds to a global element declaration in the substitution group of an element within the content model.
3. Finally, an element is "recognized" at the top level of a document if there is a global element definition with the matching name.

There may be other reasonable ways to define recognizability. These seem like the most reasonable rules to me, but the same idea of validation by projection will still work even with a different definition of recognizability.

Using Validation By Projection

We will call a document "Valid By Projection" according to a specific schema if the document is valid after projecting to the recognized elements and attributes in the schema.

When would you want to use validation by projection as opposed to ordinary, plain old validation? Validation by projection is more lax than plain validation, and it is a way of apply a must-ignore rule. Both experience and theory tell us that:

1. Message consumers should apply validation by projection.
2. Message producers should conform to ordinary strict validation.

Using the notation of the Theorem of Compatible Extensions, this is the same as saying we should define, for a specific schema S,

p(S) = { documents valid according to S }
c(S) = { documents valid by projection according to S }

The key is that the set acepted by consumers is larger than the set allowed for producers. This allows new versions of schema to "wedge into" the gap between p(S) and c(S) while maintaining full compatibility.

Part 1 in this series described this "wedging between" idea in theoretical detail. But what does it mean in practice?

A Simple Example of Full Compatibility

Here is an example. We need to take a look at two versions of a schema. Version one has a first and last name, and an age:

<xs:schema xmlns:...> <xs:element name="customer" type="customer-type"/> <xs:complexType name="customer-type"> <xs:sequence> <xs:element name="first" type="xs:token"/> <xs:element name="last" type="xs:token"/> <xs:element name="age" type="xs:int"/> </xs:sequence> </xs:complexType> </xs:schema>

Version two introduces some additional new, optional information - a middle name and a "since" date:

<xs:schema xmlns:...> <xs:element name="customer" type="customer-type"/> <xs:complexType name="customer-type"> <xs:sequence> <xs:element name="first" type="xs:token"/> <xs:element name="middle" type="xs:token" minOccurs="0"/> <xs:element name="last" type="xs:token"/> <xs:element name="age" type="xs:int"/> <xs:element name="since" type="xs:date" minOccurs="0"/> </xs:sequence> </xs:complexType> </xs:schema>

Now, to test compatibility, we have two different interesting questions to ask:

1. Is a producer using V1 compatible with a consumer using V2? That is, do we have backward-compatibility?
2. Is a producer using V2 compatible with a consumer using V1? That is, do we have foward-compatibility?

Backward Compatibility

+----------------------+                    +----------------------+
| Old Message Producer | --(old message)--> | New Message Consumer |
+----------------------+                    +----------------------+

Backward compatibility is achieved because our V2 schema is carefully designed so that every XML document that was valid according to the V1 schema is still valid in V2. This is a kind of design that is not hard to do within ordinary schema mechanisms. In our case, the main thing we have done is to make sure that both new elements <middle> and <since> are defined to be optional.

Since a producer using V1 is required to follow strict validity according to the V1 schema, it produces documents that look like this:

<customer> <first>David</first> <last>Bau</last> <age>33</age> </customer>

Documents like this are still valid according to the V2 schema - and when they are projected into the V2 schema, they are not changed at all - so our V2 consumers have no trouble accepting them.

Forward Compatibility

+----------------------+                    +----------------------+
| New Message Producer | --(new message)--> | Old Message Consumer |
+----------------------+                    +----------------------+

Forward compatibility works because of projection. A V2 producer is required to conform to strict validation according to the V2 schema, so it is not allowed to do bad things such as put a non-number such as "n/a" within the "age" element.

But the V2 schema permits the producer to include new elements that are not present in the V1 schema such as <middle> and <since>. Here is an example valid V2 message:

<customer> <first>Edgar</first> <middle>Frank</middle> <last>Codd</last> <age>62</age> <since>1978-04-12</since> </customer>

When the V1 consumer receives this message, it applies validation by projection. In other words, it first strips out unrecognized elements as follows:

<customer> <first>Edgar</first> <last>Codd</last> <age>62</age> </customer>

Then it applies validation on the result.

Validation by projection allows V2 to include new information that would not have been recognized by V1.

Here, we can also see that it is important that the V2 schema has been carefully designed so that all elements that used to be recognized in V1 were constrained so that they are still only allowed to be used in ways that would have been valid in V1. This rule is what I call the "cannot be assumed to be recognizable rule", and it is formally set down in a previous article. When stripped of all the new elements, an instance must still be valid according to the old schema.

Next Steps

This article has described the practical key to the ideas behind the theory of compatibility. By requiring consumers to ignore unrecognized parts of messages, you open the door to easy versioning and full compatibility.

The key is to define a "projection" function for the schema language, and to require consumers to use "validation by projection" while still requiring producers to use traditional strict validation.

In our theoretical discussions, we have also established that there are a few other pieces of the puzzle. There is a "cannot be assumed to be recognizable" rule as well as a "specialization" relationship with consistency requirements that are needed to achieve rock-solid full compatibility. In future articles, we will dissect these issues in more detail.

Posted by David at January 15, 2004 08:37 AM