Expressive power: The finit case
The authors deal with relational databases as a special case of the constraint model. The natural question is: how much more power do constraint languages have over ordinary finite databases. This is equivalent to the study if natural and active semantics queries with interpreted structure. Chapter 3 is divided into eight sections. First two are devoted to review the concepts of active and natural semantics in the relational model. Then three kinds of collapse results are given. After introducing the notation used in the chapter, the authors deal with the active-domain interpretation and generic collapse (section 3.3). The present a technique based on Ramsey's theorem that allows the to prove the generic collapse, for first-order queries as well as for queries in more powerful languages. Section 3.4 studies the natural-active collapse. Unlike the active-generic collapse, the natural-active collapse requires assumptions on the structure. The authors build up structures that have the natural-active collapse (without interpreted operations, o-minimal structures). Section 3.5 concentrates on more powerful logics and query languages such as fixpoint logics and DATALOG. The developed techniques smoothly extend to those logics. In section 3.6, other techniques and extensions including some complexity results are presented. The chapter finishes with a summary of results and bibliographical notes. The results in the chapter can be applied to extend results of the classical theory to the case where interpreted functions are present in selections of relational algebra. For the entire collection see [Zbl 0935.00022].
This page was built for publication: Expressive power: The finit case
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4508937)
