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
he2b1b75ee6ef868b
Venue
SIGMOD
Year
2002
Pagerank
8.0819e-05
Overall Rank
2,733 | 81.63%
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,816 Secure XML Querying with Security Views 2004 SIGMOD 7.9770184e-05
2,881 On the minimization of XPath queries 2003 VLDB 7.9134117e-05
4,066 Rewriting XPath Queries Using Materialized Views 2005 VLDB 6.8221983e-05
5,462 Distributed Query Evaluation with Performance Guarantees 2007 SIGMOD 6.1221387e-05
5,593 Using Partial Evaluation in Distributed Query Evaluation 2006 VLDB 6.073568e-05
6,059 Rewriting Nested XML Queries Using Nested Views 2006 SIGMOD 5.9001613e-05
6,133 Minimization of Tree Pattern Queries with Constraints 2008 SIGMOD 5.8776885e-05
7,768 Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012 VLDB 5.4558207e-05
7,995 Covering Indexes for XML Queries: Bisimulation - Simulation = Negation 2003 VLDB 5.4111901e-05
8,877 Efficient XML-to-SQL Query Translation: Where to Add the Intelligence? 2004 VLDB 5.257159e-05
12,325 Minimization of Tree Pattern Queries 2016 PODS 4.9793485e-05
13,088 Taming XPath Queries by Minimizing Wildcard Steps 2004 VLDB 4.9793485e-05
13,089 The NEXT Framework for Logical XQuery Optimization 2004 VLDB 4.9793485e-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
41 Testing Implications Of Data Dependencies 1979 SIGMOD 0.00045899672
409 Containment and Equivalence for an XPath Fragment [Extended Abstract] 2002 PODS 0.00018868173
699 Query Containment for Conjunctive Queries With Regular Expressions 1998 PODS 0.00014686953
1,096 Minimization of Tree Pattern Queries 2001 SIGMOD 0.00012050482
1,315 DTD Inference for Views of XML Data 2000 PODS 0.00011058412
1,660 On the Decidability of Query Containment under Constraints 1998 PODS 9.9592164e-05
2,241 Querying Network Directories 1999 SIGMOD 8.7708234e-05
4,248 Integrity Constraints for XML 2000 PODS 6.704016e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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