Revisiting the Expressiveness Landscape of Data Graph Queries
This work provides a complete picture of the expressive power of existing graph query languages, which is important for researchers and practitioners designing and using graph databases.
This paper investigates the expressive power of three families of graph query languages: regular path queries, walk logic, and first-order logic with transitive closure operators, within a data graph model that considers both data and topology. The authors demonstrate that an extension of regular path queries, incorporating regular path comparisons and transitive closure operators, can unify the expressivity of all three families.
The study of graph queries in database theory has spanned more than three decades, resulting in a multitude of proposals for graph query languages. We can identify three main families of languages, with the canonical representatives being: (1) regular path queries, (2) walk logic, and (3) first-order logic with transitive closure operators. This paper provides a complete picture of the expressive power of these languages in the context of data graphs. Specifically, we consider a graph data model that supports querying over both data and topology. For example, ``Does there exist a path between two different persons in a social network with the same last name?''. We also show that an extension of (1) with regular path comparisons, augmented with transitive closure operators, can unify the expressivity of (1)--(3).