hegnerInformationOrdering

# Title: hegnerInformationOrdering

## Overview

This example, derived from one by Hegner, was used by Cheney et al. to raise the issue of whether, from a "least change" point of view, it is better for consistency restoration to reuse old model elements or introduce new ones.

## Models

Let $M = {\cal P}(A \times B \times C)$ for some sets $A, B, C$, and let $N = {\cal P}(A \times B)$.

## Consistency

$m\in M$ is only consistent with its projection.

For example, $m = \{(a_0, b_0, c_0), (a_1, b_1, c_1)\}$ is consistent with $n = \{(a_0, b_0), (a_1, b_1)\}$, but not with $n' = \{(a_0, b_0), (a_1, b_1), (a_2, b_2)\}$.

## Consistency Restoration

$\overrightarrow{R}(m,n)$ returns the projection of $m$, i.e. the set of pairs produced by discarding the $C$ component from each triple in $m$.

$\overleftarrow{R}(m,n)$ must return something whose projection is $n$. Let us say:

1. for each pair $(a,b) \in n$ check whether there is any triple $(a,b,c) \in m$. If so, mark all such triples "justified". If not, add to $m$ a triple $(a,b,c)$ for some $c$ that does not currently occur in $m$.
2. remove from $m$ any triples not marked "justified".

## Properties

Correct and hippocratic.

## Discussion

The issue here is whether, when consistency restoration requires the use of a model element but does not precisely constrain which one, it is better to reuse an already-in-use model element, or to use a previously unused model element. The above consistency restoration has a reasonable claim to be the "least change" necessary; but it may introduce to $m$ more different elements of $C$ than needed. Is that a bug or a feature? Hegner argues that it is a feature, on the basis that to reuse previously seen elements of $C$ would make a larger change to the set of true statements about $m$. See Hegner's paper for more.

## References

This is Example 4.4 from

@inproceedings{cheney15:bx,
author = {James Cheney and Jeremy Gibbons and James McKinna and Perdita Stevens},
title = {Towards a Principle of Least Surprise for Bidirectional Transformations},
booktitle = {Proceedings of {Bx} 2015},
year = 2015,
ee = {http://ceur-ws.org/Vol-1396/p66-cheney.pdf},
publisher = {CEUR-WS.org},
series = {CEUR Workshop Proceedings},
volume = 1396
}

which was derived from

@article{DBLP:journals/amai/Hegner11,
author = {Stephen J. Hegner},
title = {Information-based distance measures and the canonical reflection of
journal = {Ann. Math. Artif. Intell.},
volume = {63},
number = {3-4},
pages = {317—355},
year = {2011},
url = {http://dx.doi.org/10.1007/s10472-012-9278-x},
doi = {10.1007/s10472-012-9278-x},
timestamp = {Mon, 19 Mar 2012 21:51:02 +0100},
biburl = {http://dblp.uni-trier.de/rec/bib/journals/amai/Hegner11},
bibsource = {dblp computer science bibliography, http://dblp.org}
}

Perdita Stevens