Loading…

Complexity of Dependences in Bounded Domains, Armstrong Codes, and Generalizations

The study of Armstrong codes is motivated by the problem of understanding complexities of dependences in relational database systems, where attributes have bounded domains. A (q, k, n)-Armstrong code is a q-ary code of length n with minimum Hamming distance n - k + 1, and for any set of k - 1 coordi...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2015-02, Vol.61 (2), p.812-819
Main Authors: Chee, YM, Zhang, H, Zhang, X
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The study of Armstrong codes is motivated by the problem of understanding complexities of dependences in relational database systems, where attributes have bounded domains. A (q, k, n)-Armstrong code is a q-ary code of length n with minimum Hamming distance 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. In this paper, f (q, 3) = 3q -1 is determined for all q ≥ 5 with three possible exceptions. This disproves a conjecture of Sali. Furthermore, we introduce generalized Armstrong codes for branching, or (s, t)-dependences, construct several classes of optimal Armstrong codes, and establish lower bounds for the maximum length n in this more general setting.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2014.2377735