Axioms of Versioning 2

I’ve written a new version of ‘Axioms of Versioning‘. I extended the formalization to get a grasp of the concept of ‘Semantic Backward Compatibility in HL7v3, which I believe is flawed (quote: “Objective of backward model compatibility is that a receiver expecting an ‘old’ version will not misinterpret content sent from a new version”). It seems to be the reverse of the position of the W3C TAG in ‘Extending and Versioning Languages: Terminology‘, and the position I would defend myself. Yet the interaction of new senders with old receivers was not sufficiently explored in my Axioms.

It turns out that exploration of this notion leads to quite natural definitions of ‘may ignore’ and ‘must understand’ semantics. The HL7v3 notion is probably best characterized by the concept of ‘partial semantical forward compatibility’ in my new Axioms. The concept is also close to, if not the same as, the TAG’s ‘Partial Understanding‘.

It really thrilled me to see how helpful my formalisms were in exploring the notions in HL7v3, and uncovering the – I think – hidden meaning in it.

Making All Changes Compatible over Multiple Versions – Part 2

In the previous article I showed how to add an optional element and make this a compatible change over two releases, so existing receivers aren’t broken by unknown elements. It is done by following two simple principles:

  1. have one or more intermediate releases;
  2. use different schema’s in intermediate releases for senders and receivers.

This strategy works well in environments where ‘Big Bang’ upgrades are undesirable and there is control over the number of different releases ‘in the field’. This applies to the Dutch national EHR infrastructure, for which I work, and probably for most exchanges between companies and/or governments.The same can be done for any kind of change. Consider making an optional element required: we have an existing

Order V1:

  • customer-id 1..1
  • name 0..1
  • order-line 1..n

with an optional ‘name’ element, and we want:

Order V2:

  • customer-id 1..1
  • name 1..1
  • order-line 1..n

Upgrading some receiving nodes to V2 would break them once they receive orders without names. If we use an intermediate release, there are no problems:

Sender 2 cannot break receiver 1. Once all parties are at V2 at least, receivers can start to upgrade to V3. If the level of control is such that there are no more than two versions allowed simultaneously, this is sufficient – else we’ll just have to have some more intermediate releases.

There are more use cases. Consider code lists: in V1, we allow the Netherlands and the USA as countries. In the next release, we want to trade with Ireland as well:

If we upgrade in two steps, every subsequent pair of releases is fully compatible. No sender can break a receiver. The same if we remove old codes:

It’s as easy to increase maximum cardinality:

Some changes take more than one intermediate release, such as adding a required element where there was none:

Sometimes we change senders first, other times receivers. It turns out there is a simple rule behind this: if the change from V1 to the final version is – by itself – backward compatible, we change receivers first. If the change is forward compatible, we change senders first.

Backward compatible changes (where new receivers can handle content from old senders) are:

  • making required elements optional;
  • introducing new optional elements;
  • increasing maximum cardinality (from 1 to n, or 0 to n, or 1 to 2);
  • adding code values;

and in general all changes which allow more document instances.
Forward compatible changes (where old receivers can handle content from new senders) are:

  • making optional elements required;
  • removing optional elements;
  • decreasing maximum cardinality (from 1 to n, or 0 to n, or 1 to 2);
  • removing code values;

and in general all changes which allow less document instances.

All patterns are reversible – if one way they describe a backward compatible change over multiple versions, then the other way they describe a forward they describe a forward compatible change and vice versa. In a next post I’ll look at some advantages and disadvantages of this approach and other approaches, such as using <xs:any> schema elements.

Making All Changes Compatible over Multiple Versions – Part 1

This article will show a way to make any change in an XML-based exchange vocabulary compatible over several versions of the exchange language. In environments where there is some control over the number of versions ‘in the field’ this is highly useful. In the Dutch Electronic Health Record exchange for instance we target a maximum of subsequent two versions in the field at any time, and so does the British NHS for their EHR. I guess – for different reasons – we will have to be bit more lenient than two versions, but the environment is still under control. It’s not uncommon in messaging scenario’s to have some control over the number over versions ‘out there’ (as opposed to publishing, where one often has little idea of what versions still exist).

