Publications of Sali, A.

Codes that attain minimum distance in every possible direction

The following problem motivated by investigation of databases is studied. Let C be a q-ary code of length n with the properties that C has minimum distance at least 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. f(q, k) is bounded by linear functions of k and q, and the exact values for special k and q are determined.

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.

Anstee R, Demetrovics J, Katona GO, Sali A. Low discrepancy allocation of two-dimensional data. In: Schewe KD, Thalheim B, editors. Foundations of Information and Knowledge Systems. Vol 1762. Berlin: Springer; 2000. p. 1-12. Abstract

Low discrepancy allocation of two-dimensional data

Fast browsing and retrieval of geographically referenced information requires the allocation of data on different storage devices for concurrent retrieval. By dividing the two-dimensional space into tiles, a system can allow users to specify regions of interest using a query rectangle and then retrieving information related to tiles covered by the query. Suppose that there are m I/O devices. A tile is labeled by i if the data corresponding to this area is stored in the ith I/O device. A labeling is efficient if the difference of the numbers of occurrences of distinct labels in any given rectangle is small. Except for some simple cases this discrepancy exceeds i. In the present paper constructions are given to make this discrepancy small relative to m. The constructions use latin squares and a lower bound is given, which shows that the constructions are best possible under certain conditions.

Demetrovics J, Katona GO, Sali A. Design type problems motivated by database theory. Journal of Statistical Planning and Inference. 1998;72(1-2):149-64. Abstract

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.

Hajnal A, Katona GO, Sali A. Preface. Discrete Mathematics. 1996;150(1-3):1-3. Abstract

Preface

Selected papers in honour of Paul Erdos on the occasion of his 80th birthday

The Characterization Of Branching Dependencies

A new type of dependencies in a relational database model is introduced. If b is an attribute, A is a set of attributes then it is said that b (p,q)-depends on A, in notation [GRAPHICS], in a database r if there are no q + 1 rows in r such that they have at most p different values in A, but q + 1 different values in b. (1,1)-dependency is the classical functional dependency. Let J(A) denote the set [GRAPHICS]. The set function J(A) is characterized if p=1, 1<q; p=2, 3<q; 2<p, p2-p-1<q. Implications among (p,q)-dependencies are also determined.