Query Planning for Evaluating SPARQL Property Paths

Summary: Proposes Waveguide, a cost-based optimizer for SPARQL property paths, using waveplans (WPs) to guide regular-path evaluation over RDF graphs. Shows WP space subsumes prior techniques, yielding large plan-cost differences and new, effective plans. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5197
Venue: SIGMOD
Year: 2016
Pagerank: 7.2251335e-05
Overall Rank: 3,649 | 74.97%
DOI: 10.1145/2882903.2882944

Incoming Non-self Citations Over Time

Authors

1. Nikolay Yakovets (York University)
2. Parke Godfrey (York University)
3. Jarek Gryz (York University)

BibTeX Citation

@inproceedings{yakovets_sigmod16,
        title = {{Query Planning for Evaluating SPARQL Property Paths}},
        author = {Yakovets, Nikolay and Godfrey, Parke and Gryz, Jarek},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2882944},
        url = {https://dl.acm.org/doi/10.1145/2882903.2882944},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,209	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD	8.9437338e-05
2,700	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	8.2411888e-05
3,473	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	7.3864987e-05
4,972	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD	6.4193234e-05
6,387	Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges	2022	VLDB	5.8896555e-05
8,046	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	5.5007031e-05
8,975	Materialized View Selection & View-Based Query Planning for Regular Path Queries	2024	SIGMOD	5.3412433e-05
9,617	NeuSO: Neural Optimizer for Subgraph Queries	2026	SIGMOD	5.2434488e-05
9,761	AvantGraph Query Processing Engine	2022	VLDB	5.2238304e-05
10,215	cuRPQ: A High-Performance GPU-Based Framework for Processing Regular and Conjunctive Regular Path Queries	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
124	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030950263
1,575	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010318258
2,066	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.2348082e-05
3,452	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS	7.4007472e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,098	Designing a Query Language for RDF: Marrying Open and Closed Worlds	2016	PODS
2	8,975	Materialized View Selection & View-Based Query Planning for Regular Path Queries	2024	SIGMOD
3	500	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB
4	5,716	Graph-Aware, Workload-Adaptive SPARQL Query Caching	2015	SIGMOD
5	747	Querying Graph Databases	2013	PODS
6	6,833	Efficient Evaluation of Queries in a Mediator for WebSources	2002	SIGMOD
7	3,067	Evaluating Queries with Generalized Path Expressions	1996	SIGMOD
8	3,556	Static Analysis and Optimization of Semantic Web Queries	2012	PODS
9	11,787	SPARQL Rewriting: Towards Desired Results	2020	SIGMOD
10	3,452	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS