Bidirectionalizing Graph Transformation - Related works

7. Related Work

Bidirectional transformation has been discussed as view updat- ing problem in the database community. 

• Bancilhon and Spyratos (1981) proposed a general approach to the view updating problem. They introduced an elegant solution based on the concept of a constant complement view that captures the information in the view but not in the original database. 
• Their idea was not only applied to relational databases (Hegner 1990; Lechtenbo ̈rger and Vossen 2003) but also to tree structures (Matsuda et al. 2007). Constant comple- ment views satisfy very strong bidirectional properties at the sac- rifice of the number of reflectable updates. 
• Although such strong properties are nice for some applications (Hegner 1990), they are too strong for our purpose, i.e., model transformation in software engineering. 
• Recent work by Fegaras (2010) propagates updates on XML views created from relational databases. It supports dupli- cates but detects view side effects at both compile and run time. 

In the area of programming languages, view updating has been studied as bidirectional transformation. 

• Foster et al. (2005) pro- posed the first linguistic approach to solving this problem. They developed some domain specific languages to support the develop- ment of bidirectional transformation on strings and trees. 
• Bohannon et al. (2006) applied these techniques to relational databases, mak- ing use of functional dependencies in relations to correctly prop- agate updates. 
• However, their approach is limited to strings, trees and relations, and is difficult to apply to graph transformation due to graph-specific features such as circularity and sharing. 

Within the context of software engineering, 

• there has been sev- eral works on bidirectional model (graph) transformation (Ehrig et al. 2005; Jouault and Kurtev 2005; OMG 2005; Schu ̈rr and Klar 2008; Stevens 2007), which can deal with kinds of graph structures. 
• However, they lack a clear formal bidirectional semantics and there has not yet been any powerful method of bidirectionalization that can be used to automatically derive backward model transforma- tions from forward model transformations, so that both transforma- tions can form a consistent bidirectional model transformation. 

The concept of structural recursion is not new and has been studied in both the database (Breazu-Tannen et al. 1991) and the functional programming communities (Sheard and Fegaras 1993). 

• However, most of these have focused on structural recursion over lists or trees instead of graphs. Examples include the higher order function fold (Sheard and Fegaras 1993) in ML and Haskell, and the generic computation pattern called catamorphism in programming algebras (Bird and de Moor 1996). 
• UnCAL (Buneman et al. 2000) demonstrates that the idea of structural recursion can be extended to graphs, but the original focus was on the optimization of query fusion rather than bidirectionalization. 

Our work was greatly inspired by interesting work on efficient graph querying (Buneman et al. 2000; Sheng et al. 1999). 

• Un- like trees, graphs involve subtle issues on their representation and equivalence. The use of bisimulation and structural recursion in (Buneman et al. 2000) opens a new way of building a framework for both declarative and efficient graph querying with high modularity and composability. 
• This motivated us to extend the framework from graph querying to graph transformation and apply it to model trans- formation (Hidaka et al. 2009). 
• This work is a further step in this direction to extend it from unidirectional model transformation to bidirectional model transformation.