Closure via functional dependence simplification

Abstract

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 classical algorithm. This experiment reveals the best behaviour of our method which shows a significant improvement in the average speed.

Keywords:

• logic
• closure operator
• functional dependencies

2010 AMS Subject Classifications :

• 03B80
• 68P15

Acknowledgements

This paper was partially supported by project no. TIN2011-28084 of the Science and Innovation Ministry of Spain and P09-FQM-5233 of the Junta de Andalucía. We thank the anonymous referees for their valuable comments that have notably improved the paper.

Notes

We write X ⁺ instead of when no confusion arises.

As usual, |X| denotes the cardinality of the set X.

LIST[a] is a list of dependencies in which a occurs on the left-hand side of the FDs.

All of them have the same language and semantics and the axiomatic systems are equivalents. That is, the set of derived formulas from a given set of formulas is the same in all these logics.

That is, , with the superindex ‘e’ being the abbreviation of the word ‘extended’.

Wild 61 remarked that ‘the execution times are mostly relevant for comparing algorithms’.

A comma-separated values (CSV) file with the results, the source code of the algorithms and the executable version of these for Windows XP used in this empirical study are available at http://enciso.lcc.uma.es/SLFD/.