Jumping Evaluation of Nested Regular Path Queries

Joachim Niehren (1) , Sylvain Salvati (1) , Rustam Azimov (2)

1 LINKS - Linking Dynamic Data
2 SPBU - Saint Petersburg State University

Nested regular path queries are used for querying graph databases and RDF triple stores. We pro- pose a new algorithm for evaluating nested regular path queries on a graph from a set of start nodes in combined linear time. We show that this complexity upper bound can be reduced by making it de- pendent on the size of the query’s top-down needed subgraph, a notion that we introduce. For many queries in practice, the top-down needed subgraph is way smaller than the whole graph. Our algo- rithm is based on a novel compilation schema from nested regular path queries to monadic datalog queries. Its complexity upper bound follows from known properties of top-down datalog evaluation. 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, it 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 dedicated techniques, by using any efficient top-down datalog evaluator. We confirm the efficiency of our algorithm experimentally based on an implementation with LogicBlox.

Domaines: Base de données [cs.DB]

Joachim Niehren, Sylvain Salvati, Rustam Azimov. Jumping Evaluation of Nested Regular Path Queries. 38th International Conference on Logic Programming (ICLP'2022), Jul 2022, Haifa, Israel. ⟨hal-02492780v5⟩