Containment of Nested XML Queries

Summary: Containment of nested XML queries: poly-time for fanout 1; coNP-hard for general fanout with nesting depth 2. Fixed nesting depth yields coNP-complete containment; extensions: union, arithmetic; descendant edges, negation; heuristics speed checks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hf5e6a0997a5c8feb
Venue: VLDB
Year: 2004
Pagerank: 5.8153622e-05
Overall Rank: 6,319 | 57.52%
DOI: 10.1016/B978-012088469-8.50015-2

Incoming Non-self Citations Over Time

Authors

1. Xin Dong (University of Washington)
2. Alon Y. Halevy (University of Washington)
3. Igor Tatarinov (University of Washington)

BibTeX Citation

@article{dong_vldb04,
        title = {{Containment of Nested XML Queries}},
        author = {Dong, Xin and Halevy, Alon Y. and Tatarinov, Igor},
        journal = {PVLDB},
        series = {{VLDB} '04},
        doi = {10.1016/B978-012088469-8.50015-2},
        url = {https://doi.org/10.1016/B978-012088469-8.50015-2},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,321	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.6413639e-05
6,059	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.9001613e-05
7,418	Structured Materialized Views for XML Queries	2007	VLDB	5.5327659e-05
9,135	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	5.2224867e-05
9,851	Deciding Well-Definedness of XQuery Fragments	2005	PODS	5.1198285e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
24	Data Integration: A Theoretical Perspective	2002	PODS	0.00055043581
130	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030320165
310	Optimization of Real Conjunctive Queries	1993	PODS	0.00021374145
409	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00018868173
642	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00015243164
699	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014686953
875	Queries Independent of Updates	1993	VLDB	0.00013316445
899	Mapping Data in Peer-to-Peer Systems: Semantics and Algorithmic Issues	2003	SIGMOD	0.00013186809
979	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012729663
1,096	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00012050482
1,521	Constraint Checking with Partial Information	1994	PODS	0.00010379636
2,321	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.6413639e-05
4,619	Semantic Representations and Query Languages for Or-sets	1993	PODS	6.4993923e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,514	View-Based Query Containment	2003	PODS
2	1,818	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS
3	1,275	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS
4	3,095	Query Containment for Data Integration Systems	2000	PODS
5	1,599	Conjunctive Queries over Trees	2004	PODS
6	166	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD
7	8,325	Containment Join Size Estimation: Models and Methods	2003	SIGMOD
8	12,845	Relational-Style XML Query	2008	SIGMOD
9	4,596	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS
10	409	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS