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: 3356
Venue: SIGMOD
Year: 2001
Pagerank: 0.00012326498
Overall Rank: 1,068 | 92.68%
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,317	MARS: A System for Publishing XML from Mixed and Redundant Storage	2003	VLDB	0.00011179293
1,916	XPath Satisfiability in the Presence of DTDs	2005	PODS	9.4878711e-05
2,268	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.8370676e-05
2,680	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD	8.267202e-05
2,757	Secure XML Querying with Security Views	2004	SIGMOD	8.1601016e-05
2,817	On the minimization of XPath queries	2003	VLDB	8.0945626e-05
3,643	Tree Pattern Aggregation for Scalable XML Data Dissemination	2002	VLDB	7.2312164e-05
3,976	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.9785468e-05
4,537	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.6417534e-05
5,298	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD	6.2770047e-05
5,731	Secure XML Publishing without Information Leakage in the Presence of Data Inference	2004	VLDB	6.106721e-05
5,936	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	6.0353909e-05
6,005	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD	6.0119945e-05
6,185	Containment of Nested XML Queries	2004	VLDB	5.9488248e-05
7,202	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	5.6755422e-05
7,622	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	5.5806644e-05
7,836	Covering Indexes for XML Queries: Bisimulation - Simulation = Negation	2003	VLDB	5.5353696e-05
8,066	Semantic Query Optimization for XQuery over XML Streams	2005	VLDB	5.4942177e-05
8,713	Efficient XML-to-SQL Query Translation: Where to Add the Intelligence?	2004	VLDB	5.3778229e-05
8,941	Client-Based Access Control Management for XML documents	2004	VLDB	5.3483178e-05
9,687	Answering Tree Pattern Queries Using Views	2006	VLDB	5.2351299e-05
12,780	Semantic Query Optimization in an Automata-Algebra Combined XQuery Engine over XML Streams	2004	VLDB	5.093636e-05
12,797	Answering XPath Queries over Networks by Sending Minimal Views	2004	VLDB	5.093636e-05
12,798	Taming XPath Queries by Minimizing Wildcard Steps	2004	VLDB	5.093636e-05
12,799	The NEXT Framework for Logical XQuery Optimization	2004	VLDB	5.093636e-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,652	Finding a Minimal Tree Pattern Under Neighborhood Constraints	2011	PODS
2	3,167	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB
3	4,107	Processing Queries on Tree-Structured Data Efficiently	2006	PODS
4	9,687	Answering Tree Pattern Queries Using Views	2006	VLDB
5	8,422	LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying	2007	VLDB
6	10,044	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS
7	5,848	Efficient Mining of XML Query Patterns for Caching	2003	VLDB
8	12,030	Minimization of Tree Pattern Queries	2016	PODS
9	6,005	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD
10	2,680	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD