On the expressive power of data dependencies (Q1822528)

Since the language of data dependencies is a language for semantic specification of databases, it is highly desirable to know which classes of databases are axiomatizable by different kinds of data dependencies. As a decisive step towards a comprehensive theory, the paper under review gives characterizations of axiomatizability of (finite) databases by data dependencies, using algebraic closure conditions. Some preservation properties of dependencies are given, following the line of investigation of \textit{J. A. Makowsky} [Logic Colloquium '82, Proc. Colloq., Florence 1982, Stud. Logic Found. Math. 112, 303-343 (1984; Zbl 0553.68028)]. Then, the algebraic characterizations of axiomatizability are proved by means of two model-theoretic techniques. These characterizations are used to obtain axiomatizability results for external views and consistent databases.