Efficient Algorithms for Minimizing Tree Pattern Queries

Summary: TPQ minimization for XML/LDAP graphs via graph simulation; three constraint settings: Case 1 no constraints O(n^2), Case 2 all constraints O(n^4), Case 3 required-child/descendant only O(n^2). Advances prior O(n^4)/O(n^6) bounds; runtime-optimal for Cases 1 and 3. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3358
Venue: SIGMOD
Year: 2002
Pagerank: 7.821865e-05
Overall Rank: 2,956 | 79.44%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Prakash Ramanan

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,947	Secure XML Querying with Security Views	2004	SIGMOD	0.00010000435
3,084	On the minimization of Xpath queries	2003	VLDB	7.6011919e-05
4,568	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.0784118e-05
5,188	Using Partial Evaluation in Distributed Query Evaluation	2006	VLDB	5.6385696e-05
5,317	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD	5.5719038e-05
5,948	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD	5.2602218e-05
6,300	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.1223169e-05
7,584	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	4.7041255e-05
7,763	Covering Indexes for XML Queries: Bisimulation - Simulation = Negation	2003	VLDB	4.6575679e-05
8,493	Efficient XML-to-SQL Query Translation: Where to Add the Intelligence?	2004	VLDB	4.4991066e-05
11,827	Minimization of Tree Pattern Queries	2016	PODS	4.1945683e-05
12,605	Taming XPath Queries by Minimizing Wildcard Steps	2004	VLDB	4.1945683e-05
12,606	The NEXT Framework for Logical XQuery Optimization	2004	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
38	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00075110004
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.000216753
810	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00016428374
882	DTD Inference for Views of XML Data	2000	PODS	0.00015657456
1,235	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00013120483
1,490	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011699154
1,662	Querying Network Directories	1999	SIGMOD	0.00010977682
3,960	Integrity Constraints for XML	2000	PODS	6.5882121e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,397	LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying	2007	VLDB	4.527474e-05
3,610	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB	6.9196208e-05
3,084	On the minimization of Xpath queries	2003	VLDB	7.6011919e-05
7,584	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	4.7041255e-05
2,855	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB	8.0059865e-05
4,625	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.0406081e-05
3,117	Processing Queries on Tree-Structured Data Efficiently	2006	PODS	7.5407318e-05
9,534	Answering Tree Pattern Queries Using Views	2006	VLDB	4.3268303e-05
5,948	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD	5.2602218e-05
1,235	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00013120483