2023/03/24 by Lei Zou, Yue Pang, Zou, Lei +5
Computer Science · #Advanced Database Systems and Queries #Databases (cs.DB) #FOS: Computer and information sciences #Graph Theory and Algorithms #Semantic Web and Ontologies
paper · pdf · doi:10.48550/arxiv.2303.13844
openalex publication_date 2023/03/24 · openalex created_date 2023/03/31 · openalex updated_date 2026/07/28
The proliferation of RDF datasets has resulted in studies focusing on optimizing SPARQL query processing. Most existing work focuses on basic graph patterns (BGPs) and ignores other vital operators in SPARQL, such as UNION and OPTIONAL. SPARQL queries with these operators, which we abbreviate as SPARQL-UO, pose serious query plan generation challenges. In this paper, we propose techniques for executing SPARQL-UO queries using BGP execution as a building block, based on a novel BGP-based Evaluation (BE)-Tree representation of query plans. On top of this, we propose a series of cost-driven BE-tree transformations to generate more efficient plans by reducing the search space and intermediate result sizes, and a candidate pruning technique that further enhances efficiency at query time. Experiments confirm that our method outperforms the state-of-the-art by orders of magnitude.