Compact Answers to Temporal Path Queries
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909711379464192 |
|---|---|
| author | Adnan, Muhammad Calvanese, Diego Corman, Julien Dignös, Anton Nutt, Werner Savković, Ognjen |
| author_facet | Adnan, Muhammad Calvanese, Diego Corman, Julien Dignös, Anton Nutt, Werner Savković, Ognjen |
| contents | We study path-based graph queries that, in addition to navigation through edges, also perform navigation through time. This allows asking questions about the dynamics of networks, like traffic movement, cause-effect relationships, or the spread of a disease. In this setting, a graph consists of triples annotated with validity intervals, and a query produces pairs of nodes where each pair is associated with a binary relation over time. For instance, such a pair could be two airports, and the temporal relation could map potential departure times to possible arrival times. An open question is how to represent such a relation in a compact form and maintain this property during query evaluation. We investigate four compact representations of answers to a such queries, which are based on alternative ways to encode sets of intervals. We discuss their respective advantages and drawbacks, in terms of conciseness, uniqueness, and computational cost. Notably, the most refined encoding guarantees that query answers over dense time can be finitely represented. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_22143 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Compact Answers to Temporal Path Queries Adnan, Muhammad Calvanese, Diego Corman, Julien Dignös, Anton Nutt, Werner Savković, Ognjen Databases We study path-based graph queries that, in addition to navigation through edges, also perform navigation through time. This allows asking questions about the dynamics of networks, like traffic movement, cause-effect relationships, or the spread of a disease. In this setting, a graph consists of triples annotated with validity intervals, and a query produces pairs of nodes where each pair is associated with a binary relation over time. For instance, such a pair could be two airports, and the temporal relation could map potential departure times to possible arrival times. An open question is how to represent such a relation in a compact form and maintain this property during query evaluation. We investigate four compact representations of answers to a such queries, which are based on alternative ways to encode sets of intervals. We discuss their respective advantages and drawbacks, in terms of conciseness, uniqueness, and computational cost. Notably, the most refined encoding guarantees that query answers over dense time can be finitely represented. |
| title | Compact Answers to Temporal Path Queries |
| topic | Databases |
| url | https://arxiv.org/abs/2507.22143 |