COMPARISON OF FUNCTIONAL AND PREDICATIVE QUERY PARADIGMS

In the last decade many extensions of the relational model were propos ed, and basic properties of the relational model were investigated in their contexts. In particular, the equivalence of calculus and algebra , and the relative expressive power of other related languages were ex plored. This paper investigates this subject in a general framework, i ndependently of any specific data type constructors that may exist in specific models, with the goal of making explicit the conditions that enable translation between query languages. The framework is based on a combination the well-founded approach of deductive programs and the initial algebra approach of algebraic specifications. The latter does not support negation (i.e., disequations); hence our combination contr ibutes to the theory of algebraic specifications. Given the framework, we present the predicative and functional approaches to database desc ription and querying. The first leads to the calculus and deductive ap proaches, the second to several algebras and, also, to generalizations that allow restricted definition by equations. We extend the notions of domain independence to our framework. We then present various suffi cient conditions for the calculus and (some) algebra to be equivalent. We also compare the expressive power of algebras and more general lan guages to several deductive languages, under stratified and well-found ed semantics. Finally, we define safety conditions and prove similar r esults for safe versions of the languages. (C) 1997 Academic Press.