DBScholar

Back to papers

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
3420
Venue
SIGMOD
Year
2002
Pagerank
8.267202e-05
Overall Rank
2,680 | 81.62%
DOI
10.1145/564691.564726

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{ramanan_sigmod02,
        title = {{Efficient Algorithms for Minimizing Tree Pattern Queries}},
        author = {Ramanan, Prakash},
        series = {{SIGMOD} '02},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/564691.564726},
        url = {https://dl.acm.org/doi/10.1145/564691.564726},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank Citing Paper Year Venue Pagerank
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,976 Rewriting XPath Queries Using Materialized Views 2005 VLDB 6.9785468e-05
5,336 Distributed Query Evaluation with Performance Guarantees 2007 SIGMOD 6.2612462e-05
5,458 Using Partial Evaluation in Distributed Query Evaluation 2006 VLDB 6.2115011e-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
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,713 Efficient XML-to-SQL Query Translation: Where to Add the Intelligence? 2004 VLDB 5.3778229e-05
12,030 Minimization of Tree Pattern Queries 2016 PODS 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
Previous Page 1 / 1 Next

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
40 Testing Implications Of Data Dependencies 1979 SIGMOD 0.00046918506
395 Containment and Equivalence for an XPath Fragment [Extended Abstract] 2002 PODS 0.00019298983
686 Query Containment for Conjunctive Queries With Regular Expressions 1998 PODS 0.00014948634
1,068 Minimization of Tree Pattern Queries 2001 SIGMOD 0.00012326498
1,290 DTD Inference for Views of XML Data 2000 PODS 0.00011312135
1,630 On the Decidability of Query Containment under Constraints 1998 PODS 0.00010180625
2,201 Querying Network Directories 1999 SIGMOD 8.9653966e-05
4,167 Integrity Constraints for XML 2000 PODS 6.8578387e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 8,422 LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying 2007 VLDB
2 3,167 From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery 2003 VLDB
3 2,817 On the minimization of XPath queries 2003 VLDB
4 7,622 Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012 VLDB
5 2,625 Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach 2003 VLDB
6 4,537 On Testing Satisfiability of Tree Pattern Queries 2004 VLDB
7 4,107 Processing Queries on Tree-Structured Data Efficiently 2006 PODS
8 9,687 Answering Tree Pattern Queries Using Views 2006 VLDB
9 6,005 Minimization of Tree Pattern Queries with Constraints 2008 SIGMOD
10 1,068 Minimization of Tree Pattern Queries 2001 SIGMOD