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: 3359
Venue: SIGMOD
Year: 2002
Pagerank: 7.8143379e-05
Overall Rank: 2,957 | 79.46%
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,951	Secure XML Querying with Security Views	2004	SIGMOD	9.9907874e-05
3,089	On the minimization of Xpath queries	2003	VLDB	7.5938563e-05
4,568	Rewriting XPath Queries Using Materialized Views	2005	VLDB	6.0725918e-05
5,190	Using Partial Evaluation in Distributed Query Evaluation	2006	VLDB	5.633429e-05
5,324	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD	5.5668659e-05
5,950	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD	5.2551296e-05
6,300	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.1174095e-05
7,588	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	4.6996269e-05
7,763	Covering Indexes for XML Queries: Bisimulation - Simulation = Negation	2003	VLDB	4.6531059e-05
8,492	Efficient XML-to-SQL Query Translation: Where to Add the Intelligence?	2004	VLDB	4.4947925e-05
11,835	Minimization of Tree Pattern Queries	2016	PODS	4.1905499e-05
12,614	Taming XPath Queries by Minimizing Wildcard Steps	2004	VLDB	4.1905499e-05
12,615	The NEXT Framework for Logical XQuery Optimization	2004	VLDB	4.1905499e-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.0007528369
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00021654356
808	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.000164132
880	DTD Inference for Views of XML Data	2000	PODS	0.00015642282
1,236	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00013107769
1,489	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011687823
1,658	Querying Network Directories	1999	SIGMOD	0.00010970782
3,962	Integrity Constraints for XML	2000	PODS	6.581926e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,374	LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying	2007	VLDB	4.5282277e-05
3,613	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB	6.9139845e-05
3,089	On the minimization of Xpath queries	2003	VLDB	7.5938563e-05
7,588	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	4.6996269e-05
2,862	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB	7.9982917e-05
4,624	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.034764e-05
3,115	Processing Queries on Tree-Structured Data Efficiently	2006	PODS	7.5414053e-05
9,535	Answering Tree Pattern Queries Using Views	2006	VLDB	4.3226836e-05
5,950	Minimization of Tree Pattern Queries with Constraints	2008	SIGMOD	5.2551296e-05
1,236	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00013107769