Bidirectionalizing graph transformations

Soichiro Hidaka, Zhenjiang Hu, Kazuhiro Inaba, Hiroyuki Kato, Kazutaka Matsuda, Keisuke Nakano

Research output: Chapter in Book/Report/Conference proceedingConference contribution

58 Citations (Scopus)


Bidirectional transformations provide a novel mechanism for synchronizing and maintaining the consistency of information between input and output. Despite many promising results on bidirectional transformations, these have been limited to the context of relational or XML (tree-like) databases. We challenge the problem of bidirectional transformations within the context of graphs, by proposing a formal definition of a well-behaved bidirectional semantics for UnCAL, i.e., a graph algebra for the known UnQL graph query language. The key to our successful formalization is full utilization of both the recursive and bulk semantics of structural recursion on graphs. We carefully refine the existing forward evaluation of structural recursion so that it can produce sufficient trace information for later backward evaluation. We use the trace information for backward evaluation to reflect in-place updates and deletions on the view to the source, and adopt the universal resolving algorithm for inverse computation and the narrowing technique to tackle the difficult problem with insertion. We prove our bidirectional evaluation is well-behaved. Our current implementation is available online and confirms the usefulness of our approach with nontrivial applications.

Original languageEnglish
Title of host publicationICFP'10 - Proceedings of the 2010 ACM SIGPLAN International Conference on Functional Programming
Number of pages12
Publication statusPublished - 2010
Event15th ACM SIGPLAN International Conference on Functional Programming, ICFP'10 - Baltimore, MD, United States
Duration: 2010 Sept 272010 Sept 29

Publication series

NameProceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP


Other15th ACM SIGPLAN International Conference on Functional Programming, ICFP'10
Country/TerritoryUnited States
CityBaltimore, MD


  • bidirectional transformation
  • graph query and transformation
  • structural recursion
  • view updating

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Bidirectionalizing graph transformations'. Together they form a unique fingerprint.

Cite this