Properties for Paths in Graph Databases
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908472622186496 |
|---|---|
| author | Orejas, Fernando Pino, Elvira Angles, Renzo Pasarella, Edelmira Milonakis, Nikos |
| author_facet | Orejas, Fernando Pino, Elvira Angles, Renzo Pasarella, Edelmira Milonakis, Nikos |
| contents | This paper presents a formalism for defining properties of paths in graph databases, which can be used to restrict the number of solutions to navigational queries. In particular, our formalism allows us to define quantitative properties such as length or accumulated cost, which can be used as query filters. Furthermore, it enables the identification and removal of paths that may be considered ill-formed.
The new formalism is defined in terms of an operational semantics for the query language that incorporates these new constructs, demonstrating its soundness and completeness by proving its compatibility with a simple logical semantics. We also analyze its expressive power, showing that path properties are more expressive than register automata. Finally, after discussing some complexity issues related to this new approach, we present an empirical analysis carried out using our prototype implementation of the graph database that serves as a running example throughout the paper. The results show that queries using path properties as filters outperform standard queries that do not use them. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_19329 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Properties for Paths in Graph Databases Orejas, Fernando Pino, Elvira Angles, Renzo Pasarella, Edelmira Milonakis, Nikos Databases Logic in Computer Science This paper presents a formalism for defining properties of paths in graph databases, which can be used to restrict the number of solutions to navigational queries. In particular, our formalism allows us to define quantitative properties such as length or accumulated cost, which can be used as query filters. Furthermore, it enables the identification and removal of paths that may be considered ill-formed. The new formalism is defined in terms of an operational semantics for the query language that incorporates these new constructs, demonstrating its soundness and completeness by proving its compatibility with a simple logical semantics. We also analyze its expressive power, showing that path properties are more expressive than register automata. Finally, after discussing some complexity issues related to this new approach, we present an empirical analysis carried out using our prototype implementation of the graph database that serves as a running example throughout the paper. The results show that queries using path properties as filters outperform standard queries that do not use them. |
| title | Properties for Paths in Graph Databases |
| topic | Databases Logic in Computer Science |
| url | https://arxiv.org/abs/2507.19329 |