Dependencies in Relational Databases Algebraic and Logical Approach 1

Abstract

Functional and multivalued dependencies are expressed in terms of special equivalence relations, called indiscernibility relations. Subsequently, an algebra of indiscernibility relations of a given relational database is introduced and examined. It is shown that a dependency holds in a database if and only if a corresponding algebraic formula is equal to the greatest element in the algebra.

In addition, a formal deductive system, called D-logic is defined. This system corresponds to a fragment of non-classical logic. An equivalence theorem showing that D-logic describes, in an adequate way, properties of functional and multivalued dependencies is stated.

D-logic and D-lattices are instrumental in proving several properties of dependencies. Examples showing how these techniques are valuable in proving theorems about dependencies are given.