Expressive power and data complexity of nonrecursive query languages for lists and trees (extended abstract)
Evgeny Dantsin, Андрей Воронков · 2000
We extend the traditional query languages by primitives for handling lists and trees. Our main results characterize the expressive power and data complexity of the following extended languages: (1) relational algebra with lists and trees, (2) nonrecursive [email protected]@@@ with lists and trees, (3) nonrecursive Prolog with lists and trees, (4) first-order logic over lists and trees.