Revisiting the Expressiveness Landscape of Data Graph Queries
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917547878645760 |
|---|---|
| author | Benedikt, Michael Lin, Anthony Widjaja Yen, Di-De |
| author_facet | Benedikt, Michael Lin, Anthony Widjaja Yen, Di-De |
| contents | 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_17871 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Revisiting the Expressiveness Landscape of Data Graph Queries Benedikt, Michael Lin, Anthony Widjaja Yen, Di-De Databases 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). |
| title | Revisiting the Expressiveness Landscape of Data Graph Queries |
| topic | Databases |
| url | https://arxiv.org/abs/2406.17871 |