Codes that attain minimum distance in every possible direction

Gyula Katona; Attila Sali; Klaus-Dieter Schewe

Open Mathematics (2008)

  • Volume: 6, Issue: 1, page 1-11
  • ISSN: 2391-5455

Abstract

top
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.

How to cite

top

Gyula Katona, Attila Sali, and Klaus-Dieter Schewe. "Codes that attain minimum distance in every possible direction." Open Mathematics 6.1 (2008): 1-11. <http://eudml.org/doc/269591>.

@article{GyulaKatona2008,
abstract = {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.},
author = {Gyula Katona, Attila Sali, Klaus-Dieter Schewe},
journal = {Open Mathematics},
keywords = {Error correcting codes; database; functional dependency; key dependency; extremal problems of codes},
language = {eng},
number = {1},
pages = {1-11},
title = {Codes that attain minimum distance in every possible direction},
url = {http://eudml.org/doc/269591},
volume = {6},
year = {2008},
}

TY - JOUR
AU - Gyula Katona
AU - Attila Sali
AU - Klaus-Dieter Schewe
TI - Codes that attain minimum distance in every possible direction
JO - Open Mathematics
PY - 2008
VL - 6
IS - 1
SP - 1
EP - 11
AB - 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.
LA - eng
KW - Error correcting codes; database; functional dependency; key dependency; extremal problems of codes
UR - http://eudml.org/doc/269591
ER -

References

top
  1. [1] Abiteboul S., Hull R., Vianu V., Foundations of databases, Addison-Wesley, 1995 Zbl0848.68031
  2. [2] Armstrong W.W., Dependency structures of data base relationships, Information Processing, 1974, 74, 580–583 
  3. [3] Demetrovics J., On the equivalence of candidate keys with Sperner systems, Acta Cybernet., 1978/79, 4, 247–252 Zbl0427.68072
  4. [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 Zbl0577.68084
  5. [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 Zbl0526.06004
  6. [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 Zbl0466.68086
  7. [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 Zbl0767.68030
  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 Zbl0932.68038
  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 Zbl1034.68513
  10. [10] Fagin R., Horn clauses and database dependencies, J. Assoc. Comput. Mach., 1982, 29, 952–985 Zbl0493.68092
  11. [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 Zbl0738.05071
  12. [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 Zbl1202.68141
  13. [13] Odlyzko A.M., Asymptotic enumeration methods, In: Graham R.L, Crbtschel M., Lovász L. (Eds.), Handbook of combinatorics, Elsevier, Amsterdam, 1995 Zbl0845.05005
  14. [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 Zbl1202.68149
  15. [15] Sali A., Schewe K.-D., Counter-free keys and functional dependencies in higher-order datamodels, Fund. Inform., 2006, 70, 277–301 Zbl1101.68526
  16. [16] Sali A., Schewe K.-D., Keys and Armstrong databases in trees with restructuring, Acta Cybernet., preprint Zbl1164.68335
  17. [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. [18] Turán P., On an extremal problem in graph theory, Mat. Fiz. Lapok, 1941, 48, 436–452 (in Hungarian) 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.