Taming the Expressiveness and Programmability of Graph Analytical Queries
This work addresses the problem of limited expressiveness and programmability in graph query languages for researchers and practitioners in graph databases, though it appears incremental as it builds on existing DSL concepts.
The authors tackled the lack of a domain-specific language (DSL) that fully covers completeness, expressiveness, and programmability for graph analytical queries by proposing the \flash DSL, which is proven Turing complete and achieves good expressiveness and programmability, with experiments showing it can program complex algorithms with satisfactory runtime.
Graph database has enjoyed a boom in the last decade, and graph queries accordingly gain a lot of attentions from both the academia and industry. We focus on analytical queries in this paper. While analyzing existing domain-specific languages (DSLs) for analytical queries regarding the perspectives of completeness, expressiveness and programmability, we find out that none of existing work has achieved a satisfactory coverage of these perspectives. Motivated by this, we propose the \flash DSL, which is named after the three primitive operators Filter, LocAl and PuSH. We prove that \flash is Turing complete (completeness), and show that it achieves both good expressiveness and programmability for analytical queries. We provide an implementation of \flash based on code generation, and compare it with native C++ codes and existing DSL using representative queries. The experiment results demonstrate \flash's expressiveness, and its capability of programming complex algorithms that achieve satisfactory runtime.