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.00021654356 |
| 1,662 | Conjunctive Queries over Trees | 2004 | PODS | 0.00010966423 |
| 2,396 | Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract) | 1992 | PODS | 8.8892825e-05 |
| 2,957 | Efficient Algorithms for Minimizing Tree Pattern Queries | 2002 | SIGMOD | 7.8143379e-05 |
| 3,089 | On the minimization of Xpath queries | 2003 | VLDB | 7.5938563e-05 |
| 4,568 | Rewriting XPath Queries Using Materialized Views | 2005 | VLDB | 6.0725918e-05 |
| 5,950 | Minimization of Tree Pattern Queries with Constraints | 2008 | SIGMOD | 5.2551296e-05 |
| 7,288 | Static Analysis of Active XML Systems | 2008 | PODS | 4.7695781e-05 |
| 9,889 | The (Almost) Complete Guide to Tree Pattern Containment | 2015 | PODS | 4.2576366e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,361 | Minimizing Conjunctive Regular Path Queries | 2025 | PODS | 4.1905499e-05 |
| 6,946 | Tree-Width and Functional Dependencies in Databases | 2008 | PODS | 4.8874695e-05 |
| 10,903 | Consistent Query Answering for Primary Keys on Rooted Tree Queries | 2024 | PODS | 4.1905499e-05 |
| 9,535 | Answering Tree Pattern Queries Using Views | 2006 | VLDB | 4.3226836e-05 |
| 7,588 | Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data | 2012 | VLDB | 4.6996269e-05 |
| 2,957 | Efficient Algorithms for Minimizing Tree Pattern Queries | 2002 | SIGMOD | 7.8143379e-05 |
| 9,446 | Finding a Minimal Tree Pattern Under Neighborhood Constraints | 2011 | PODS | 4.3373542e-05 |
| 9,889 | The (Almost) Complete Guide to Tree Pattern Containment | 2015 | PODS | 4.2576366e-05 |
| 5,950 | Minimization of Tree Pattern Queries with Constraints | 2008 | SIGMOD | 5.2551296e-05 |
| 1,236 | Minimization of Tree Pattern Queries | 2001 | SIGMOD | 0.00013107769 |