Expressive power and data complexity of nonrecursive query languages for lists and trees (extended abstract)

Abstract

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.