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: 1567
Venue: PODS
Year: 2012
Pagerank: 7.3113256e-05
Overall Rank: 3,556 | 75.61%
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
530	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.0001709169
3,463	Efficient Evaluation and Approximation of Well-designed Pattern Trees	2015	PODS	7.3921264e-05
5,832	Containment and Equivalence of Well-Designed SPARQL	2014	PODS	6.0733071e-05
8,098	Designing a Query Language for RDF: Marrying Open and Closed Worlds	2016	PODS	5.4874656e-05
11,852	An Efficient Index for RDF Query Containment	2019	SIGMOD	5.093636e-05
11,895	The Tractability Frontier of Well-designed SPARQL Queries	2018	PODS	5.093636e-05
12,119	Left Bit Right: For SPARQL Join Queries with OPTIONAL Patterns (Left-outer-joins)	2015	SIGMOD	5.093636e-05
12,339	SPAM: A SPARQL Analysis and Manipulation Tool	2012	VLDB	5.093636e-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
366	Scalable Semantic Web Data Management Using Vertical Partitioning	2007	VLDB	0.00020039981
542	Hexastore: Sextuple Indexing for Semantic Web Data Management	2008	VLDB	0.00016838296
1,565	Column-Store Support for RDF Data Management: not all swans are white	2008	VLDB	0.00010349261
2,446	Querying Semantic Web Data with SPARQL	2011	PODS	8.5728114e-05
6,256	View Matching for Outer-Join Views	2005	VLDB	5.9398047e-05
6,373	Full Disjunctions: Polynomial-Delay Iterators in Action	2006	VLDB	5.8946564e-05
7,759	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS	5.5505938e-05

Semantically Similar Papers

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