×

Minimum matrix representation of closure operations. (English) Zbl 0577.68084

Let a be a column of the matrix M and A be a set of its columns. We say that A implies a iff M contains no two rows equal in A but different in a. It is easy to see that if \(L_ M(A)\) denotes the columns implied by A, then \(L_ M(A)\) is a closure operation. We say in this case that M represents this closure operation. Let s(L) denote the minimum number of rows of the matrices representing a given closure operation L. The paper contains three types of results. In section 3 s(L) is determined for some special closure operations. In section 4, \(s(L_ 1\times L_ 2)\) is given in terms of \(s(L_ 1)\) and \(s(L_ 2)\). Finally closure operations L with large s(L) are considered.
Reviewer: L.Rónyai

MSC:

68P20 Information storage and retrieval of data
68P05 Data structures
05A99 Enumerative combinatorics

Keywords:

database
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Armstrong, W. W., Dependency structures of data base relationship, (Information Processing, 74 (1974), North-Holland: North-Holland New York), 580-583 · Zbl 0296.68038
[2] Békéssy, A.; Demetrovics, J.; Hannák, L.; Katona, G. O.H.; Frankl, P., On the number of maximal dependencies in a data base relation of fixed order, Discrete Math., 30, 83-88 (1980) · Zbl 0452.68098
[3] Békéssy, A.; Demetrovics, J.; Gyepesi, Gy., Logical investigation of the relational date model in view of functional dependency (in Hungarian), MTA SZTAKI Tanulmányok, 109, 1-56 (1980)
[4] Codd, E. F., A relational model of data for large shared data banks, Comm ACM, 13, 377-387 (1970) · Zbl 0207.18003
[5] Demetrovics, J., Candidate keys and antichains, SIAM J. Algebraic Discrete Methods, 1, 92 (1980) · Zbl 0496.68067
[6] Demetrovics, J., On the equivalence of candidate keys with Sperner systems, Acta Cybernetica (Szeged), 4, 247-252 (1979) · Zbl 0427.68072
[7] Demetrovics, J.; Gyepesi, Gy., On the functional dependency and some generalization of it, Acta Cybernetica, 5, 295-305 (1981) · Zbl 0549.68094
[8] Demetrovics, J.; Gyepesi, Gy., A note on minimal matrix representation of closure operations, Combinatorica, 3, 177-179 (1983) · Zbl 0526.06004
[9] Demetrovics, J.; Katona, G. O.H., Extremal combinatorial problems in relational data base, (Lecture Notes in Computer Science, 117 (1981), Springer: Springer Amsterdam), 110-119 · Zbl 0466.68086
[10] Füredi, Z., Minimum relational data bases (in Hungarian), Alk. Mat. Lapok, 9, 23-28 (1983) · Zbl 0531.68053
[11] Hanani, H., The existence and construction of balanced incomplete block designs, Ann. Math. Statist., 32, 361-386 (1961) · Zbl 0107.36102
[12] Hanani, H., On resolvable balanced incomplete block designs, J. Combin. Theory (A), 17, 275-289 (1974) · Zbl 0305.05010
[13] Moon, J. W.; Moser, L., On cliques in graphs, Israel J. Math., 3, 23-28 (1965) · Zbl 0144.23205
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.