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.1484281e-05
Overall Rank: 3,633 | 75.58%
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
540	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00016726545
3,531	Efficient Evaluation and Approximation of Well-designed Pattern Trees	2015	PODS	7.2274159e-05
5,948	Containment and Equivalence of Well-Designed SPARQL	2014	PODS	5.9370407e-05
8,270	Designing a Query Language for RDF: Marrying Open and Closed Worlds	2016	PODS	5.364379e-05
12,152	An Efficient Index for RDF Query Containment	2019	SIGMOD	4.9793485e-05
12,195	The Tractability Frontier of Well-designed SPARQL Queries	2018	PODS	4.9793485e-05
12,412	Left Bit Right: For SPARQL Join Queries with OPTIONAL Patterns (Left-outer-joins)	2015	SIGMOD	4.9793485e-05
12,630	SPAM: A SPARQL Analysis and Manipulation Tool	2012	VLDB	4.9793485e-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
376	Scalable Semantic Web Data Management Using Vertical Partitioning	2007	VLDB	0.00019626699
557	Hexastore: Sextuple Indexing for Semantic Web Data Management	2008	VLDB	0.00016497067
1,598	Column-Store Support for RDF Data Management: not all swans are white	2008	VLDB	0.00010120971
2,483	Querying Semantic Web Data with SPARQL	2011	PODS	8.3997473e-05
6,382	View Matching for Outer-Join Views	2005	VLDB	5.8066944e-05
6,499	Full Disjunctions: Polynomial-Delay Iterators in Action	2006	VLDB	5.7650247e-05
7,922	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS	5.4261252e-05

Semantically Similar Papers

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