Minimization of Tree Pattern Queries with Constraints

Summary: Minimization of TPQs under FBST-constraints, extending FT-, backward-, and sibling-constraints beyond prior work. Algorithms compute a single minimal TPQ and enumerate all minimal queries; faster FT-constraint minimization; experimental validation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: he844685a1ad8d4c5
Venue: SIGMOD
Year: 2008
Pagerank: 5.8749061e-05
Overall Rank: 6,135 | 58.77%
DOI: 10.1145/1376616.1376678

Incoming Non-self Citations Over Time

Authors

1. Ding Chen (National University of Singapore)
2. Chee-Yong Chan (National University of Singapore)

BibTeX Citation

@inproceedings{chen_sigmod08,
        title = {{Minimization of Tree Pattern Queries with Constraints}},
        author = {Chen, Ding and Chan, Chee-Yong},
        series = {{SIGMOD} '08},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1376616.1376678},
        url = {https://dl.acm.org/doi/10.1145/1376616.1376678},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,606	Capturing Topology in Graph Pattern Matching	2012	VLDB	6.0667077e-05
7,777	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	5.4532403e-05
12,331	Minimization of Tree Pattern Queries	2016	PODS	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
409	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00018859247
1,096	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00012044781
2,733	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD	8.0780747e-05
2,883	On the minimization of XPath queries	2003	VLDB	7.9096688e-05
3,244	Inference of Concise DTDs from XML Data	2006	VLDB	7.4956321e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,851	Relational-Style XML Query	2008	SIGMOD
2	9,836	Finding a Minimal Tree Pattern Under Neighborhood Constraints	2011	PODS
3	12,331	Minimization of Tree Pattern Queries	2016	PODS
4	9,869	Answering Tree Pattern Queries Using Views	2006	VLDB
5	7,777	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB
6	4,639	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB
7	3,235	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB
8	2,883	On the minimization of XPath queries	2003	VLDB
9	2,733	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD
10	1,096	Minimization of Tree Pattern Queries	2001	SIGMOD