Bx Examples Repository

Title: Composers

Version: 0.1

Type: Precise


This example stands for many cases where two slightly, but significantly, different representations of the same real world data are needed. The definition of consistency is easy, but there is a choice of ways to restore consistency.


A model $m \in M$ comprises a set of (unrelated) objects of class Composer, representing musical composers, each with a name, dates and nationality.

A model $n \in N$ is an ordered list of pairs, each comprising a name and a nationality.


Models $m$ and $n$ are consistent if they embody the same set of (name, nationality) pairs. That is, both: (i) for every composer in $m$, there is at least one entry in the list $n$ with the same name and nationality; and (ii) for every entry in $n$, there is at least one element of $m$ with the same name and nationality (there may be many such, each with distinct dates).

Consistency Restoration

Given models $m$ and $n$,


produce a modified version of $n$ by:

  • deleting from $n$ any entry for which there is no element of $m$ with the same name and nationality;
  • adding at the end of $n$ an entry comprising each (name, nationality) pair derivable from an element of $m$ but not already occurring in $n$. Such additional entries should be in alphabetical order by name, and within name, by nationality; no duplicates should be added (even if there are several composers in $m$ with the same name and nationality).


produce a modified version of $m$ by:

  • deleting from $m$ any composer for which there is no entry in $n$ with the same name and nationality;
  • adding to $m$ a new composer for each (name, nationality) pair that occurs in $n$ but is not derivable from an element already occurring in $m$. The dates of any newly added composer should be ????-????.


  • Correct
  • Hippocratic
  • Not undoable
  • Simply matching


If the bx is to be correct and hippocratic, restoring consistency must involve adding (respectively, deleting) composers that are present (respectively, not present) in the authoritative model but not in the one to be modified. Questions that the bx programmer still needs to resolve are:

  • Do we ever modify the name and/or nationality of an existing composer, or do we create a new composer in the event of any mismatch? E.g. if one side has Britten, British and the other has Britten, English, does consistency restoration involve changing one of the nationalities, or adding a second Britten? Of course if name is a key in the models there is no choice.
  • Where in the list $n$ is a new composer added? Choices include: at the beginning; at the end. We might consider in an alphabetically determined position, but note that the user is not constrained to add composers in alphabetical order, and we fail hippocraticness if we choose to reorder when nothing at all need be changed. It therefore seems unlikely that changing the order of user-added composers will be wanted.
  • What dates are used for a newly added composer in $m$?


This has been used as an example of why undoability is too strong. Consider a composer currently present (just once) in both of a consistent pair of models. If we delete it from $n$, and enforce consistency on $m$, the representation of the composer in $m$, including this composer's dates, is lost. If we now restore it to $n$ and re-enforce consistency on $m$, then the absence of any extra information besides the models means that the dates cannot be restored, so $m$ cannot return to exactly its original state.


This version was used in Perdita Stevens' slides in several 2008 events, but seems to have appeared in print first in:

Perdita Stevens:
Bidirectional model transformations in QVT: semantic issues and open questions. Software and System Modeling 9(1): 7-20 (2010)

Original (asymmetric) variant was in:

Aaron Bohannon, J. Nathan Foster, Benjamin C. Pierce, Alexandre Pilkiewicz, and Alan Schmitt. Boomerang: Resourceful Lenses for String Data. In ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), San Francisco, California, January 2008. DOI 10.1145/1328438.1328487


Perdita Stevens, James McKinna, James Cheney. University of Edinburgh.


None yet


  • we should add some of our artefacts [Perdita]
Unless otherwise stated, the content of this page is licensed under GNU Free Documentation License.