DBScholar

Back to papers

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
h2cabff98736b15ab
Venue
PODS
Year
2015
Pagerank
7.2274159e-05
Overall Rank
3,531 | 76.27%
DOI
10.1145/2745754.2745767

Incoming Non-self Citations Over Time

Authors

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
540 An Analytical Study of Large SPARQL Query Logs 2018 VLDB 0.00016726545
8,270 Designing a Query Language for RDF: Marrying Open and Closed Worlds 2016 PODS 5.364379e-05
9,466 Efficiently Enumerating Answers to Ontology-Mediated Queries 2022 PODS 5.1722982e-05
10,115 Semantic Acyclicity Under Constraints 2016 PODS 5.0789354e-05
12,195 The Tractability Frontier of Well-designed SPARQL Queries 2018 PODS 4.9793485e-05
Previous Page 1 / 1 Next

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
684 Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants 2007 PODS 0.00014798237
2,483 Querying Semantic Web Data with SPARQL 2011 PODS 8.3997473e-05
3,633 Static Analysis and Optimization of Semantic Web Queries 2012 PODS 7.1484281e-05
5,948 Containment and Equivalence of Well-Designed SPARQL 2014 PODS 5.9370407e-05
7,140 Semantic Acyclicity on Graph Databases 2013 PODS 5.6005794e-05
9,169 Efficient Approximations of Conjunctive Queries 2012 PODS 5.2141412e-05
12,456 Does Query Evaluation Tractability Help Query Containment? 2014 PODS 4.9793485e-05
Previous Page 1 / 1 Next

Semantically Similar Papers