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.8776885e-05
Overall Rank: 6,133 | 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,605	Capturing Topology in Graph Pattern Matching	2012	VLDB	6.0695806e-05
7,768	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	5.4558207e-05
12,325	Minimization of Tree Pattern Queries	2016	PODS	4.9793485e-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.00018868173
1,096	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00012050482
2,733	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD	8.0819e-05
2,881	On the minimization of XPath queries	2003	VLDB	7.9134117e-05
3,242	Inference of Concise DTDs from XML Data	2006	VLDB	7.4991762e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,845	Relational-Style XML Query	2008	SIGMOD
2	9,829	Finding a Minimal Tree Pattern Under Neighborhood Constraints	2011	PODS
3	12,325	Minimization of Tree Pattern Queries	2016	PODS
4	9,862	Answering Tree Pattern Queries Using Views	2006	VLDB
5	7,768	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB
6	4,636	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB
7	3,233	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB
8	2,881	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