On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values

Summary: Tight combined-complexity for recursion-free functional queries on complex values: monad algebra with atomic equality is TA[2^O(n),O(n)]-complete; its monotone fragment is NEXPTIME-complete; deep equality admits TA lower and EXPSPACE upper bounds. Core XQuery (child-only) is expressively equivalent to list monad algebra and inherits these combined complexities, while fixed-query data complexity lies in TC0. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1343
Venue: PODS
Year: 2005
Pagerank: 6.0488752e-05
Overall Rank: 4,611 | 67.93%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Christoph Koch

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,626	Behavioral Simulations in MapReduce	2010	VLDB	6.9047458e-05
6,299	Incremental View Maintenance For Collection Programming	2016	PODS	5.1225782e-05
7,238	A Crash Course on Database Queries	2007	PODS	4.7928464e-05
7,248	Positive Higher-Order Queries	2010	PODS	4.7902631e-05
7,454	The GCX System: Dynamic Buffer Minimization in Streaming XQuery Evaluation	2007	VLDB	4.7263711e-05
11,156	Synthesizing Nested Relational Queries from Implicit Specifications	2023	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
97	Remarks on the Algebra of Non First Normal Form Relations	1982	PODS	0.0005080702
485	A New Approach to Database Logic	1984	PODS	0.00022085103
713	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00017731096
1,123	A Transducer-Based XML Query Processor	2002	VLDB	0.00013849322
1,264	Projecting XML Documents	2003	VLDB	0.00012976407
1,793	The BEA/XQRL Streaming XQuery Processor	2003	VLDB	0.00010533088
1,848	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	0.00010330772
2,248	The Complexity of XPath Query Evaluation	2003	PODS	9.2038466e-05
2,546	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS	8.5701687e-05
2,553	Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions	1988	PODS	8.5500139e-05
3,040	Tractable Query Languages for Complex Object Databases	1991	PODS	7.6707607e-05
3,189	On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions	1989	SIGMOD	7.4116834e-05
3,925	Schema-based Scheduling of Event Processors and Buffer Minimization for Queries on Structured Data Streams	2004	VLDB	6.6260709e-05
5,503	Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract)	2000	PODS	5.4738619e-05
5,974	A Query Language for NC	1994	PODS	5.246329e-05
6,794	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	4.9244886e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,847	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB	4.1945683e-05
9,530	Deciding Well-Definedness of XQuery Fragments	2005	PODS	4.3290808e-05
3,040	Tractable Query Languages for Complex Object Databases	1991	PODS	7.6707607e-05
7,248	Positive Higher-Order Queries	2010	PODS	4.7902631e-05
6,150	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.1846373e-05
4,285	A Query Language for List-Based Complex Objects	1994	PODS	6.2913523e-05
5,503	Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract)	2000	PODS	5.4738619e-05
1,663	Conjunctive Queries over Trees	2004	PODS	0.00010977096
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
6,794	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	4.9244886e-05