Closure via functional dependence simplification

摘要

In this paper, a method for computing the closure of a set of attributes according to a specification of functional dependencies of the relational model is described. The main feature of this method is that it computes the closure using solely the inference system of the SL_(FD) logic. For the first time, logic is used in the design of automated deduction methods to solve the closure problem. The strong link between the SL_(FD) logic and the closure algorithm is presented and an SL_(FD) simplification paradigm emerges as the key element of our method. In addition, the soundness and completeness of the closure algorithm are shown. Our method has linear complexity, as the classical closure algorithms, and it has all the advantages provided by the use of logic. We have empirically compared our algorithm with the Diederich and Milton classicai algorithm. This experiment reveals the best behaviour of our method which shows a significant improvement in the average speed.