Algebraic and calculus query languages for recursively typed complex objects (Q686644)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algebraic and calculus query languages for recursively typed complex objects |
scientific article |
Statements
Algebraic and calculus query languages for recursively typed complex objects (English)
0 references
10 October 1993
0 references
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.
0 references
recursively typed complex objects
0 references
query languages
0 references