Codes that attain minimum distance in every possible direction

• Autorzy: Gyula Katona , Attila Sali , Klaus-Dieter Schewe
• Języki publikacji: EN

Abstrakty

EN

The following problem motivated by investigation of databases is studied. Let $$ \mathcal{C} $$ be a q-ary code of length n with the properties that $$ \mathcal{C} $$ 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.

Słowa kluczowe

EN

Error correcting codes; database; functional dependency; key dependency; extremal problems of codes

Kategorie tematyczne

• 05D99: None of the above, but in this section
• 94B65: Bounds on codes
• 68P15: Database theory
• 94B25: Combinatorial codes

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2008
• Tom: 6
• Numer: 1
• Strony: 1-11

Daty

wydano

2008-03-01

online

2008-02-26

Twórcy

autor

Gyula Katona

• Hungarian Academy of Sciences

autor

Attila Sali

• Hungarian Academy of Sciences

autor

Klaus-Dieter Schewe

• Massey University

Bibliografia

• [1] Abiteboul S., Hull R., Vianu V., Foundations of databases, Addison-Wesley, 1995
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [10] Fagin R., Horn clauses and database dependencies, J. Assoc. Comput. Mach., 1982, 29, 952–985
• [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
• [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
• [13] Odlyzko A.M., Asymptotic enumeration methods, In: Graham R.L, Crbtschel M., Lovász L. (Eds.), Handbook of combinatorics, Elsevier, Amsterdam, 1995
• [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
• [15] Sali A., Schewe K.-D., Counter-free keys and functional dependencies in higher-order datamodels, Fund. Inform., 2006, 70, 277–301
• [16] Sali A., Schewe K.-D., Keys and Armstrong databases in trees with restructuring, Acta Cybernet., preprint
• [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)

Identyfikatory

DOI

10.2478/s11533-008-0001-4