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: 4081
Venue: SIGMOD
Year: 2008
Pagerank: 6.0119945e-05
Overall Rank: 6,005 | 58.81%
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,484	Capturing Topology in Graph Pattern Matching	2012	VLDB	6.2018052e-05
7,622	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	5.5806644e-05
12,030	Minimization of Tree Pattern Queries	2016	PODS	5.093636e-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
395	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00019298983
1,068	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00012326498
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,185	Inference of Concise DTDs from XML Data	2006	VLDB	7.6567423e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,555	Relational-Style XML Query	2008	SIGMOD
2	9,652	Finding a Minimal Tree Pattern Under Neighborhood Constraints	2011	PODS
3	12,030	Minimization of Tree Pattern Queries	2016	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	3,167	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB
7	4,537	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB
8	2,817	On the minimization of XPath queries	2003	VLDB
9	2,680	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD
10	1,068	Minimization of Tree Pattern Queries	2001	SIGMOD