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.0428289e-05
Overall Rank: 4,612 | 67.95%
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,633	Behavioral Simulations in MapReduce	2010	VLDB	6.8959345e-05
6,299	Incremental View Maintenance For Collection Programming	2016	PODS	5.1176554e-05
7,234	A Crash Course on Database Queries	2007	PODS	4.7882493e-05
7,244	Positive Higher-Order Queries	2010	PODS	4.7856771e-05
7,453	The GCX System: Dynamic Buffer Minimization in Streaming XQuery Evaluation	2007	VLDB	4.7218383e-05
11,159	Synthesizing Nested Relational Queries from Implicit Specifications	2023	PODS	4.1905499e-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
93	Remarks on the Algebra of Non First Normal Form Relations	1982	PODS	0.00051290296
485	A New Approach to Database Logic	1984	PODS	0.00022061287
712	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00017714027
1,123	A Transducer-Based XML Query Processor	2002	VLDB	0.00013836955
1,261	Projecting XML Documents	2003	VLDB	0.00012985367
1,792	The BEA/XQRL Streaming XQuery Processor	2003	VLDB	0.00010524893
1,854	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	0.00010320817
2,250	The Complexity of XPath Query Evaluation	2003	PODS	9.1949563e-05
2,546	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS	8.5606179e-05
2,560	Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions	1988	PODS	8.541561e-05
3,043	Tractable Query Languages for Complex Object Databases	1991	PODS	7.6632326e-05
3,195	On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions	1989	SIGMOD	7.4052272e-05
3,928	Schema-based Scheduling of Event Processors and Buffer Minimization for Queries on Structured Data Streams	2004	VLDB	6.6206222e-05
5,516	Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract)	2000	PODS	5.4685963e-05
5,980	A Query Language for NC	1994	PODS	5.241279e-05
6,795	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	4.9197522e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,531	Deciding Well-Definedness of XQuery Fragments	2005	PODS	4.3249319e-05
12,856	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB	4.1905499e-05
3,043	Tractable Query Languages for Complex Object Databases	1991	PODS	7.6632326e-05
7,244	Positive Higher-Order Queries	2010	PODS	4.7856771e-05
6,153	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS	5.1796878e-05
4,278	A Query Language for List-Based Complex Objects	1994	PODS	6.285241e-05
1,662	Conjunctive Queries over Trees	2004	PODS	0.00010966423
5,516	Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract)	2000	PODS	5.4685963e-05
432	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023349408
6,795	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	4.9197522e-05