On the expressive power of database queries with intermediate types

摘要

The set-height of a complex object type is defined to be its level of nesting of the set construct. In a query of the complex object calculus which maps a database D to an output type T, an intermediate type is a type which is used by some variable of the query, but which is not present in D or T. For each k, i ⩾ 0 we define CALCk,i to be the family of calculus queries mapping from and to types with set-height ⩽ k and using intermediate types with set-height ⩽i. In particular, CALC0.0 is the classical relational calculus, and CALC0.1 is equivalent to the family of second-order (relational) queries. Several results concerning these families of languages are obtained. A primary focus is on the families CALC0, i, which map relations to relations. Upper and lower bounds in terms of hyper-exponential time and space on the complexity of these families are provided. The CALC0, i hierarchy does not collapse with respect to expressive power. The union ∪0 ⩽ iCALC0, i is exactly the family of elementary queries, i.e., queries with hyper-exponential complexity. The expressive power of queries from the complex object calculus interpreted using semantics based on the use of arbitrarily large finite or infinite set of invented values is studied. Under these semantics, the expressive power of the relational calculus is not increased, and the CALC0, i hierarchy collapses at CALC0.1. In general, queries with these semantics may not be computable. We also consider an alternative semantics which yields a family of queries equivalent to the computable queries.