Suppose we have a message version V1, a basic order with a customer id and one or more order lines. In V2 we want to add a name, since the customer may have different contacts for different orders, and needs a way to indicate this. So the V2 message looks like this:

Order V2:

  • customer-id 1..1
  • name 0..1
  • order-line 1..n

As you see, I will indicate minimum and maximum cardinality on all elements. For instance, name occurs zero times minimum and once maximum, or in other words, name is optional. The elements themselves, of course, may be complex in this example. I will add one convenient shorthand for this article, zero minimum cardinality:

Order V1:

  • customer-id 1..1
  • name 0..0
  • order-line 1..n

V1 order contain a minimum of zero names, and a maximum of zero names. In other words, V1 orders cannot contain names. This is not a common construct in schema languages, but it will help this small exposure.

If we do nothing beyond this, V2 senders will break V1 receivers: their schema’s cannot handle the unknown ‘name’ element and either validation will fail or their receiving software might break. There is no way to know without knowing all implementations, which is not doable in a field with thousands of participants. So the existing implementations will break: new senders will send unexpected content to old receivers.

One way of solving the problem is “ignoring unknown content” like HTML does – but here we’ll look at another approach. Instead of moving from version 1 to version 2, we’ll define an intermediate version with different schema’s for senders and receivers:

I’ve simplified the content, focusing on the important ‘name’ element. In version 2, we move to the intermediate situation: senders are unchanged, but receivers are upgraded to accept names. Only in version 3 can senders send names. And all of a sudden all subsequent versions can communicate with each other. If we combine this with the rule that no more than two versions co-exist at the same time, compatibility remains intact. If we allow co-existence of three or more versions at the same time, the principle remains, we’ll just need some more intermediate versions.

In the next part we’ll look at how to use this approach for all changes, not just adding optional content.

Axioms of Versioning

Obsolete, please see the latest version

Version 1

An attempt to define syntactical and semantical compatiblity of versions in a formal way. Much derives from the writings of David Orchard, especially the parts on syntactical forward and backward compatibility (though my terminology differs).

  1. Let U be a set of (specifications of) software processable languages {L1, L2, … Ln}
    1. This axiomatization does not concern itself with natural language
  2. The extension of a language Lx is a set of conforming document instances ELx = {Dx1, Dx2, … Dxn}
    1. Iff ELx = ELy then Lx and Ly are extensionally equivalent
      • Lx and Ly may still be different: they may define different semantics for the same syntactical construct
    2. Iff ELx ? ELy then Lx is an extensional sublanguage of Ly
    3. Iff ELx ? ELy then Lx is an extensional superlanguage of Ly
    4. D is the set of all possible documents; or the union of all ELx where Lx ? U
  3. For each Lx ? U there is a set of processors Px = {Px1, Px2, … Pxn} which implement Lx
    1. Each Pxy exhibits behaviour as defined in Lx
    2. Processors can produce and consume documents
    3. Each Pxy produces only documents it can consume itself
    4. At consumption, Pxy may accept or reject documents
  4. The behaviour of a processor Pxy of language Lx is a function Bxy
    1. The function Bxy takes as argument a document, and its value is a processor state
      • We assume a single processor state before each function execution, alternatively we could assume a <state, document> tuple as function argument
    2. If for two processors Pxy and Pxz for language Lx for a document d Bxy(d) = Bxz(d) then the two processors behave similar for d
      • Two processor states for language Lx are deemed equivalent if a human with thorough knowledge of language specification Lx considers the states equivalent. Details may vary insofar as the language specification allows it.
      • Processor equivalence is not intended to be formally or computably decidable; though in some cases it could be.
    3. If ?d ( d ? ELx ? Bxy(d) = Bxz(d) ) then Pxy and Pxz are behaviourally equivalent for Lx
      • If two processors behave the same for every document which belongs to a language Lx, the processors are behaviourally equivalent for Lx.
  5. An ideal language specifies all aspects of desired processor behaviour completely and unambiguously; assume all languages in U are ideal
  6. A processor Px is an exemplary processor of a language Lx if it fully implements language specification Lx; assume all processors for all languages in U are exemplary
    1. Because they are (defined to be) exemplary, every two processors for a language Lx are behaviourally equivalent
    2. ELx = { d is a document ? Px accepts d }
    3. The complement of ELx is the set of everything (normally, every document) which is rejected by Px
    4. The make set MLx = { d is a document ? Px can produce d }
  7. A language Lx is syntactically compatible with Ly iff MLx ? ELy and MLy ? ELx
    • Two languages are syntactically compatible if they accept the documents produced by each other.
    1. A language Ln+1 is syntactically backward compatible with Ln iff MLn ? ELn+1 and Ln+1 is a successor of Ln
      • A language change is syntactically backward compatible if a new receiver accepts all documents produced by an older sender.
    2. A language Ln is syntactically forward compatible with Ln+1 iff MLn+1 ? ELn and Ln+1 is a successor of Ln
      • A language change is syntactically forward compatible if an old receiver accepts all documents produced by a new sender.
  8. A document d can be a member of the extension of any number of languages
    1. Px is an (exemplary) processor of Lx, Py is an (exemplary) processor of language Ly
    2. Two langauges Lx and Ly are semantically equivalent iff ELx = ELy ? ?d ( (d ? ELx ) ? Bx(d) = By(d) )
      • If two languages Lx and Ly take the same documents as input, and their exemplary processors behave the same for every document, the languages are semantically equivalent.
      • Two languages can only be compared if their exemplary processors are similar enough to be compared.
      • Not every two languages can be compared.
      • “Semantic” should not be interpreted in the sense of “formal semantics”.
  9. The semantical equivalence set of a document d for Lx = { y ? ELx | Bx(d) = Bx(y) }
    1. Or: SLx,d = { y ? ELx | Bx(d) = Bx(y) }
      • The semantical equivalence set of a document d is the set of documents which make a processor behave the same as d
      • Semantical equivalence occurs for expressions which are semantically equivalent, such as i = i + 1 and i += 1 for C, or different attribute order in XML etc.
    2. d ? SLx,d
    3. Any two semantical equivalence sets of Lx are necessarily disjunct
      • If z ? SLx,e were also z ? SLx,d then every member of SLx,e would be in SLx,d and vice versa and thus SLx,d = SLx,e
  10. A language Ly is a semantical superlanguage of Lx iff ?d ( d ? MLx ? By(d) = Bx(d) )
    1. For all documents produced by Px, Py behaves the same as Px
      • Equivalence in this case should be decided based on Lx; if Ly makes behavioural distinctions which are not mentioned in Lx, behaviour is still the same as far as Lx is concerned
    2. It follows: ?d ( d ? MLx ? ?SLy,d ( SLy,d ? ELy ? ( SLx,d ? MLx ) ? SLy,d ? By(d) = Bx(d) ) )
      • For any document produced by Px, the part of its semantical equivalence set which Px can actually produce, is a subset of the semantical equivalence set of Py for this document
    3. For all d ? ELx ? d ? MLx there may be many equivalence sets in Ly for which By(d) ? Bx(d)
      • In other words: for documents accepted but not produced by Px, Ly may define additional behaviours
    4. Lx is a semantical sublanguage of Ly iff Ly is a semantical superlanguage of Lx
  11. A language Ln+1 is semantically backward compatible with Ln iff Ln+1 is a semantical superlanguage of Ln and Ln+1 is a successor of Ln
    1. An old sender may expect a newer, but semantically backward compatible, receiver to behave as the sender intended
    2. A language Ln is semantically forward compatible with Ln+1 iff Ln+1 is a semantical sublanguage of Ln and Ln+1 is a successor of Ln
    3. Semantic forward compatibility is only possible if a language loses semantics; i.e. it’s processors exhibit less functionality, and produce less diverse documents
    4. A processor cannot understand what it does not know about yet

More Compatibility Flavours

See also my previous posts on this issue.

