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: 9401
Venue: VLDB
Year: 2004
Pagerank: 5.9488248e-05
Overall Rank: 6,185 | 57.57%
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,268	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.8370676e-05
5,936	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	6.0353909e-05
7,267	Structured Materialized Views for XML Queries	2007	VLDB	5.6597556e-05
8,971	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	5.3420194e-05
9,678	Deciding Well-Definedness of XQuery Fragments	2005	PODS	5.2373357e-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
22	Data Integration: A Theoretical Perspective	2002	PODS	0.00056204792
124	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030950263
309	Optimization of Real Conjunctive Queries	1993	PODS	0.00021768596
395	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00019298983
633	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00015560958
686	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014948634
853	Queries Independent of Updates	1993	VLDB	0.00013587101
884	Mapping Data in Peer-to-Peer Systems: Semantics and Algorithmic Issues	2003	SIGMOD	0.00013419278
953	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012997935
1,068	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00012326498
1,489	Constraint Checking with Partial Information	1994	PODS	0.00010612225
2,268	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.8370676e-05
4,522	Semantic Representations and Query Languages for Or-sets	1993	PODS	6.6466406e-05

Semantically Similar Papers

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