On the expressive power of data dependencies

Abstract

The class of data dependencies is a class of first-order sentences that seem to be suitable to express semantic constraints for relational databases. We deal with the question of which classes of databases are axiomatizable by data dependencies. (A class Γ of databases is said to be axiomatizable by sentences of a certain kind if there exists a set of sentences of that kind such that Γ is the class of all models of that set.) Our results characterize, by algebraic closure conditions, classes of databases that are axiomatizable by dependencies of different kinds. Our technique is model-theoretic, and the characterization easily entails all previously known results on axiomatizability by dependencies. © 1986 Springer-Verlag.