TY - GEN
T1 - Graph queries through Datalog optimizations
AU - Tekle, K. Tuncay
AU - Gorbovitski, Michael
AU - Liu, Yanhong A.
PY - 2010
Y1 - 2010
N2 - This paper describes the use of a powerful graph query language for querying programs, and a novel combination of transformations for generating efficient implementations of the queries. The language supports graph path expressions that allow convenient use of both vertices and edges of arbitrary kinds as well as additional global and local parameters in graph paths. Our implementation method combines transformation to Datalog, recursion conversion, demand transformation, and specialization, and finally generates efficient analysis programs with precise complexity guarantees. This combination improves an O(V E) time complexity factor using previous methods to O(E), where V and E are the numbers of graph vertices and edges, respectively. We also describe implementations and experiments that confirm the analyzed complexities.
AB - This paper describes the use of a powerful graph query language for querying programs, and a novel combination of transformations for generating efficient implementations of the queries. The language supports graph path expressions that allow convenient use of both vertices and edges of arbitrary kinds as well as additional global and local parameters in graph paths. Our implementation method combines transformation to Datalog, recursion conversion, demand transformation, and specialization, and finally generates efficient analysis programs with precise complexity guarantees. This combination improves an O(V E) time complexity factor using previous methods to O(E), where V and E are the numbers of graph vertices and edges, respectively. We also describe implementations and experiments that confirm the analyzed complexities.
KW - Complexity analysis
KW - Datalog
KW - Demand-driven evaluation
KW - Graph query languages
KW - Optimization
KW - Program analysis
KW - Program transformation
UR - https://www.scopus.com/pages/publications/77956246613
U2 - 10.1145/1836089.1836093
DO - 10.1145/1836089.1836093
M3 - Conference contribution
AN - SCOPUS:77956246613
SN - 9781450301329
T3 - PPDP'10 - Proceedings of the 2010 Symposium on Principles and Practice of Declarative Programming
SP - 25
EP - 34
BT - PPDP'10 - Proceedings of the 2010 Symposium on Principles and Practice of Declarative Programming
T2 - 12th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming, PPDP 2010
Y2 - 26 July 2010 through 28 July 2010
ER -