The multiple facets of the canonical direct unit implicational basis

Karell Bertet (1) , Bernard Monjardet (2)

1 L3I - Laboratoire Informatique, Image et Interaction - EA 2118
2 CES - Centre d'économie de la Sorbonne

The notion of dependencies between "attributes" arises in many areas such as relational databases, data analysis, data-mining, formal concept analysis, knowledge spaces. Formalization of dependencies leads to the notion of so-called full implicational systems (or full family of functional dependencies) which is in one-to-one correspondence with the other signicant notions of closure operator and of closure system. An efficient generation of a full implicational system (or of a closure system) can be performed from equivalent implicational systems and in particular from bases for such systems, for example, the so-called canonical basis. This paper shows the equality between five other bases originating from dfferent works and satisfying various properties (in particular they are unit implicational systems). The three main properties of this unique basis are the directness, canonical and minimal properties, whence the name canonical direct unit implicational basis given to this unit implicational system. The paper also gives a characterization of this canonical basis and it makes precise its link with the prime implicants of the Horn function associated to a closure operator.

La notion de dépendance entre attributs est présente dans de nombreux domaines comme les bases de données relationnelles, l'analyse et la fouille des données, l'analyse formelle des concepts ou les espaces de connaissance. La formalisation de ces dépendances conduit à la notion de système complet d'implications, notion en correspondance biunivoque avec les notions d'opérateur de fermeture ou de famille de Moore. Un système complet d'implications (ou une fermeture) peut être engendré efficacement à partir de bases, par exemple la la base canonique (de Duquenne et Guigues). Dans ce texte, nous montrons l'identité de cinq autres bases obtenues dans des domaines variés . Cette base est unitaire directe, canonique et minimale, d'où son nom de base unitaire canonique directe. Nous donnons une caractérisation de cette base et nous montrons sa correspondance avec les implicants premiers de la fonction de Horn associée à une fermeture.

Mots clés: canonical direct basis; closure system; formal concept analysis; functional dependency; Horn function; implicational system; knowledge space; prime implicant; relational databases

Mots clés: analyse formelle de concepts; base canonique directe; base de données relationnelles; dépendance fonctionnelle; famille de Moore; fonction de Horn; implication; implicant premier; système de fermeture

Domaines: Méthodes et statistiques; Base de données [cs.DB]

Karell Bertet, Bernard Monjardet. The multiple facets of the canonical direct unit implicational basis. Theoretical Computer Science, 2010, 411 (22-24), pp.2155-2166. ⟨10.1016/j.tcs.2009.12.021⟩. ⟨halshs-00308798v2⟩