Bidirectionalizing graph transformations
Bidirectionalizing graph transformations
复制标题
DOI：
10.1145/1863543.1863573
复制
发表时间：
2010-09
期刊：
影响因子：
--
通讯作者：
S. Hidaka;Zhenjiang Hu;K. Inaba;H. Kato;Kazutaka Matsuda;Keisuke Nakano
中科院分区：
文献类型：
--
作者：
S. Hidaka;Zhenjiang Hu;K. Inaba;H. Kato;Kazutaka Matsuda;Keisuke Nakano
双向转换提供了一种新颖的机制，用于同步和维护输入和输出之间的信息一致性。尽管在双向转换方面取得了许多有希望的成果，但这些成果仅限于关系数据库或XML（树状）数据库。我们挑战的问题，双向转换的上下文中的图形，提出了一个正式的定义，一个良好的双向语义的UnCAL，即，用于已知的UnQL图查询语言的图代数。我们成功的形式化的关键是充分利用图上的结构递归的递归和批量语义。我们仔细完善现有的结构递归的前向评价，使其能够产生足够的跟踪信息，为以后的后向评价。我们使用跟踪信息进行向后评估，以反映在源视图上的就地更新和删除，并采用通用的逆计算解决算法和缩小技术，以解决插入困难的问题。我们证明了我们的双向评估是良好的行为。我们目前的实现是在线提供的，并证实了我们的方法与非平凡的应用程序的有用性。
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.