Optimization of Kleene closure regular path query on large RDF graphs
Tenglong Ren, Xiaowang Zhang, Zhiyong Feng · The Computer Journal · 2025
Abstract As the core operator of regular path query (RPQ), the Kleene closure is essentially a recursive operation based on predicates. It has more expressive power than first-order logic, but its algorithmic complexity is an NP-hard problem and expensive to execute. Most approaches implement Kleene closure via online recursive queries (inefficient for large-scale data), yet significant reusable intermediate results emerge during execution. This paper proposes an efficient query optimization method based on offline preprocessing and tree-structured strategies to address the challenges of NP-hard complexity and low execution efficiency caused by the recursive nature of Kleene closure RPQs (KRPQs). The core contributions of this work include: (i) recursive index tree: by precomputing and materializing intermediate results of predicate paths offline, Kleene closure queries are transformed into non-recursive SPARQL queries. This allows direct retrieval of answer branches from the preconstructed index tree, eliminating redundant computations and reducing online complexity. (ii) Selectivity-driven dynamic optimization: a heuristic cost model estimates intermediate result sizes to guide query plan generation, minimizing redundant operations. (3) Query decomposition tree for nested KRPQs: a hierarchical decomposition algorithm processes nested Kleene closures layer-by-layer from inner to outer expressions, overcoming limitations of existing methods in handling complex nested structures. Experiments on large-scale RDF datasets demonstrate that the method reduces average response times by 50%–70% for single-predicate and expression-based Kleene closure queries compared to systems like Virtuoso, Jena, and KRPQ, with over 60% improvement for complex nested queries. Additionally, multithreaded preprocessing and path pool optimizations achieve up to a 76$\times $ reduction in index construction time. Experiments show that the method can significantly reduce the time of KRPQs based on large RDF graphs.