So we’ve got backward and forward compatibility, and syntactical and semantical compatibility. (Quick recapture: Backward compatibility is the ability to accept data from older applications, forward compatibility the ability to accept data from newer applications. Syntactical compatibility is the ability to successfully (i.e. without raising errors) accept data from other version applications, semantical compatibility the ability to understand data from other version applications.)

So what else is there?

Noah Mendelsohn made clear to me one has to distinguish language and application compatibility.

Let’s see what this means when looking at syntactical and semantical compatibility. A language L2 is syntactically backward compatible with an earlier language L1 if and only if every L1 document is also an L2 document. Or to rephrase it: if and only if an application built to accept L2 documents also accepts L1 documents. Or (the way I like it): if and only if the set of L1 documents is a subset of the set of L1 documents:

L1 is a subset of L2

And of course L2 is forwards compatible with respect to L1 if, and only if, every L2 document is also a L1 document:

L2 is a subset of L1

This makes it quite clear that if L2 is both backward and forward compatible with respect to L1, both of the above diagrams apply, so L2 = L1:

L2 is L1

But this flies in the face of accepted wisdom! Of course both backward and forward compatibility is possible! HTML is designed to be forward compatible, is it not, through the mechanism of ‘ignore unknown tags’. And two HTML versions of course can be backward compatible, if HTMLn+1 supports everything HTMLn does. Yet the above diagrams speak for themselves as well. The distinction between language and application compatibility offers the solution. The diagrams only are about syntactical language compatibility. The HTML forward compatibility mechanism is about applications as well: HTML instructs browsers to ignore unknown markup. So the HTML compatibility mechanism is about browser, ergo application behavior.

HTML tells HTMLn browsers to accept all L2 (HTMLn+1) markup (and ignore it), and to accept all L1 (HMTLn) markup, and – not ignore, but – process it. (“If a user agent encounters an element it does not recognize, it should try to render the element’s content.” – HTML 4.01) Now this sounds familiar – that’s syntactical versus semantical compatibility, isn’t it? So HTML makes forward compatibility possible through instructing the application – the browser – to syntactically accept future versions, but semantically ignore them. The n-version browser renders n+1 element content, but has no idea what the tags around it mean (render bold and blue? render indigo and italic? render in reverse?).

Summing up: there is no such thing as two (different) languages L2 and L1 which are both back- and forward compatible. There is such a thing as two applications A1 (built for language L1) and A2 (built for L2) which are both back- and forward compatible: A1 must ignore unknown L2 syntax, and A2 must accept and process all L1 syntax and semantics:

A2 back- and forward compatible wrt A1

(Yes, and to be complete, this is a rewrite of an email list submission of mine, but vastly improved through discussions with Noah Mendelsohn and David Orchard, who may or may not agree with what I’ve said here…)

Syntactical and Semantical Compatibility

In a previous post I summarized some concepts from David Orchard’s W3C TAG Finding ‘Extending and Versioning Languages‘. Now I’ll make things complicated and talk about syntactical and semantical compatibility.

When I send you a message we can distinguish syntactical compatibility and semantical compatibility. We have syntactical compatibility when I send you a message and you can parse it – there is nothing in the content which makes you think: I cannot read this text. Semantical compatibility is about more than just reading: you need to the understand the meaning of what I’m sending you. Without syntactical compatibility, semantical compatibility is impossible. With syntactical compatibility, semantical compatibility is not guaranteed, it comes as an extra on top of syntactical compatibility.

Semantical compatibility is kind of the Holy Grail in data exchanges. Whenever two parties exchange data, there is bound to be a moment when they find they haven’t truly understood each other. To give just one example from real life: two parties exchanged data on disabled employees who (temporarily) could not work. (In the Netherlands, by law this involves labour physicians as well as insurance companies.) After exchanging data for quite a while, they found out that when they exchanged a date containing the end of the period of disability, one party sent the last day of disability, while the other expected the first working day. Just one day off, but the consequences can significantly add up when insurance is involved…

