Revisiting the Expressiveness Landscape of Data Graph Queries
<|reference_start|>Revisiting the Expressiveness Landscape of Data Graph Queries: The study of graph queries in database theory has spanned more than three decades, resulting in a multitude of proposals for graph query languages. These languages differ in the mechanisms. 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), augmented with transitive closure operators, can unify the expressivity of (1)--(3) without increasing the query evaluation complexity.<|reference_end|>
@article{benedikt2024revisiting,
    title={Revisiting the Expressiveness Landscape of Data Graph Queries},
    author={Michael Benedikt and Anthony Widjaja Lin and Di-De Yen},
    journal={arXiv preprint arXiv:2406.17871},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.17871},
    primaryClass={cs.DB}
}