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 metadatas

Cited literature [43 references]  Display  Hide  Download

https://hal.inria.fr/hal-01101107
Contributor : Amedeo Napoli <>
Submitted on : Friday, January 9, 2015 - 5:04:10 PM
Last modification on : Tuesday, December 18, 2018 - 4:38:02 PM
Long-term archiving on : Friday, September 11, 2015 - 1:40:16 AM

File

jb+mk+an-amai72-2014.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

468

Files downloads

297