Temporal Regular Path Queries

Arenas, Marcelo; Bahamondes, Pedro; Aghasadeghi, Amir; Stoyanovich, Julia; IEEE COMP SOC

Abstract

In the last decade, substantial progress has been made towards standardizing the syntax of graph query languages, and towards understanding their semantics and complexity of evaluation. In this paper, we consider temporal property graphs (TPGs) and propose temporal regular path queries (TRPQs) that incorporate time into TPG navigation. Starting with design principles, we propose a natural syntactic extension of the MATCH clause of popular graph query languages. We then formally present the semantics of TRPQs, and study the complexity of their evaluation. We show that TRPQs can be evaluated in polynomial time if TPGs are time-stamped with time points, and identify fragments of the TRPQ language that admit efficient evaluation over a more succinct interval-annotated representation. Finally, we implement a fragment of the language in a state-of-the-art dataflow framework, and experimentally demonstrate that TRPQ can be evaluated efficiently.

Más información

Título según WOS: ID WOS:000855078402035 Not found in local WOS DB
Título de la Revista: 2022 IEEE 38TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING (ICDE 2022)
Editorial: IEEE COMPUTER SOC
Fecha de publicación: 2022
Página de inicio: 2412
Página final: 2425
DOI:

10.1109/ICDE53745.2022.00226

Notas: ISI