zbMATH — the first resource for mathematics

Deductive query langauges for recursively typed complex objects. (English) Zbl 0905.68058
Summary: Deductive database query languages for recursively typed complex objects based on the set and tuple constructs are studied. A fundamental characteristic of such complex objects is that in them, sets may contain members with arbitrarily deep nesting of tuple and set constructs. Relative to mappings from flat relations to flat relations, two extensions of COL in this context (with stratified semantics and inflationary semantics, respectively) are shown to have the expressive power of computable queries. Although the deductive calculus of Bancilhon and Khoshafian has the ability to simulate Turing machines, when restricted to flat input and output its expressive power is characterized by a weak variant of the conjunctive queries.

68P15 Database theory
68N17 Logic programming
Full Text: DOI