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,612 | On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values | 2005 | PODS | 6.0428289e-05 |
| 12,673 | String Operations in Query Languages | 2001 | PODS | 4.1905499e-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,278 | A Query Language for List-Based Complex Objects | 1994 | PODS | 6.285241e-05 |
| 4,343 | Languages for Relational Databases over Interpreted Structures | 1997 | PODS | 6.2665123e-05 |
| 4,366 | An Expressive Language for Linear Spatial Database Queries (extended abstract) | 1998 | PODS | 6.2427716e-05 |
| 4,376 | Safe Constraint Queries | 1998 | PODS | 6.233754e-05 |
| 6,795 | Complexity of Nonrecursive Logic Programs with Complex Values | 1998 | PODS | 4.9197522e-05 |
Previous
Page 1 / 1
Next