×

Preserving two-tuple dependencies under projection. (English) Zbl 0729.68015

This paper deals with the study of the conditions under which a special type of dependencies, known in the relational database theory as propositional dependencies, are preserved under projection. Because propositional dependencies are slightly more general than functional dependencies, the results given in this paper are also applicable to functional dependencies.
In the introductory section, some considerations on the importance of the propositional dependencies theory for the study of the database design process, are made. Also, three well known database problems (extensibility, view update and implied constraint) related to the problems from this paper, are listed.
The propositional dependencies are defined in section 2. Section 3 deals with the study of different forms to represent propositional dependencies and relations, named “constraints tableaux”. To a given set of propositional dependencies a standard disjunctive normal form is associated, which in its turn is represented as a 0-1 matrix representing the constraint tableau. Also, a relation can be represented as an extended constraint tableau named \(\Omega\) tableau. The main results of this section are: a realizability theorem for a \(\Omega\) tableau and as a corollary, validity conditions for functional dependencies.
In the next section, the previous results are used to solve the following problem: (we cite from the paper) “Given a set of functional dependencies \(\Sigma\) over the universal set of attributes U, and a relation S(X), \(X\subseteq U\) such that S satisfies \(\pi_ X(\Sigma)\), i.e. the projection of \(\Sigma\) over X, then under what conditions does there exist a relation R(U) that satisfies \(\Sigma\) such that \(S=\pi_ X(R)\), i.e. S is the projection of R.”
Also an algorithm to compute such a relation, if it exists, is given and exemplified. The main result of this paper concerning the conditions under which propositional dependencies are preserved under projections is proved in section 5.
All the concepts and results presented in this paper are defined and proved respectively, and all of them are exemplified. Except for few typing errors, the paper is well written and the references are good. It is assumed that the reader is familiar with relational database theory and with some background in propositional logic.

MSC:

68P15 Database theory
PDFBibTeX XMLCite