Towards a formal model of compatibility in Web architecture

One of the things I致e been involved in lately has been working on extensibility and versioning models for the Web and Web services. The bulk of the work shows up in the TAG finding http://www.w3.org/2001/tag/doc/versioning and in the xml.com article at http://www.xml.com/pub/a/2003/12/03/versioning.html. This thinking has also shown up in the Web Arch documents sections General principles 1.2.2 Extensibility (http://www.w3.org/TR/webarch/#general), 4.2 Extensibility and Versioning (http://www.w3.org/TR/webarch/#ext-version) and 4.5.3 Namespaces (http://www.w3.org/TR/webarch/#xml-formats).

I was really glad to see many folks including the TAG really endorse the work on extensibility and compatibility, and even more so the observation that I made that compatibility and extensibility are not just for XML data formats. That in reality, all 3 legs of the Web architecture (formats, identifiers, protocols) are formats that have defined rules for compatibility and extensibility. And whether or not the Web was designed this way, the compatibility guarantees of things like HTTP headers, URI fragment identifiers/path expressions/query strings, and document formats have the same underlying models and they are all necessary.

So what is left to do?

First up is to more formally define what is meant by compatibility and extensibility. Right now we池e a little loosy-goosy on these. David Bau, who I致e been working with a lot over the past few years, has posted some really excellent stuff on his blog (http://www.davidbau.com). Now I知 going to take a bit of a different tack than DaveB on this, but you can certainly tell me if you like his approach better. It wouldn稚 be the first time that the DB material was better than the DO material.

What I would like to do, but probably won稚 have time to do:

The relationship between format set theory and protocol set theory needs to be refined. All the work that we致e been doing so far has been around defining format set theory, but we池e missing protocol set theory. I have this intuition that they are actually the same. My theory goes that a protocol can be expressed in terms of set theory and compatibility and extensibility theories can be applied. For example, a request response protocol can be expressed as A, B. In formats, we壇 say that A, B is extensible if a C could be introduced, say A,C,B. Does the same hold true for Protocols? Given the web architecture bent, I値l take a look at the HTTP protocol for this. This would have to do an analysis of a subset of a protocol, specifically the time based sequence of messages and excluding the other stuff, like security considerations, specific timing constraints (back-off algorithms). I think that one of the big problems is that interfaces/protocol constructs in languages like Java aren稚 designed very well for distributed compatibility (such as adding in a new method) but that requires a bit of explanation. BPEL?

I want to examine the relationship of protocol set theory to WSDL, BPEL, WS-Policy needs examination. I provided one way of allowing for compatible WSDL files � that is by designing the schema for individual operations for extensibility. But the issue of whether an entire application protocol can be designed and described in WSDL/BPEL that formally supports compatibility needs to be done.

Finally, the relationship between 塗eaders� and WS-* specifications in SOAP/WSDL/WS-Policy/BPEL and compatibility could be examined. For example, what compatibility guarantees can be assumed between an application with protocol X and using spec Y and Z to pass headers? Is there an interesting set intersection that might preclude an application from being forward compatible? Are these specifications really orthogonal from a message exchange pattern perspective.

And a final thing that I won稚 have time to do, though maybe the final item will be a forcing function, is to work on formal models of compatibility on mixed namespace documents.

Formal models of compatibility and extensibility.

We provided a formal definition for language, instance, sender, receiver, component, vocabulary, terms in the finding. We also provide a definition of compatibility, but it痴 just not very adequate.

To reprise:
A language has a vocabulary that may be drawn from one or more XML Namespaces (or none). [Definition: A vocabulary is a set of terms]. The syntactic structure of the language is constrained by the use of DTDs, XML Schema, other schema languages or narrative constraints expressed in the relevant language specification.

In general, the intended meaning of a vocabulary term is scoped by the language in which the term is found. However, there is some expectation that terms drawn from an XML Namespace have a consistent meaning across all languages in which they are used.

For our purposes, [Definition: a language is an identifiable set of vocabulary terms that has defined constraints.] For example, the elements and attributes of XHTML 1.0 or the names of built-in functions in XPath 2.0. Languages may or may not be defined by a schema in any particular schema language. By language, we just mean the set of elements and attributes, or components, used by a particular application.

Now there痴 a really important point that痴 hiding in here, which is that a language must have defined constraints. This is the 田ontract� of the language. If a contract is missing, then it is very difficult to design a language with any kind of compatibility guarantees. If all you致e got is running code, and the developer wants to introduce a new feature, how does (s)he know what messages must still be understood? I would argue that a language that does not have a contract is really just an arbitrary set of terms. And there痴 no way of knowing what are valid terms or not? In the absence of a contract, is allowable or not? This is the essence of Service Oriented Architecture, the transformation of terms into a language. Without the language, figuring out the allowable terms is extremely difficult in a distributed environment. Reverse-engineering somebody else痴 software by packet sniffing simply doesn稚 scale.

There痴 a quote 鉄ervice Oriented Architecture is about shared language understanding, not about reverse engineering terms�. OK, it痴 not that great, but it gives a flavour of the rationale.

And where language understanding gets super important is when the system changes. In the absence of a language, it痴 exceedingly difficult to version the software to figure out new allowable words and sentences. The reason is that without a written definition of the contract aka language, the designer has to guess and hack at what works.

Given that contracts will be provided, we can move to examination of set theory of languages and contracts.

The Web architecture document provides a starting point.

Language subset: one language is a subset (or, "profile") of a second language if any document in the first language is also a valid document in the second language and has the same interpretation in the second language. Taken another way, the set of allowable documents in the first language is less than the first.

Language superset: one language is a superset of a second language if the second is a language subset of the first.

Language extension: one language is an extension of a second language if the first is a superset of the second. This follows our intuition, that adding to a language (extending) results in a bigger set than the first set.

Now let痴 take a look at XML languages. Imagine I define a schema that defines a really simple set of allowable documents. The 吐oo� schema allows only 1 element, a foo. A valid document is . Now we have a choice of making this extensible or not. If we say that foo is not extensible, then there is no possibility of defining additional terms. Which means a receiver doesn稚 have to think about receiving new terms. But this means that we can never change foo � in this case by adding something � and retaining compatibility.

To allow for compatibility, we advocate that the contract for foo allow extensibility. One simple extensibility model is to say foo can have any number of siblings after it. So is a legal document.

The set of allowable documents that are valid under foo we will call V0.

Now what is a 田ompatible� change to V0? According to set theory, V1 must be a subset of V0. But wait! We just said that extension was the addition of terms, and compatibility theory says we can only subset. How can we subset and superset at the same time?

Well it turns out there is a trick that gets played. There is a difference between known combination of terms and allowable combination of terms. In the case of V0, the only known combination was known was . Any additional terms are allowed, but ignored. Given that the software only knows about foo, given a it can稚 do anything except ignore it.

Let us introduce a new term and create V1. To create V1, we expand the set of 徒nown� terms. In this case, we will add a element. We say that a bar is allowed, but if it occurs, it must be the first sibling of foo. The corollary is that a is not allowed after a , thus is not valid in V1.

In defining bar, we expand the set of known terms by some amount of the unknown terms. So when we 兎xtend� our language, we increase the set of known terms. But we also reduce the set of allowable combination of terms.

One way of looking at this is that Extensibility in XML languages is actually the process of creating successive subsets of the allowable combination of terms. What you say? Extensibility is about subsetting? Allow me to explain.

V0 allows any terms after the foo element and has only one known term. V1 allow only 1 term (bar) after the foo element, allows any terms after the bar element, and has two known terms. V1 has a larger set of know combination of terms but a subset of allowable combination of terms.

What we have discovered is that a language extension is a superset of the known combination of terms but is also a subset of the allowable combination of terms. Isn稚 this deliciously ironic? Extensibility allows us to subset in the future.

We have a problem though: We can稚 describe compatibility in terms of just V0 and V1. Backwards compatibility is where V0 can be interpreted as V1, and forwards compatibility is where V1 can be interpreted as V0. How do we define the set theory for this? Our intuition says that backwards compatibility is where V0 is a subset of V1. But this is based upon the 田losed� set model, not the 登pen� set model that we致e been dealing with. We know that in the example of V, V0 is a superset of the allowable combination of terms in V1 yet is a subset of the known terms.

But we know that there is difference between the known combination of terms and the allowable combination of terms. A piece of software that knows about V0 will only send documents. If it sent any other kind of document, it would be a different language as it would know the terms. If it sent , then it has created a new vocabulary, say V2. To describe compatibility, we need to distinguish between the known combination of terms or closed set and the possible combination of terms or open set.

We will refine our definition of V to be the set of allowable terms A and K to be the set of known terms. So K is a subset of A. K0 = foo, and K1 = Foo, bar. In K1, remember that bar is optional. We need to introduce a function on our sets to determine the minimal set of terms. We will call this req() for required elements.

We use these sets and the function to determine compatibility. In the case of backwards compatibility, we can allow any of the optional known elements to be omitted. Omiting all the optional aspect of K1 is called req(K1).

V1 is backwards compatible with V0 if req(K1) = req(K0), K1 is a superset of K0, and A1 is a subset of A0.

In the case of forwards compatibility, an instance of V1 can be treated as an instance of K0.

V0 is forwards compatible with V1 if req(V1) = K0 and A1 is a subset of A0.

This follows our intuition: Forwards compatibility requires accepting and ignoring unknown content, so A0 must be larger than K0 and we have to be able to map the A0 set down to K0. If A1 is not a subset of A0, then the portion of A1 that is outsideA0 can稚 be mapped to K0.

The mapping function we talk about is described as the 溺ustIgnore� rule, and is essential to enable the mapping of V1 to the K0 portion of V0.

Now have two definitions of compatibility based upon our sets of known and allowable terms.