Publications of Sali, A.

New type of coding problem motivated by database theory

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.

Design type problems motivated by database theory

Let k less than or equal to n, p less than or equal to g<m be positive integers. Suppose that the m x n matrix M satisfies the following two properties: for any choice of k distinct columns c(1),c(2)....,ck, there are q + 1 rows such that the number of different entries in c(i) (1 less than or equal to i less than or equal to k-1) in these rows is at most p, while all q + 1 entries of c(k) in these rows are different; this is true for no choice of k + 1 distinct columns. We review results minimizing m, given n,p,q,k. Two of the results are new. The optimal or nearly optimal constructions can be considered as n partitions of the m-element set satisfying certain conditions. This version leads to the orthogonal double covers, also surveyed here. (C) 1998 Elsevier Science B.V. All rights reserved.