Seminars

NO.091 Bidirectional Transformations

Shonan Village Center

September 26 - 29, 2016 (Check-in: September 25, 2016 )

Organizers

  • 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

Overview

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.

Report

No-091.pdf