Graph queries through datalog optimizations

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(VE) 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.