Bidirectional Transformations

NII Shonan Meeting:

@ Shonan Village Center September 26-29, 2016


  • Anthony Anjorin, Chalmers University of Technology, Sweden
  • Zinovy Diskin, McMaster University and the University of Waterloo, Canada
  • Meng Wang, University of Kent, UK
  • Yingfei Xiong, Peking University, China


Description of the meeting:
Bidirectional transformations (BX) is a common pattern of computing: transforming data from one
format to another, and requiring a transformation in the opposite direction that is in some sense an
inverse. The most well-known instance is the viewupdate problem from relational database design:
a view represents a kind of virtual database table, computed on the fly from concrete source tables
rather than being represented explicitly, and the problem comes when mapping an update of the
view back to a corresponding update on the source tables. In a similar way, the problem is central
to model transformations, playing a crucial role in software evolution: having transformed a high-level
model into a lower-level implementation, one often needs to restore consistency between the
two parts that may have evolved separately.
Giving this widespread applicability, research on BX naturally spans multiple disciplines: (1)
Programming Languages (PL), (2) Graph Transformations (GT), (3) Software Engineering (SE),
and (4) Databases (DB).

1. In PL research, the goal is to design languages that are suitable for programming BX (i.e.,
two opposing transformations are encoded in a single definition rather than with two separate
definitions). Notable techniques includes lenses – collection of combinators, which can be read
in two ways, and bidirectionalization – program transformation that constructs bidirectional
programs from unidirectional ones.

2. In GT research, a rule-based approach is taken by specifying consistency as a direction-agnostic
graph grammar, i.e., a set of high-level graph transformation rules that generate the
language of consistent pairs of graphs. Incremental forward and backward synchroniser with
desirable properties are then automatically derived by operationalising this grammar.

3. In SE research, the goal is to support different software engineering activities with BX. In software
development, people usually create different kinds of artefacts, and it has been a long-standing problem
to synchronise these artefacts and keep them consistent. By applying BX to these problems, SE researchers
have contributed to different aspects of BX research, such as synchronisation of object-oriented models,
delta-based BX, and exploring the design space of BX.

4. In DB research, BX concerns the classical view-update problem of relational databases, the
dual problem of incremental view maintenance, and modern manifestations of synchronisation
problems like data exchange and provenance. XML transformations is another active research
area of BX, effectively allowing queries to be made bidirectional.

The Shonan meeting proposed in 2016 will build on the momentum and results generated at
previous meetings of similar nature (Dagstuhl 2011 and Ban 2013) to further develop cross-disciplinary
research agenda and integration effort.