New type of coding problem motivated by database theory

TitleNew type of coding problem motivated by database theory
Publication TypeJournal Article
AuthorsKatona, G. O. H., and A. Sali
Journal titleDiscrete Applied Mathematics
Year2004
Pages140 - 148
Volume144
Issue1-2
Abstract

The present paper is intended to survey the interaction between relational database theory and coding theory. In particular it is shown how an extremal problem for relational databases gives rise to a new type of coding problem. The former concerns minimal representation of branching dependencies that can be considered as a data mining type question. The extremal configurations involve d-distance sets in the space of disjoint pairs of k-element subsets of an n-element set X. Let X be an n-element finite set, 0 < k < n/2 an integer. Suppose that {A(1), B-1} and {A(2), B-2} are pairs of disjoint k-element subsets of X (that is, \A(1)\ = \B-1\ = \A(2)\ = \B-2\ = k, A(1) boolean AND B-1 = 0, A(2) boolean AND B-2 = 0). Define the distance of these pairs by d({A(1), B-1}, {A(2), B-2}) = min{\A(1) – A(2)\ + \B-1 – B-2\, \A(1) – B-2\ + \B-1 – A(2)\). (C) 2004 Elsevier B.V. All rights reserved.

Languageeng
Notes

Nov; New type of coding problem motivated by database theory

Publisher linkhttp://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6TYW-4D1DHN8-3-1&_cdi=5629&_user=7105836&_orig=browse&_coverDate=11%2F30%2F2004&_sk=998559998&view=c&wchp=dGLbVtb-zSkzk&md5=6632e5f0eb2adeab8be00b7f740f123a&ie=/sdarticle.pdf