There is something funny about the relation between syntactical/semantical compatibility and backward/forward compatibility. Remember, backward compatibility is about your V2 word processor being able to handle V1 documents, or your HTML 8.0 aware browser being able to read HTML 7.0 documents. Now if this new application reads and presents the old document, we expect everything to be exactly as it was in the older application. So a HTML 7.0 <b> tag should render text bold; if the HMTL 8.0 browser does not display it this way, we do not consider HTML 8.0 (or the browser) truly backward compatible. In other words, of backward compatible applications we expect both syntactical and semantical backward compatibility: we expect the newer application not just to read the old documents, but we expect new applications to understand the meaning of old documents as well.
Forward compatibility is different. Forward compatibility is the ability of the n-th application to read n+1 documents. So a HTML 7.0 browser, when rendering a HTML 8.0 document, should not crash or show an error, but show the HTML 8.0 as far as possible. Of course, no one can expect HTML 8.0 tags to be processed by the HTML 7.0 browser, but all HTML 7.0 tags should be displayed as before, HTML 8.0 tags should be ignored. In other words, of forward compatible applications we expect syntactical, but not semantical forward compatibility.

This brings to light the key characteristic of forward compatibility: it is the ability to accept unknown syntax, and ignore its semantics. It is reflected in the paradigm: Must-Ignore-Unknown. There is a well-known corollary to this: Must-Understand. Must-Understand flags are constructs which force an application to return an error when they do not understand the thus ‘flagged’ content. Where Must-Ignore-Unknown is a directive which forces semantics of unknown constructs to be ingnored, Must-Understand flags do the reverse: they force the receiver to either understand the semantics (get your meaning) or reject the message.

When we make applications which accept new syntax (to a degree) and ignore their semantics, we make forward compatible applications. Of backward compatibility, we expect it all.

On Compatibility – Back and Forth

Compatibility in data exchanges is very different from – and much more complex than – compatibility in traditional software. David Orchard has written extensively about it in a W3C TAG Finding, ‘Extending and Versioning Languages‘. I’ve given some thought to a few concepts in his piece.

First of all, David distinguishes producers and consumers of documents. This complicates the traditional compatibility picture. With say a word processor things are simple – if your V2 word processor can read documents created with your V1 word processor, the V2 processor is backward compatible with the V1 processor. If the V1 processor can read V2 documents, it is forward compatible with V2. Of course no one will buy a V2 word processor, write documents, and then buy a V1 word processor and try to access the V2 documents, so this is uncommon in traditional software applications.

The producer/consumer distinction complicates things. All of sudden forward compatibility matters a lot. There are two possible situations:

  • an old producer sends a document to a new consumer; if the consumer needs to read it, the consumer should be backward compatible with the older producer;
  • a new producer sends a document to an older consumer; if the consumer needs to read it, the consumer should be forward compatible with the newer producer.

Since there is no universal preferred viewpoint, both back- and forward compatibility are equally important. With preferred viewpoint I mean producers nor consumers are inherently more important than the other. In traditional software, one can assume consumers to be newer than or equal to producer versions: you may try to read old documents with new software, but the reverse is seldom the case without documents being exchanged. However, sometimes there is a preferred viewpoint. In the automobile industry a few huge car makers dominate the market, with many many smaller part suppliers competing for the orders of the few big buyers. The same in consumer goods, where a few large supermarket chains dominate a market with many more food producers. In such cases, the big ones can call the shots and dictate which versions are permissable and which not. The suppliers can comply or go bust. Such an unequality may make backward or forward compatibility more important – depending on whether messages go towards or away from the big shots.

The next question is how to achieve both forms of compatibility. Backward compatibility is relatively easy to achieve: new consumers should support all document features which older producers could make (and which older consumers could read). Forward compatibility is more difficult: the old consumers should be able to process content which they do not yet know about. It can be done by ignoring all unknown content (as in HTML), or having special places in your documents where unknown (read: newer) content is allowed. In XML Schema this can be done with wildcards, special constructs which allow any kind of content where the XML Schema ‘any’ tag occurs (it can be bit more complicated than that in real life, though).This summarizes the main problem area. In a few follow-up posts I’ll explore some of these notions in more detail.