The Complexity of Query Containment in Expressive Fragments of XPath 2.0

Summary: Complexity map for CoreXPath+{intersection,equality,complementation,for‑loops,TC}: cases range EXPTIME, 2‑EXPTIME, to non‑elementary. Intersection typically adds one exponential; equality/TC usually inert (TC makes downward+intersection EXPSPACE→2‑EXPTIME); complementation/for‑loops cause non‑elementary; results extend to DTDs and satisfiability. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hbdd5598c2f577f94
Venue: PODS
Year: 2007
Pagerank: 6.5098871e-05
Overall Rank: 4,596 | 69.11%
DOI: 10.1145/1265530.1265541

Incoming Non-self Citations Over Time

Authors

1. Balder ten Cate (University of Amsterdam)
2. Carsten Lutz (Technical University of Dresden)

BibTeX Citation

@inproceedings{cate_pods07,
        address = {New York, NY, USA},
        series = {{PODS} '07},
        title = {{The Complexity of Query Containment in Expressive Fragments of XPath 2.0}},
        url = {https://dl.acm.org/doi/10.1145/1265530.1265541},
        doi = {10.1145/1265530.1265541},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cate, Balder ten and Lutz, Carsten},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,740	High-Performance Complex Event Processing over XML Streams	2012	SIGMOD	6.4435709e-05
6,571	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.7457654e-05
9,422	Decidable XPath Fragments in the Real World	2019	PODS	5.1798389e-05
10,237	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS	5.0543689e-05
12,656	The Complexity of Text-Preserving XML Transformations	2011	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
409	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00018868173
1,599	Conjunctive Queries over Trees	2004	PODS	0.00010117703
1,976	XPath Satisfiability in the Presence of DTDs	2005	PODS	9.2797174e-05
3,795	The Expressivity of XPath with Transitive Closure*	2006	PODS	7.0167646e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,881	On the minimization of XPath queries	2003	VLDB
2	1,599	Conjunctive Queries over Trees	2004	PODS
3	6,319	Containment of Nested XML Queries	2004	VLDB
4	12,824	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
5	6,571	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS
6	3,795	The Expressivity of XPath with Transitive Closure*	2006	PODS
7	9,422	Decidable XPath Fragments in the Real World	2019	PODS
8	1,976	XPath Satisfiability in the Presence of DTDs	2005	PODS
9	2,177	The Complexity of XPath Query Evaluation	2003	PODS
10	409	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS