From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery

Summary: Introduces generalized tree patterns (GTPs) to represent and evaluate whole XQuery expressions, beyond individual XPath matches, including joins, quantifiers, grouping, aggregation, and nesting. Schema-driven GTP simplification yields substantially faster plans than navigation and straightforward evaluation in TIMBER. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 9169
Venue: VLDB
Year: 2003
Pagerank: 7.6749991e-05
Overall Rank: 3,167 | 78.28%
DOI: 10.1016/B978-012722442-8/50029-X

Incoming Non-self Citations Over Time

Authors

1. Zhimin Chen (University of British Columbia)
2. H.V. Jagadish (University of Michigan)
3. Laks V. S. Lakshmanan (University of British Columbia)
4. Stelios Paparizos (University of Michigan)

BibTeX Citation

@article{chen_vldb03,
        title = {{From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery}},
        author = {Chen, Zhimin and Jagadish, H.V. and Lakshmanan, Laks V. S. and Paparizos, Stelios},
        journal = {PVLDB},
        series = {{VLDB} '03},
        volume = {29},
        pages = {237--248},
        doi = {10.1016/B978-012722442-8/50029-X},
        url = {https://doi.org/10.1016/B978-012722442-8/50029-X},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,744	System RX: One Part Relational, One Part XML	2005	SIGMOD	9.868841e-05
3,180	Approximate XML Query Answers	2004	SIGMOD	7.6599179e-05
3,917	Tree Logical Classes for Efficient Evaluation of XQuery	2004	SIGMOD	7.0182992e-05
4,066	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB	6.9298871e-05
4,576	Efficient Evaluation of XQuery over Streaming Data	2005	VLDB	6.6216442e-05
5,772	Pattern tree algebras: sets or sequences?	2005	VLDB	6.0930389e-05
6,557	Semistructured Models, Queries and Algebras in the Big Data Era	2016	SIGMOD	5.8401127e-05
7,267	Structured Materialized Views for XML Queries	2007	VLDB	5.6597556e-05
7,622	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	5.5806644e-05
8,066	Semantic Query Optimization for XQuery over XML Streams	2005	VLDB	5.4942177e-05
8,333	Efficient Keyword Search over Virtual XML Views	2007	VLDB	5.4519621e-05
12,559	Grouping and Optimization of XPath Expressions in DB2 pureXML	2008	SIGMOD	5.093636e-05
12,583	Towards a Physical XML independent XQuery/SQL/XML Engine	2008	VLDB	5.093636e-05
12,799	The NEXT Framework for Logical XQuery Optimization	2004	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
137	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00029877792
163	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027839792
175	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00027226333
362	Storing and Querying Ordered XML Using a Relational Database System	2002	SIGMOD	0.00020125068
395	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00019298983
1,204	A Comprehensive XQuery to SQL Translation using Dynamic Interval Encoding	2003	SIGMOD	0.00011664562

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,066	Semantic Query Optimization for XQuery over XML Streams	2005	VLDB
2	9,687	Answering Tree Pattern Queries Using Views	2006	VLDB
3	4,066	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB
4	5,772	Pattern tree algebras: sets or sequences?	2005	VLDB
5	3,129	Structure and Value Synopses for XML Data Graphs	2002	VLDB
6	7,622	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB
7	4,576	Efficient Evaluation of XQuery over Streaming Data	2005	VLDB
8	9,338	Tree-Pattern Queries on a Lightweight XML Processor	2005	VLDB
9	3,917	Tree Logical Classes for Efficient Evaluation of XQuery	2004	SIGMOD
10	4,537	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB