The following problem motivated by investigation of databases is studied. Let be a q-ary code of length n with the properties that has minimum distance at least n − k + 1, and for any set of k − 1 coordinates there exist two codewords that agree exactly there. Let f(q, k)be the maximum n for which such a code exists. f(q, k)is bounded by linear functions of k and q, and the exact values for special k and qare determined.
@article{bwmeta1.element.doi-10_2478_s11533-008-0001-4,
author = {Gyula Katona and Attila Sali and Klaus-Dieter Schewe},
title = {Codes that attain minimum distance in every possible direction},
journal = {Open Mathematics},
volume = {6},
year = {2008},
pages = {1-11},
zbl = {1140.94020},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-008-0001-4}
}
Gyula Katona; Attila Sali; Klaus-Dieter Schewe. Codes that attain minimum distance in every possible direction. Open Mathematics, Tome 6 (2008) pp. 1-11. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-008-0001-4/
[1] Abiteboul S., Hull R., Vianu V., Foundations of databases, Addison-Wesley, 1995 | Zbl 0848.68031
[2] Armstrong W.W., Dependency structures of data base relationships, Information Processing, 1974, 74, 580–583
[3] Demetrovics J., On the equivalence of candidate keys with Sperner systems, Acta Cybernet., 1978/79, 4, 247–252 | Zbl 0427.68072
[4] Demetrovics J., Füredi Z., Katona G.O.H., Minimum matrix representation of closure operations, Discrete Appl. Math., 1985, 11, 115–128 http://dx.doi.org/10.1016/S0166-218X(85)80003-2 | Zbl 0577.68084
[5] Demetrovics J., Gyepesi G., A note on minimal matrix representation of closure operations, Combinatorica, 1983, 3, 177–179 http://dx.doi.org/10.1007/BF02579291 | Zbl 0526.06004
[6] Demetrovics J., Katona G.O.H., Extremal combinatorial problems in relational data base, In: Fundamentals of computation theory, Springer-Verlag, Berlin-New York, 1981 | Zbl 0466.68086
[7] Demetrovics J., Katona G.O.H., Sali A., The characterization of branching dependencies, Discrete Appl. Math., 1992, 40, 139–153 http://dx.doi.org/10.1016/0166-218X(92)90027-8 | Zbl 0767.68030
[8] Demetrovics J., Katona G.O.H., Sali A., Design type problems motivated by database theory, J. Statist. Plann. Inference, 1998, 72, 149–164 http://dx.doi.org/10.1016/S0378-3758(98)00029-9 | Zbl 0932.68038
[9] Demetrovics J., Katona G.O.H., A survey of some combinatorial results concerning functional dependencies in database relations, Ann. Math. Artificial Intelligence, 1993, 7, 63–82 http://dx.doi.org/10.1007/BF01556350 | Zbl 1034.68513
[10] Fagin R., Horn clauses and database dependencies, J. Assoc. Comput. Mach., 1982, 29, 952–985 | Zbl 0493.68092
[11] Füredi Z., Perfect error-correcting databases, Discrete Appl. Math., 1990, 28, 171–176 http://dx.doi.org/10.1016/0166-218X(90)90114-R | Zbl 0738.05071
[12] Hartmann S., Link S., Schewe K.-D., Weak functional dependencies in higher-order datamodels, In: Seipel D., Turull Torres J. M. (Eds.), Foundations of Information and Knowledge Systems, Springer LNCS, 2942, Springer Verlag, 2004 | Zbl 1202.68141
[13] Odlyzko A.M., Asymptotic enumeration methods, In: Graham R.L, Crbtschel M., Lovász L. (Eds.), Handbook of combinatorics, Elsevier, Amsterdam, 1995 | Zbl 0845.05005
[14] Sali A., Minimal keys in higher-order datamodels, In: Seipel D., Turull Torres J. M. (Eds.), Foundations of Information and Knowledge Systems, Springer LNCS, 2942, Springer Verlag, 2004 | Zbl 1202.68149
[15] Sali A., Schewe K.-D., Counter-free keys and functional dependencies in higher-order datamodels, Fund. Inform., 2006, 70, 277–301 | Zbl 1101.68526
[16] Sali A., Schewe K.-D., Keys and Armstrong databases in trees with restructuring, Acta Cybernet., preprint | Zbl 1164.68335
[17] Silva A.M., Melkanoff M.A., A method for helping discover the dependencies of a relation, In: Gallaire H., Minker J., Nicolas J.-M. (Eds.), Advances in Data Base Theory, Plenum Publishing, New York, 1981
[18] Turán P., On an extremal problem in graph theory, Mat. Fiz. Lapok, 1941, 48, 436–452 (in Hungarian)