Skip to Main content Skip to Navigation
Journal articles

Characterizing functional dependencies in formal concept analysis with pattern structures

Jaume Baixeries 1 Mehdi Kaytoue 2 Amedeo Napoli 3
1 Departament de Llenguatges i Sistemes Informatics
LSI - Llenguatges i Sistemes Informàtics
2 DM2L - Data Mining and Machine Learning
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
3 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
Abstract : Computing functional dependencies from a relation is an impor-tant database topic, with many applications in database management, reverse engineering and query optimization. Whereas it has been deeply investigated in those fields, strong links exist with the mathematical framework of For-mal Concept Analysis. Considering the discovery of functional dependencies, it is indeed known that a relation can be expressed as the binary relation of a formal context, whose implications are equivalent to those dependencies. How-ever, this leads to a new data representation that is quadratic in the number of objects w.r.t. the original data. Here, we present an alternative avoiding such a data representation and show how to characterize functional dependencies using the formalism of pattern structures, an extension of classical FCA to handle complex data. We also show how another class of dependencies can be characterized with that framework, namely, degenerated multivalued depen-dencies. Finally, we discuss and compare the performances of our new approach in a series of experiments on classical benchmark datasets.
Document type :
Journal articles
Complete list of metadata

Cited literature [43 references]  Display  Hide  Download
Contributor : Amedeo Napoli Connect in order to contact the contributor
Submitted on : Friday, January 9, 2015 - 5:04:10 PM
Last modification on : Saturday, October 16, 2021 - 11:26:07 AM
Long-term archiving on: : Friday, September 11, 2015 - 1:40:16 AM


Files produced by the author(s)



Jaume Baixeries, Mehdi Kaytoue, Amedeo Napoli. Characterizing functional dependencies in formal concept analysis with pattern structures. Annals of Mathematics and Artificial Intelligence, Springer Verlag, 2014, 72, pp.129 - 149. ⟨10.1007/s10472-014-9400-3⟩. ⟨hal-01101107⟩



Les métriques sont temporairement indisponibles