online read us now
Paper details
Number 1 - March 1996
Volume 6 - 1996
Computing a cover for projected functional dependencies from a Boolean expression
Wojciech Zawadzki
Abstract
This paper gives the solution to a problem of finding an expression for a cover for πR(F), where F is a set of functional dependencies, using Boolean functions as a formal tool. Another approach to represent a set of functional dependencies F by a Boolean function φ (R), where R = {A,B, ... } stands for a relation schema, is presented. The main result is an algorithm of transformation: φ(R) → φ(πX(R)) → πX(F). It is shown that such a transformation is equivalent to the decomposition of a Boolean function. The algorithm employs a number of optimization steps to reduce its complexity and to avoid redundancies resulting from the augmentation rule. A paper is being prepared (Zawadzki, 1995) in which the algorithm will be implemented and some estimation of time complexity will be given. It is conjectured that it may run in polynomial time unless the number of non-redundant dependencies is itself an exponential function of |X|. To the author's knowledge, there is only one algorithm (Gottlob, 1987) for the above problem, but it is not guaranteed to run in polynomial time.
Keywords
-