Computing Compact Answers to Temporal Path Queries using SQL

Companion Proc. of the 9th Int. Joint Conf. on Rules and Reasoning (RuleML+RR). CEUR Workshop Proceedings, https://ceur-ws.org/. 2025.

Temporal Regular Path Queries (TRPQs) are a recent extension of regular path queries over a graph where facts are annotated with time intervals. They enable navigation both in time and over the structure of the graph. TRPQs return pairs of entities, each associated with a binary temporal relation, which relates the two entities through time. This allows modelling phenomena phenomena such as virus propagation or mapping possible trip departures to arrival times when there is uncertainty about traffic. A key challenge of TRPQs is representing binary temporal relations in a compact way, and ensuring that these compact representations can be computed efficiently. While these problems have been recently investigated from the theoretical side, little attention has been paid to corresponding implementation techniques. In this work, we address this gap by introducing the first SQL-based implementation of TRPQ answering that produces compact answers. We investigate two alternative formats for compact answers. For each format, we first lay the foundations for an efficient implementation by translating TRPQ operations into operations over compact answers, thus preserving compactness during the evaluation process. In addition, we apply state-of-the-art interval coalescing techniques to reduce the cost of temporal joins and ensure that our results have minimal cardinality. We also present a dedicated benchmark and parameterized experiments that illustrate the trade-offs between the two compact representations, depending on the length of intervals in the input data and query. Our empirical findings also reveal the critical role of coalescing for efficient query answering.

@inproceedings{RuleML-RR-challenge-2025,
  title = "Computing Compact Answers to Temporal Path Queries using SQL",
   year = "2025",
   author = "Muhammad Adnan and Diego Calvanese and Julien Corman and
Anton Dignös and Werner Nutt and Ognjen Savkovic",
   booktitle = "Companion Proc. of the 9th Int. Joint Conf. on Rules and
Reasoning (RuleML+RR)",
   publisher = "CEUR-WS.org",
   series = "CEUR Workshop Proceedings, https://ceur-ws.org/",
}