The multiple facets of the canonical direct unit implicational basis. (English) Zbl 1209.68187

Bertet, K.; Monjardet, B.

Theor. Comput. Sci. 411, No. 22-24, 2155-2166 (2010).

Summary: The notion of dependencies between “attributes” arises in many areas such as relational databases, data analysis, data-mining, formal concept analysis, knowledge structures \(\dots \). 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.

MSC:

68P15

Database theory

Keywords:

implicational system; closure operator; closure system; canonical direct unit basis; lattice; Horn Boolean function

Software:

JBool

References:

[1]	Aizerman, M.A.; Aleskerov, F.T., Theory of choice, (1995), Elsevier Science B.V North Holland · Zbl 0721.90001
[2]	Appert, A., Sur LES topologies transitives, Bulletin de l’académie royale de belgique (classe des sciences), 23, 2, 135-142, (1937) · JFM 63.1172.01
[3]	Armstrong, W.W., Dependency structures of database relationships, Information processing, 74, 580-583, (1974) · Zbl 0296.68038
[4]	Berry, A.; San Juan, E., Generalized domination in closure systems, Discrete applied mathematics, 154, 7, 1064-1084, (2006) · Zbl 1093.68033
[5]	K. Bertet, Some algorithmical aspects using the canonical direct implicational basis, in: Fourth International Conference on Concept Lattice and their Applications, CLA’06, 2006, pp. 101-114.
[6]	Bertet, K.; Nebut, M., Efficient algorithms on the Moore family associated to an implicational system, Dmtcs, 6, 2, 315-338, (2004) · Zbl 1062.06004
[7]	Birkhoff, G., Lattice theory, (1940), American Mathematical Society · Zbl 0126.03801
[8]	Birkhoff, G.; Frink, O., Representations of lattices by sets, Transactions of the American mathematical society, 64, 299-316, (1948) · Zbl 0032.00504
[9]	Buchi, J.R., Finite automatas, their algebras and grammars, () · Zbl 0142.24902
[10]	Caspard, N.; Leclerc, B.; Monjardet, B., Ensembles ordonnés finis: concepts, Résultats et usages, vol. 60, (2007), Springer
[11]	Caspard, N.; Monjardet, B., The lattice of closure systems, closure operators and implicational systems on a finite set: A survey, Discrete applied mathematics, 127, 2, 241-269, (2003) · Zbl 1026.06008
[12]	Codd, E.F., A relational model of data for large shared data banks, Communications of the ACM, 13, 6, 377-387, (1970) · Zbl 0207.18003
[13]	Crama, Y.; Hammer, P.L., Boolean functions, (2009), Cambridge University Press
[14]	Davey, B.A.; Priestley, H.A., Introduction to lattices and orders, (1991), Cambridge University Press · Zbl 0701.06001
[15]	Dechter, R.; Pearl, J., Structure identification in relational data, Artificial intelligence, 58, 237-270, (1992) · Zbl 0782.68095
[16]	Demetrovics, J.; Nam-Son, H., Databases, closure operations and sperner families, (), 199-203 · Zbl 0839.68025
[17]	Doignon, J.P.; Falmagne, J.C., Knowledge spaces, (1999), Springer Verlag Berlin
[18]	Duquenne, V., Latticial structures in data analysis, Theoretical computer science, 217, 2, 407-436, (1999) · Zbl 1034.68510
[19]	Fagin, R., Functional dependencies in a relational database and propositional logic, IBM journal of research and development, 21, 6, 534-544, (1977) · Zbl 0366.68022
[20]	Ganter, B., Attribute exploration with background knowledge, Theoretical computer science, 217, 215-233, (1999) · Zbl 0914.68168
[21]	Ganter, B.; Wille, R., Formal concept analysis, mathematical foundations, (1999), Springer Verlag Berlin · Zbl 0909.06001
[22]	Gentzen, G., Investigations into logical deduction, ()
[23]	Guigues, J.L.; Duquenne, V., Familles minimales d’implications informatives résultant d’un tableau de données binaires, Mathematiques & sciences humaines, 95, 5-18, (1986)
[24]	Hammer, P.L.; Kogan, A., Horn’s functions and their dnfs, Information processing letters, 44, 23-29, (1992) · Zbl 0794.68148
[25]	Hand, D.; Mannila, H.; Smyth, P., Principles of data-mining, (2001), MIT Press
[26]	Henschen, L.J., Semantic resolution for Horn sets, IEEE transactions on computers, 25, 816-822, (1976) · Zbl 0331.68054
[27]	Hertz, P., Über axiomensysteme für beliebige satzsysteme, Mathematische annalen, 101, 457-514, (1927) · JFM 55.0627.01
[28]	Hodges, W., Logical features of Horn clauses, (), 449-503
[29]	Horn, A., On sentences which are true of direct unions of algebras, Journal of symbolic logic, 16, 14-21, (1951) · Zbl 0043.24801
[30]	Ibaraki, T.; Kogan, A.; Makino, K., Functional dependencies in Horn theories, Artificial intelligence, 108, 1-30, (1999) · Zbl 0914.68185
[31]	K. Ben-Khalifa, S. Montameny, Horn-representation of a concept lattice, in: J. Diatta, P. Eklund, M. Liquière (Eds.), Fifth International Conference on Concept Lattices and their Applications, CLA’2007, Montpellier, France, October 24-26, 2007, pp. 181-191.
[32]	Maier, D., The theory of relational databases, (1983), Computer Sciences Press · Zbl 0519.68082
[33]	Mannila, H.; Räihä, K.J., The design of relational databases, (1992), Addison-Wesley · Zbl 0777.68014
[34]	McKinsey, J.C.C., The decision problem for some classes of sentences without quantifiers, Journal of symbolic logic, 8, 61-76, (1943) · Zbl 0063.03864
[35]	Monjardet, B., Arrowian characterizations of latticial federation consensus functions, Mathematical social sciences, 20, 1, 51-71, (1990) · Zbl 0746.90002
[36]	Monjardet, B., The presence of lattice theory in discrete problems of mathematical social sciences, Why? mathematical social sciences, 46, 2, 103-144, (2003) · Zbl 1054.91062
[37]	E.H. Moore, On a form of general analysis with applications to linear differential and integral equations, in: Atti del IV Congr. Int. dei Mat. II, Roma, 1909, pp. 98-114.
[38]	Rusch, A.; Wille, R., Knowledge spaces and formal concept analysis, (), 427-436 · Zbl 0899.92041
[39]	Scott, D., Completeness and axiomatizability in many-valued logic, (), 411-435
[40]	Scott, D.S., Domains for denotational semantics, (), 577-613
[41]	R. Taouil, Y. Bastide, Computing proper implications, in: 9th International Conference on Conceptual Structures, Stanford, USA, 2002. · Zbl 0996.68046
[42]	Tarski, A., Remarques sur LES notions fondamentales de la méthodologie des mathématiques, Annales de la société polonaise de mathématiques, 7, 270-272, (1929) · JFM 55.0038.15
[43]	Wild, M., A theory of finite closure spaces based on implications, Advances in mathematics, 108, 1, 118-139, (1994) · Zbl 0863.54002