Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract)
Summary: With list/tree primitives, nonrecursive Datalog/Prolog/FO all have the same expressive power; their range‑restricted fragments equal relational algebra and every query is a Boolean combination of range‑restricted queries. Data complexity is polynomial (in AC0 under natural encodings): lists/trees add no expressiveness but induce a nonelementary program‑complexity blowup vs. PSPACE for the relational counterparts. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,611 | On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values | 2005 | PODS | 6.0488752e-05 |
| 12,664 | String Operations in Query Languages | 2001 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,285 | A Query Language for List-Based Complex Objects | 1994 | PODS | 6.2913523e-05 |
| 4,346 | Languages for Relational Databases over Interpreted Structures | 1997 | PODS | 6.2725564e-05 |
| 4,369 | An Expressive Language for Linear Spatial Database Queries (extended abstract) | 1998 | PODS | 6.2487721e-05 |
| 4,379 | Safe Constraint Queries | 1998 | PODS | 6.2397591e-05 |
| 6,794 | Complexity of Nonrecursive Logic Programs with Complex Values | 1998 | PODS | 4.9244886e-05 |
Previous
Page 1 / 1
Next