Static Analysis and Optimization of Semantic Web Queries

Summary: Introduces pattern trees as tree-shaped execution plans for well-designed SPARQL, enabling transformation rules and a simple normal form that capture OPTIONAL-specific semantics. Studies equivalence/containment and the enumeration/counting complexity for this fragment. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h2f19d54afe084b2b
Venue: PODS
Year: 2012
Pagerank: 7.1261366e-05
Overall Rank: 3,637 | 75.63%
DOI: 10.1145/2213556.2213572

Incoming Non-self Citations Over Time

Authors

1. Andrés Letelier (Pontifical Catholic University of Chile)
2. Jorge Pérez (University of Chile)
3. Reinhard Pichler (Vienna University of Technology)
4. Sebastian Skritek (Vienna University of Technology)

BibTeX Citation

@inproceedings{letelier_pods12,
        address = {New York, NY, USA},
        series = {{PODS} '12},
        title = {{Static Analysis and Optimization of Semantic Web Queries}},
        url = {https://dl.acm.org/doi/10.1145/2213556.2213572},
        doi = {10.1145/2213556.2213572},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Letelier, Andrés and Pérez, Jorge and Pichler, Reinhard and Skritek, Sebastian},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
536	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00016738841
3,534	Efficient Evaluation and Approximation of Well-designed Pattern Trees	2015	PODS	7.2048261e-05
5,964	Containment and Equivalence of Well-Designed SPARQL	2014	PODS	5.914608e-05
8,292	Designing a Query Language for RDF: Marrying Open and Closed Worlds	2016	PODS	5.3441107e-05
12,201	An Efficient Index for RDF Query Containment	2019	SIGMOD	4.9605343e-05
12,244	The Tractability Frontier of Well-designed SPARQL Queries	2018	PODS	4.9605343e-05
12,461	Left Bit Right: For SPARQL Join Queries with OPTIONAL Patterns (Left-outer-joins)	2015	SIGMOD	4.9605343e-05
12,679	SPAM: A SPARQL Analysis and Manipulation Tool	2012	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
379	Scalable Semantic Web Data Management Using Vertical Partitioning	2007	VLDB	0.00019556057
558	Hexastore: Sextuple Indexing for Semantic Web Data Management	2008	VLDB	0.00016438585
1,605	Column-Store Support for RDF Data Management: not all swans are white	2008	VLDB	0.00010084951
2,494	Querying Semantic Web Data with SPARQL	2011	PODS	8.3699384e-05
6,395	View Matching for Outer-Join Views	2005	VLDB	5.7850662e-05
6,514	Full Disjunctions: Polynomial-Delay Iterators in Action	2006	VLDB	5.7438288e-05
7,938	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS	5.4059178e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,436	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS
2	4,482	Semantic Query Optimization in the Presence of Types	2010	PODS
3	3,534	Efficient Evaluation and Approximation of Well-designed Pattern Trees	2015	PODS
4	719	Querying Graph Databases	2013	PODS
5	7,793	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB
6	536	An Analytical Study of Large SPARQL Query Logs	2018	VLDB
7	8,292	Designing a Query Language for RDF: Marrying Open and Closed Worlds	2016	PODS
8	2,494	Querying Semantic Web Data with SPARQL	2011	PODS
9	9,392	Expressive Languages for Querying the Semantic Web	2014	PODS
10	5,964	Containment and Equivalence of Well-Designed SPARQL	2014	PODS