Dependencies in Relational Databases Algebraic and Logical Approach ¹

Article type: Research Article

Authors: Rauszer, Cecylia M.

Affiliations: Institute of Mathematics, Warsaw University, Banacha 2, 02-097 Warsaw, Poland

Note: [1] An extended abstract of the paper has been published in the Colloquia Proceedings of ISMIS, 1987, Charlotte, USA.

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.

DOI: 10.3233/FI-1993-193-403

Journal: Fundamenta Informaticae, vol. 19, no. 3-4, pp. 235-274, 1993