Minimization of Tree Pattern Queries
Summary: Proves minimization of tree-pattern queries (child/descendant, labels, wildcards) is Sigma^P_2-complete, resolving an open problem of Flesca et al. (2003). Disproves the M-NR conjecture by showing minimality cannot be achieved by node deletion and gives a gadget reduction. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Wojciech Czerwiński
- 2. Wim Martens
- 3. Matthias Niewerth
- 4. Paweł Parys
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 9 of 9 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 499 | Containment and Equivalence for an XPath Fragment [Extended Abstract] | 2002 | PODS | 0.000216753 |
| 1,663 | Conjunctive Queries over Trees | 2004 | PODS | 0.00010977096 |
| 2,398 | Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract) | 1992 | PODS | 8.8973978e-05 |
| 2,956 | Efficient Algorithms for Minimizing Tree Pattern Queries | 2002 | SIGMOD | 7.821865e-05 |
| 3,084 | On the minimization of Xpath queries | 2003 | VLDB | 7.6011919e-05 |
| 4,568 | Rewriting XPath Queries Using Materialized Views | 2005 | VLDB | 6.0784118e-05 |
| 5,948 | Minimization of Tree Pattern Queries with Constraints | 2008 | SIGMOD | 5.2602218e-05 |
| 7,291 | Static Analysis of Active XML Systems | 2008 | PODS | 4.7741469e-05 |
| 9,890 | The (Almost) Complete Guide to Tree Pattern Containment | 2015 | PODS | 4.2617199e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,349 | Minimizing Conjunctive Regular Path Queries | 2025 | PODS | 4.1945683e-05 |
| 6,949 | Tree-Width and Functional Dependencies in Databases | 2008 | PODS | 4.8898337e-05 |
| 10,899 | Consistent Query Answering for Primary Keys on Rooted Tree Queries | 2024 | PODS | 4.1945683e-05 |
| 9,534 | Answering Tree Pattern Queries Using Views | 2006 | VLDB | 4.3268303e-05 |
| 7,584 | Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data | 2012 | VLDB | 4.7041255e-05 |
| 2,956 | Efficient Algorithms for Minimizing Tree Pattern Queries | 2002 | SIGMOD | 7.821865e-05 |
| 9,441 | Finding a Minimal Tree Pattern Under Neighborhood Constraints | 2011 | PODS | 4.3415167e-05 |
| 9,890 | The (Almost) Complete Guide to Tree Pattern Containment | 2015 | PODS | 4.2617199e-05 |
| 5,948 | Minimization of Tree Pattern Queries with Constraints | 2008 | SIGMOD | 5.2602218e-05 |
| 1,235 | Minimization of Tree Pattern Queries | 2001 | SIGMOD | 0.00013120483 |