Kleene Closure Property Path Query Optimization Based on Node Clustered Index
Tenglong Ren, Lulu Yang, Xiaowang Zhang, Zhiyong Feng
Abstract
The evaluation of Kleene Closure Property Path Queries (KPPQs) over RDF graphs presents a fundamental trade-off. Under the intuitive simple path semantics, which forbids node repetition, the problem is NP-complete. This forces practical systems to adopt existential path semantics, which admits tractable evaluation but produces result sets bloated with redundant and often semantically meaningless paths due to unnecessary detours through cycles. This paper introduces a novel indexing framework that effectively navigates this trade-off. Our key insight is that while enumerating all simple paths is intractable, a carefully selected, compact set of representative simple paths is sufficient to correctly and completely answer connectivity queries in practice. We propose the Node Clustered Index (NCI), which pre-materializes such paths—including the longest acyclic chains and fundamental cycles —transforming online query processing from a costly graph traversal into an efficient index lookup and expansion operation. Crucially, our method guarantees that every result conforms to simple path semantics. Extensive experiments demonstrate that our approach achieves near-perfect recall, outperforming state-of-the-art systems by up to an order of magnitude. This work establishes that for NP-complete path problems, seeking polynomial-time, empirically perfect approximations is a viable and powerful paradigm, delivering both performance and quality without compromise.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Related papers
- A Reachability Index for Recursive Label-Concatenated Graph QueriesChao Zhang, Angela Bonifati, Hugo Kapp, Vlad Ioan Haprian et al.ICDE 2023 · 7 citations
- Regular Path Query Evaluation Sharing a Reduced Transitive Closure Based on Graph ReductionInju Na, Yang-Sae Moon, Ilyeop Yi, Kyu-Young Whang et al.ICDE 2022 · 10 citations
- Materialized View Selection & View-Based Query Planning for Regular Path QueriesYue Pang, Lei Zou, Jeffrey Xu Yu, Linglin YangSIGMOD 2024 · 7 citations
- Language-aware Indexing for Conjunctive Path QueriesYuya Sasaki, George Fletcher, Makoto OnizukaICDE 2022 · 1 citation
- Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive QueriesNikolaos Tziavelis, Deepak Ajwani, Wolfgang Gatterbauer, Mirek Riedewald et al.VLDB 2020 · 45 citations
