Skip to Main content Skip to Navigation
Conference papers

Jumping Evaluation of Nested Regular Path Queries

Rustam Azimov 1 Joachim Niehren 2 Sylvain Salvati 2
2 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : The propositional dynamic logic is a fundamental language that provides nested regular path queries for datagraphs, as needed for querying graph databases and RDF triple stores. We pro- pose a new algorithm for evaluating nested regular path queries. Not only does it evaluate path queries on datagraphs from a set of start nodes in combined linear time, but also this complex- ity bound depends only on the size of the query’s top-down needed subgraph, a notion that we introduce formally. For many queries relevant in practice, the top-down neeeded subgraph is way smaller than the whole datagraph. Our algorithm is based on a new compilation schema from nested regular path queries to monadic datalog queries that we introduce. We prove that the top-down evaluation of the datalog program visits only the top-down needed subgraph for the path query. Thereby, the combined linear time complexity depending on the size of the top-down needed subgraph is implied by a general complexity result for top-down datalog evaluation (Tekle and Liu 2010). As an application, we show that our algorithm permits to reformulate in simple terms a variant of a very efficient automata-based algorithm proposed by Maneth and Nguyen that evaluates navigational path queries in datatrees based on indexes and jumping. Moreover, our variant overcomes some limitations of Maneth and Nguyen’s: it is not bound to trees and applies to graphs; it is not limited to forward navigational XPath but can treat any nested regular path query and it can be implemented efficiently without any specialized or dedicated techniques, by simply using any efficient datalog evaluator.
Document type :
Conference papers
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Inria Links <>
Submitted on : Wednesday, June 10, 2020 - 5:16:25 PM
Last modification on : Sunday, February 14, 2021 - 9:13:41 PM


Files produced by the author(s)


  • HAL Id : hal-02492780, version 2



Rustam Azimov, Joachim Niehren, Sylvain Salvati. Jumping Evaluation of Nested Regular Path Queries. Bases de données avancées, Sep 2020, Online, France. ⟨hal-02492780v2⟩



Record views


Files downloads