The multiple facets of the canonical direct unit implicational basis

• Published in: Theoretical computer science 2010-05, Vol.411 (22), p.2155-2166
• Main Authors: Bertet, K., Monjardet, B.
• Format: Article
• Language: English
• Subjects: Applied sciences; Artificial intelligence; Canonical direct unit basis; Closure operator; Closure system; Combinatorics. Ordered structures; Computer Science; Computer science; control theory; systems; Exact sciences and technology; Horn Boolean function; Humanities and Social Sciences; Implicational system; Lattice; Learning and adaptive systems; Mathematical analysis; Mathematics; Methods and statistics; Miscellaneous; Order, lattices, ordered algebraic structures; Sciences and techniques of general use; Special functions; Theoretical computing
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2009.12.021

The notion of dependencies between “attributes” arises in many areas such as relational databases, data analysis, data-mining, formal concept analysis, knowledge structures … . 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 significant notions of closure operator and of closure system. An efficient generation of a full implicational system (or a closure system) can be performed from equivalent implicational systems and in particular from the bases for such systems, for example, the so-called canonical basis. This paper shows the equality between five other bases originating from different 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 nice characterization of this canonical basis and makes precise its link with the prime implicants of the Horn function associated to a closure operator. It concludes that it is necessary to compare more closely related works made independently, and with a different terminology, in order to take advantage of the really new results in these works.