TY - GEN

T1 - Structural recursion for querying ordered graphs

AU - Hidaka, Soichiro

AU - Asada, Kazuyuki

AU - Hu, Zhenjiang

AU - Kato, Hiroyuki

AU - Nakano, Keisuke

PY - 2013

Y1 - 2013

N2 - Structural recursion, in the form of, for example, folds on lists and catamorphisms on algebraic data structures including trees, plays an important role in functional programming, by providing a systematic way for constructing and manipulating functional programs. It is, however, a challenge to define structural recursions for graph data structures, the most ubiquitous sort of data in computing. This is because unlike lists and trees, graphs are essentially not inductive and cannot be formalized as an initial algebra in general. In this paper, we borrow from the database community the idea of structural recursion on how to restrict recursions on infinite unordered regular trees so that they preserve the finiteness property and become terminating, which are desirable properties for query languages. We propose a new graph transformation language called λFG for transforming and querying ordered graphs, based on the well-defined bisimulation relation on ordered graphs with special ε-edges. The language λFG is a higher order graph transformation language that extends the simply typed lambda calculus with graph constructors and more powerful structural recursions, which is extended for transformations on the sibling dimension. It not only gives a general framework for manipulating graphs and reasoning about them, but also provides a solution to the open problem of how to define a structural recursion on ordered graphs, with the help of the bisimilarity for ordered graphs with ε-edges.

AB - Structural recursion, in the form of, for example, folds on lists and catamorphisms on algebraic data structures including trees, plays an important role in functional programming, by providing a systematic way for constructing and manipulating functional programs. It is, however, a challenge to define structural recursions for graph data structures, the most ubiquitous sort of data in computing. This is because unlike lists and trees, graphs are essentially not inductive and cannot be formalized as an initial algebra in general. In this paper, we borrow from the database community the idea of structural recursion on how to restrict recursions on infinite unordered regular trees so that they preserve the finiteness property and become terminating, which are desirable properties for query languages. We propose a new graph transformation language called λFG for transforming and querying ordered graphs, based on the well-defined bisimulation relation on ordered graphs with special ε-edges. The language λFG is a higher order graph transformation language that extends the simply typed lambda calculus with graph constructors and more powerful structural recursions, which is extended for transformations on the sibling dimension. It not only gives a general framework for manipulating graphs and reasoning about them, but also provides a solution to the open problem of how to define a structural recursion on ordered graphs, with the help of the bisimilarity for ordered graphs with ε-edges.

KW - Bisimulation

KW - Graph query language

KW - Optimization

KW - Ordered graphs

KW - Structural recursion

UR - http://www.scopus.com/inward/record.url?scp=84887136659&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84887136659&partnerID=8YFLogxK

U2 - 10.1145/2500365.2500608

DO - 10.1145/2500365.2500608

M3 - Conference contribution

AN - SCOPUS:84887136659

SN - 9781450323260

T3 - Proceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP

SP - 305

EP - 318

BT - ICFP 2013 - Proceedings of the 2013 ACM SIGPLAN International Conference on Functional Programming

T2 - 2013 18th ACM SIGPLAN International Conference on Functional Programming, ICFP 2013

Y2 - 25 September 2013 through 27 September 2013

ER -