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...
Saved in:
Published in: | IEEE transactions on information theory 2015-02, Vol.61 (2), p.812-819 |
---|---|
Main Authors: | , , |
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!
|
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 |