## Closure via functional dependence simplification.(English)Zbl 1257.68064

Summary: 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$$_{\mathsf{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$$_{\mathsf{FD}}$$ logic and the closure algorithm is presented and an SL$$_{\mathsf{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 classical algorithm. This experiment reveals the best behaviour of our method which shows a significant improvement in the average speed.

### MSC:

 68P15 Database theory 03B70 Logic in computer science 68T30 Knowledge representation

### Keywords:

logic; closure operator; functional dependencies

Maude
Full Text: