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)

Paper ID: 1689
Venue: PODS
Year: 2016
Pagerank: 5.093636e-05
Overall Rank: 12,030 | 17.47%
DOI: 10.1145/2902251.2902295

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Wojciech Czerwiński (University of Warsaw)
2. Wim Martens (University of Bayreuth)
3. Matthias Niewerth (University of Bayreuth)
4. Paweł Parys (University of Warsaw)

BibTeX Citation

@inproceedings{czerwinski_pods16,
        address = {New York, NY, USA},
        series = {{PODS} '16},
        title = {{Minimization of Tree Pattern Queries}},
        url = {https://dl.acm.org/doi/10.1145/2902251.2902295},
        doi = {10.1145/2902251.2902295},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Czerwiński, Wojciech and Martens, Wim and Niewerth, Matthias and Parys, Paweł},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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
395	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00019298983
1,564	Conjunctive Queries over Trees	2004	PODS	0.00010349456
2,296	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS	8.7908999e-05
2,680	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD	8.267202e-05
2,817	On the minimization of XPath queries	2003	VLDB	8.0945626e-05
3,976	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.9785468e-05
6,005	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD	6.0119945e-05
7,361	Static Analysis of Active XML Systems	2008	PODS	5.6340455e-05
10,044	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS	5.1703259e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,718	Minimizing Conjunctive Regular Path Queries	2025	PODS
2	7,029	Tree-Width and Functional Dependencies in Databases	2008	PODS
3	11,121	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS
4	9,687	Answering Tree Pattern Queries Using Views	2006	VLDB
5	7,622	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB
6	2,680	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD
7	9,652	Finding a Minimal Tree Pattern Under Neighborhood Constraints	2011	PODS
8	10,044	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS
9	6,005	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD
10	1,068	Minimization of Tree Pattern Queries	2001	SIGMOD