Satisfying database states
Marc H. Graham · 1982
The theory of relational databases has been carried out for the most part under a highly controversial assumption, known as the or pure universal relation assumption. Although this assumption is unrealistic, its utility to the theory is in providing an integrated view of the states of a multirelation database. A significantly weaker assumption, the assumption, has been proposed by Fagin, Mendelzon and Ullman, without an indication of its effects on states of the database. Independently, Honeyman proposed the notion of as a proper definition of a database state's satisfying a set of functional dependencies. We give a formalization of the universal scheme assumption which differs from that of Fagin et. al. and show that the weak instance definition is a natural consequence of this formalization. This remains true even when the database is constrained by any set of implicational dependencies. Having provided this logical foundation, we investigate prior results under the new definition of satisfaction. We show that the results of Aho, Sagiv and Ullman concerning expression and tableaux equivalence carriers over. We then turn to the concept of representation of dependencies as suggested by Bernstein. We give two different definitions of a functional dependency's representation by a schema, show they are different, and show that cover embedding is a stronger than necessary requirement for all of a set of dependencies to be represented by a schema. Finally, we investigate those schemas without interrelational constraints. We show that the ideas first put forward by Rissanen are not the correct ones for this new notion of satisfaction.