Temporal Regular Path Queries

Marcelo Arenas, Pedro Bahamondes, Amir Aghasadeghi, Julia Stoyanovich

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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.

    Original languageEnglish (US)
    Title of host publicationProceedings - 2022 IEEE 38th International Conference on Data Engineering, ICDE 2022
    PublisherIEEE Computer Society
    Pages2412-2425
    Number of pages14
    ISBN (Electronic)9781665408837
    DOIs
    StatePublished - 2022
    Event38th IEEE International Conference on Data Engineering, ICDE 2022 - Virtual, Online, Malaysia
    Duration: May 9 2022May 12 2022

    Publication series

    NameProceedings - International Conference on Data Engineering
    Volume2022-May
    ISSN (Print)1084-4627

    Conference

    Conference38th IEEE International Conference on Data Engineering, ICDE 2022
    Country/TerritoryMalaysia
    CityVirtual, Online
    Period5/9/225/12/22

    Keywords

    • graph query languages
    • temporal query languages

    ASJC Scopus subject areas

    • Software
    • Signal Processing
    • Information Systems

    Fingerprint

    Dive into the research topics of 'Temporal Regular Path Queries'. Together they form a unique fingerprint.

    Cite this