Efficient Evaluation and Approximation of Well-designed Pattern Trees

Summary: Study WDPTs over relational schemas, identify structural conditions yielding tractable evaluation while WDPTs strictly generalize CQs. Give 2EXPTIME upper bound for equivalence to the tractable fragment, derive FPT evaluation algorithms, and initiate approximation theory. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1651
Venue: PODS
Year: 2015
Pagerank: 7.3921264e-05
Overall Rank: 3,463 | 76.25%
DOI: 10.1145/2745754.2745767

Incoming Non-self Citations Over Time

Authors

1. Pablo Barceló (University of Chile)
2. Reinhard Pichler (Vienna University of Technology)
3. Sebastian Skritek (Vienna University of Technology)

BibTeX Citation

@inproceedings{barcelo_pods15,
        address = {New York, NY, USA},
        series = {{PODS} '15},
        title = {{Efficient Evaluation and Approximation of Well-designed Pattern Trees}},
        url = {https://dl.acm.org/doi/10.1145/2745754.2745767},
        doi = {10.1145/2745754.2745767},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Barceló, Pablo and Pichler, Reinhard and Skritek, Sebastian},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
530	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.0001709169
8,098	Designing a Query Language for RDF: Marrying Open and Closed Worlds	2016	PODS	5.4874656e-05
9,291	Efficiently Enumerating Answers to Ontology-Mediated Queries	2022	PODS	5.2910144e-05
9,933	Semantic Acyclicity Under Constraints	2016	PODS	5.1955087e-05
11,895	The Tractability Frontier of Well-designed SPARQL Queries	2018	PODS	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
673	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00015095061
2,446	Querying Semantic Web Data with SPARQL	2011	PODS	8.5728114e-05
3,556	Static Analysis and Optimization of Semantic Web Queries	2012	PODS	7.3113256e-05
5,832	Containment and Equivalence of Well-Designed SPARQL	2014	PODS	6.0733071e-05
7,028	Semantic Acyclicity on Graph Databases	2013	PODS	5.7228058e-05
9,009	Efficient Approximations of Conjunctive Queries	2012	PODS	5.3335287e-05
12,165	Does Query Evaluation Tractability Help Query Containment?	2014	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,969	Expressive and efficient pattern languages for tree-structured data (extended abstract)	2000	PODS
2	11,895	The Tractability Frontier of Well-designed SPARQL Queries	2018	PODS
3	9,652	Finding a Minimal Tree Pattern Under Neighborhood Constraints	2011	PODS
4	747	Querying Graph Databases	2013	PODS
5	10,044	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS
6	4,495	Queries with Incomplete Answers over Semistructured Data	1999	PODS
7	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS
8	4,077	Similarity-Based Queries	1995	PODS
9	3,556	Static Analysis and Optimization of Semantic Web Queries	2012	PODS
10	7,622	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB