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: 9211
Venue: VLDB
Year: 2004
Pagerank: 5.1206121e-05
Overall Rank: 6,293 | 56.27%
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,480	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.682497e-05
6,300	Rewriting Nested XML Queries Using Nested Views	2006	SIGMOD	5.1174095e-05
7,295	Structured Materialized Views for XML Queries	2007	VLDB	4.7658356e-05
8,699	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	4.4604187e-05
9,531	Deciding Well-Definedness of XQuery Fragments	2005	PODS	4.3249319e-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
47	Data Integration: A Theoretical Perspective	2002	PODS	0.00069691761
115	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00046301137
335	Optimization of Real Conjunctive Queries	1993	PODS	0.00027012705
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00021654356
582	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00019753367
808	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.000164132
836	Mapping Data in Peer-to-Peer Systems: Semantics and Algorithmic Issues	2003	SIGMOD	0.00016066053
907	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00015417107
937	Queries Independent of Updates	1993	VLDB	0.00015194231
1,236	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00013107769
1,579	Constraint Checking with Partial Information	1994	PODS	0.00011273105
2,480	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.682497e-05
4,699	Semantic Representations and Query Languages for Or-sets	1993	PODS	5.98279e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,552	View-Based Query Containment	2003	PODS	6.0856349e-05
1,959	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.958725e-05
1,520	The Containment Problem for Real Conjunctive Queries with Inequalities	2006	PODS	0.00011524911
3,174	Query Containment for Data Integration Systems	2000	PODS	7.444226e-05
1,662	Conjunctive Queries over Trees	2004	PODS	0.00010966423
193	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00035591171
7,833	Containment Join Size Estimation: Models and Methods	2003	SIGMOD	4.6367487e-05
12,370	Relational-Style XML Query	2008	SIGMOD	4.1905499e-05
4,362	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS	6.2478748e-05
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00021654356