Complexity of dependencies in bounded domains, Armstrong Codes, and generalizations
Yeow Meng Chee, Hui Zhang, Xiande Zhang · 2013
The study of Armstrong codes is motivated by the problem of understanding complexities of dependencies 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. Further, we introduce generalized Armstrong codes for branching, or (s, t)-dependencies and construct several classes of optimal Armstrong codes in this more general setting.