Minimization of Tree Pattern Queries

Summary: CIM: polynomial-time, constraint-independent minimization of tree-pattern queries; a node is redundant only if its children are, and elimination order immaterial. Under ICs, ACIM yields a unique minimal query; CDM speeds minimization by propagating labels to prune local redundancies. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h06582dfac3723136
Venue: SIGMOD
Year: 2001
Pagerank: 0.00012044781
Overall Rank: 1,096 | 92.64%
DOI: 10.1145/375663.375730

Incoming Non-self Citations Over Time

Authors

1. Sihem Amer-Yahia (AT&T)
2. SungRan Cho (Stevens Institute of Technology)
3. Laks V. S. Lakshmanan (Concordia University; Indian Institute of Technology Mumbai)
4. Divesh Srivastava (AT&T)

BibTeX Citation

@inproceedings{ameryahia_sigmod01,
        title = {{Minimization of Tree Pattern Queries}},
        author = {Amer-Yahia, Sihem and Cho, SungRan and Lakshmanan, Laks V. S. and Srivastava, Divesh},
        series = {{SIGMOD} '01},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/375663.375730},
        url = {https://dl.acm.org/doi/10.1145/375663.375730},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 25 of 25 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,353	MARS: A System for Publishing XML from Mixed and Redundant Storage	2003	VLDB	0.00010925367
1,978	XPath Satisfiability in the Presence of DTDs	2005	PODS	9.275331e-05
2,323	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.637314e-05
2,733	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD	8.0780747e-05
2,817	Secure XML Querying with Security Views	2004	SIGMOD	7.9732421e-05
2,883	On the minimization of XPath queries	2003	VLDB	7.9096688e-05
3,732	Tree Pattern Aggregation for Scalable XML Data Dissemination	2002	VLDB	7.0658485e-05
4,068	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.8189688e-05
4,639	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.4900386e-05
5,425	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD	6.1332823e-05
5,857	Secure XML Publishing without Information Leakage in the Presence of Data Inference	2004	VLDB	5.9670114e-05
6,060	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.8973683e-05
6,135	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD	5.8749061e-05
6,323	Containment of Nested XML Queries	2004	VLDB	5.8126093e-05
7,342	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	5.5464639e-05
7,777	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	5.4532403e-05
8,000	Covering Indexes for XML Queries: Bisimulation - Simulation = Negation	2003	VLDB	5.4086285e-05
8,243	Semantic Query Optimization for XQuery over XML Streams	2005	VLDB	5.3683997e-05
8,886	Efficient XML-to-SQL Query Translation: Where to Add the Intelligence?	2004	VLDB	5.2546704e-05
9,114	Client-Based Access Control Management for XML documents	2004	VLDB	5.2258409e-05
9,869	Answering Tree Pattern Queries Using Views	2006	VLDB	5.115245e-05
13,076	Semantic Query Optimization in an Automata-Algebra Combined XQuery Engine over XML Streams	2004	VLDB	4.9769913e-05
13,093	Answering XPath Queries over Networks by Sending Minimal Views	2004	VLDB	4.9769913e-05
13,094	Taming XPath Queries by Minimizing Wildcard Steps	2004	VLDB	4.9769913e-05
13,095	The NEXT Framework for Logical XQuery Optimization	2004	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,836	Finding a Minimal Tree Pattern Under Neighborhood Constraints	2011	PODS
2	3,235	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB
3	4,189	Processing Queries on Tree-Structured Data Efficiently	2006	PODS
4	9,869	Answering Tree Pattern Queries Using Views	2006	VLDB
5	8,555	LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying	2007	VLDB
6	10,243	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS
7	5,971	Efficient Mining of XML Query Patterns for Caching	2003	VLDB
8	12,331	Minimization of Tree Pattern Queries	2016	PODS
9	6,135	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD
10	2,733	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD