Lune

WWW2026Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. A Reachability Index for Recursive Label-Concatenated Graph QueriesChao Zhang, Angela Bonifati, Hugo Kapp, Vlad Ioan Haprian et al.ICDE 2023 · 7 citations
  2. 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
  3. Materialized View Selection & View-Based Query Planning for Regular Path QueriesYue Pang, Lei Zou, Jeffrey Xu Yu, Linglin YangSIGMOD 2024 · 7 citations
  4. Language-aware Indexing for Conjunctive Path QueriesYuya Sasaki, George Fletcher, Makoto OnizukaICDE 2022 · 1 citation
  5. Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive QueriesNikolaos Tziavelis, Deepak Ajwani, Wolfgang Gatterbauer, Mirek Riedewald et al.VLDB 2020 · 45 citations
Dusk over the sea between two cliffs drawn in fine vertical lines