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 -Armstrong code is a -ary code of length with minimum Hamming distance , and for any set of coordinates, there exist two codewords that agree exactly there. Let be the maximum for which such a code exists. In this paper, is determined for all with three possible exceptions. This disproves a conjecture of Sali. Furthermore, we introduce generalized Armstrong codes for branching, or -dependences, construct several classes of optimal Armstrong codes, and establish lower bounds for the maximum length in this more general setting.