Inferring dependencies from relations: A conceptual clustering approach

In this paper we consider two related types of data dependencies that can hold ina relation: conjunctiva implication rules between attribute-value pairs, and functional dependencies. We present a conceptual clustering approach that can be used, with some small modifications, for inferring a cover for both types of dependencies. The approach consists of two steps. First, a particular clustered representation of the relation, called concept (or Galois) lattice, is built. Then, a cover is extracted from the lattice built in the earlier step. Our main emphasis is on the second step. We study the computational complexity of the proposed approach and present an experimental comparison with other methods that confirms its validity. The results of the experiments show that our algorithm for extracting implication rules from concept lattices clearly outperforms an earlier algorithm, and suggest that the overall lattice-based approach to inferring functional dependencies from relations can be seen as an alternative to traditional methods.