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)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 690 | An Analytical Study of Large SPARQL Query Logs | 2018 | VLDB | 0.00018099792 |
| 8,995 | Efficiently Enumerating Answers to Ontology-Mediated Queries | 2022 | PODS | 4.412512e-05 |
| 11,828 | Designing a Query Language for RDF: Marrying Open and Closed Worlds | 2016 | PODS | 4.1945683e-05 |
| 11,829 | Semantic Acyclicity Under Constraints | 2016 | PODS | 4.1945683e-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 |
|---|---|---|---|---|
| 626 | Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants | 2007 | PODS | 0.00018973823 |
| 2,304 | Querying Semantic Web Data with SPARQL | 2011 | PODS | 9.0648775e-05 |
| 4,251 | Static Analysis and Optimization of Semantic Web Queries | 2012 | PODS | 6.3235328e-05 |
| 6,948 | Semantic Acyclicity on Graph Databases | 2013 | PODS | 4.8898337e-05 |
| 7,758 | Containment and Equivalence of Well-Designed SPARQL | 2014 | PODS | 4.6598957e-05 |
| 8,851 | Efficient Approximations of Conjunctive Queries | 2012 | PODS | 4.4363908e-05 |
| 11,967 | Does Query Evaluation Tractability Help Query Containment? | 2014 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,948 | Semantic Acyclicity on Graph Databases | 2013 | PODS | 4.8898337e-05 |
| 2,584 | Expressive and efficient pattern languages for tree-structured data (extended abstract) | 2000 | PODS | 8.4948053e-05 |
| 9,441 | Finding a Minimal Tree Pattern Under Neighborhood Constraints | 2011 | PODS | 4.3415167e-05 |
| 1,037 | Querying Graph Databases | 2013 | PODS | 0.00014502493 |
| 9,890 | The (Almost) Complete Guide to Tree Pattern Containment | 2015 | PODS | 4.2617199e-05 |
| 3,681 | Queries with Incomplete Answers over Semistructured Data | 1999 | PODS | 6.8492288e-05 |
| 8,851 | Efficient Approximations of Conjunctive Queries | 2012 | PODS | 4.4363908e-05 |
| 4,064 | Similarity-Based Queries | 1995 | PODS | 6.4820797e-05 |
| 4,251 | Static Analysis and Optimization of Semantic Web Queries | 2012 | PODS | 6.3235328e-05 |
| 7,584 | Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data | 2012 | VLDB | 4.7041255e-05 |