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: hfc282c50abc66241
Venue: PODS
Year: 2005
Pagerank: 6.4049669e-05
Overall Rank: 4,810 | 67.68%
DOI: 10.1145/1065167.1065179

Incoming Non-self Citations Over Time

Authors

1. Christoph Koch (Vienna University of Technology)

BibTeX Citation

@inproceedings{koch_pods05,
        address = {New York, NY, USA},
        series = {{PODS} '05},
        title = {{On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values}},
        url = {https://dl.acm.org/doi/10.1145/1065167.1065179},
        doi = {10.1145/1065167.1065179},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Koch, Christoph},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,142	Behavioral Simulations in MapReduce	2010	VLDB	6.780997e-05
6,223	Incremental View Maintenance For Collection Programming	2016	PODS	5.8443814e-05
7,423	A Crash Course on Database Queries	2007	PODS	5.5299903e-05
7,629	The GCX System: Dynamic Buffer Minimization in Streaming XQuery Evaluation	2007	VLDB	5.4797177e-05
7,812	Positive Higher-Order Queries	2010	PODS	5.4475778e-05
11,684	Synthesizing Nested Relational Queries from Implicit Specifications	2023	PODS	4.9769913e-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
140	Remarks on the Algebra of Non First Normal Form Relations	1982	PODS	0.00029333191
559	A New Approach to Database Logic	1984	PODS	0.00016414522
680	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.0001483008
1,111	A Transducer-Based XML Query Processor	2002	VLDB	0.00011978534
1,174	Projecting XML Documents	2003	VLDB	0.00011662712
1,539	The BEA/XQRL Streaming XQuery Processor	2003	VLDB	0.00010311535
2,179	The Complexity of XPath Query Evaluation	2003	PODS	8.9111534e-05
2,515	Towards Tractable Algebras for Bags (Extended Abstract)	1993	PODS	8.3605462e-05
2,751	Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions	1988	PODS	8.0523904e-05
2,935	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	7.8361406e-05
3,047	Tractable Query Languages for Complex Object Databases	1991	PODS	7.7108309e-05
3,184	On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions	1989	SIGMOD	7.5543186e-05
3,586	Schema-based Scheduling of Event Processors and Buffer Minimization for Queries on Structured Data Streams	2004	VLDB	7.1859239e-05
6,322	Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract)	2000	PODS	5.8126141e-05
6,804	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	5.6771104e-05
7,234	A Query Language for NC	1994	PODS	5.576635e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,858	Deciding Well-Definedness of XQuery Fragments	2005	PODS
2	13,336	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB
3	3,047	Tractable Query Languages for Complex Object Databases	1991	PODS
4	7,812	Positive Higher-Order Queries	2010	PODS
5	6,574	XPath, Transitive Closure Logic, and Nested Tree Walking Automata	2008	PODS
6	4,561	A Query Language for List-Based Complex Objects	1994	PODS
7	6,322	Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract)	2000	PODS
8	1,599	Conjunctive Queries over Trees	2004	PODS
9	421	On the Complexity of Database Queries (Extended Abstract)	1997	PODS
10	6,804	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS