Algebraic and calculus query languages for recursively typed complex objects (Q686644)

A theoretical study of the expressive power of algebraic and calculus query languages for complex objects using recursive types is conducted. In a companion paper (in preparation) analogous issues for deductive query languages are explored. The results indicate that recursive types generally increase the power of a language considerably: the algebra with iteration has the power of computable queries and the calculus has the power of an arithmetical hierarchy relativized to generic queries. A technical vehicle called ``domain Turing machine'' is introduced which is useful for proving results about the expressive power of query languages. Several classes of relational queries defined by complexity can be characterized in a natural fashion using a domain Turing machine. The investigation provides a bridge between research on the use of non- recursive complex objects in query languages and research on computable queries.