テーマ：“Bidirectionalizing Structural Recursive Transformation on Graphs”
講師：Zhenjiang Hu (National Institute of Informatics)
主査 小林 直樹
- 場所：東北大学 電気情報系3号館 206号室
- 題目：“Bidirectionalizing Structural Recursive Transformation on Graphs”
- 話者：Zhenjiang Hu (National Institute of Informatics)
- 概要：The bidirectional transformation problem is attracting more and more attention from researchers in programming language community, and there have been many interesting research results dealing with bidirectional transformation on strings or tree-like data structures. However, to the best of our knowledge, none of them can deal with graphs. In this paper, we show that the bidirectional transformation problem on graphs can be well solved, by proposing a bidirectional semantics for an existing graph algebra based on structural recursion called UnCAL,which has been well studied in the database community as an underlying algebra of more user-friendly syntax called UnQL graph query language.Challenges in graph transformation come from the cyclic nature of data model. We solve the problem by making use of original bulk semantics of structural recursion in which individual edge and reachable parts thereof can be independently transformed to reorganize the result. The bulk semantics also plays an important role in dealing with insertion of new graphs into the target, since which portion in the source to propagate the new graph can be relatively easily determined using the semantics. A prototype system has been implemented and is available online, and the experimental results show the usefulness of our approach.
This is a joint work with Soichiro Hidaka, Hiroyuki Kato and Keisuke Nakano.