DBScholar

Back to papers

The (Almost) Complete Guide to Tree Pattern Containment

Summary: Comprehensive reclassification of tree-pattern query containment/validity/satisfiability with and without schema, unifying prior results and resolving long-open complexity gaps via novel automata/reduction techniques. Pinpoints exact tractability and hardness boundaries for patterns on trees (and graphs). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1650
Venue
PODS
Year
2015
Pagerank
5.1703259e-05
Overall Rank
10,044 | 31.09%
DOI
10.1145/2745754.2745766

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{czerwinski_pods15,
        address = {New York, NY, USA},
        series = {{PODS} '15},
        title = {{The (Almost) Complete Guide to Tree Pattern Containment}},
        url = {https://dl.acm.org/doi/10.1145/2745754.2745766},
        doi = {10.1145/2745754.2745766},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Czerwinski, Wojciech and Martens, Wim and Parys, Pawel and Przybylko, Marcin},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank Citing Paper Year Venue Pagerank
9,811 Schema-Based Query Optimisation for Graph Databases 2025 SIGMOD 5.214913e-05
12,030 Minimization of Tree Pattern Queries 2016 PODS 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
395 Containment and Equivalence for an XPath Fragment [Extended Abstract] 2002 PODS 0.00019298983
747 Querying Graph Databases 2013 PODS 0.00014400452
1,564 Conjunctive Queries over Trees 2004 PODS 0.00010349456
4,504 The Complexity of Query Containment in Expressive Fragments of XPath 2.0 2007 PODS 6.6592957e-05
7,622 Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012 VLDB 5.5806644e-05
8,480 Discovering XSD Keys from XML Data 2013 SIGMOD 5.4167813e-05
Previous Page 1 / 1 Next

Semantically Similar Papers