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: 9210
Venue: VLDB
Year: 2004
Pagerank: 5.1255418e-05
Overall Rank: 6,294 | 56.22%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,479	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.6909119e-05
6,300	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.1223169e-05
7,298	Structured Materialized Views for XML Queries	2007	VLDB	4.770411e-05
8,704	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	4.4647149e-05
9,530	Deciding Well-Definedness of XQuery Fragments	2005	PODS	4.3290808e-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
48	Data Integration: A Theoretical Perspective	2002	PODS	0.00069720859
114	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00046339735
335	Optimization of Real Conjunctive Queries	1993	PODS	0.00027036073
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.000216753
581	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00019767772
810	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00016428374
839	Mapping Data in Peer-to-Peer Systems: Semantics and Algorithmic Issues	2003	SIGMOD	0.00016079422
909	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00015428222
938	Queries Independent of Updates	1993	VLDB	0.00015197786
1,235	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00013120483
1,578	Constraint Checking with Partial Information	1994	PODS	0.00011284233
2,479	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.6909119e-05
4,699	Semantic Representations and Query Languages for Or-sets	1993	PODS	5.9885891e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,553	View-Based Query Containment	2003	PODS	6.091702e-05
1,952	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.9677831e-05
1,522	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS	0.0001153051
3,168	Query Containment for Data Integration Systems	2000	PODS	7.4508875e-05
1,663	Conjunctive Queries over Trees	2004	PODS	0.00010977096
193	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00035610321
7,827	Containment Join Size Estimation: Models and Methods	2003	SIGMOD	4.6411831e-05
12,362	Relational-Style XML Query	2008	SIGMOD	4.1945683e-05
4,366	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS	6.2538592e-05
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.000216753