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,640 | On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values | 2005 | PODS | 6.6548728e-05 |
| 12,673 | String Operations in Query Languages | 2001 | PODS | 5.1725247e-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,137 | An Expressive Language for Linear Spatial Database Queries (extended abstract) | 1998 | PODS | 6.9412338e-05 |
| 4,156 | Safe Constraint Queries | 1998 | PODS | 6.9267856e-05 |
| 4,274 | Languages for Relational Databases over Interpreted Structures | 1997 | PODS | 6.8586833e-05 |
| 4,399 | A Query Language for List-Based Complex Objects | 1994 | PODS | 6.785593e-05 |
| 6,612 | Complexity of Nonrecursive Logic Programs with Complex Values | 1998 | PODS | 5.8835431e-05 |
Previous
Page 1 / 1
Next