Publications of Katona, G.O.H.

Functional dependencies distorted by errors

A relational database D is given with Q as the set of attributes. We assume that the rows (tuples, data of one individual) are transmitted through a noisy channel (or, as many times in case of the data mining applications, the observed data is distorted from the real values in a manner which we cannot know). In case of low probability of the error it may be supposed that at most one data in a row is changed by the transmission or observation. We say that A -> b (A subset of Omega, b epsilon Omega) is an error-correcting functional dependency if the data in A uniquely determine the data in b in spite of this error. We investigate the problem how much larger a minimal error-correcting functional dependency can be than the original one. We will give upper and lower bounds showing that it can be considerably larger than the original sizes, but the growth is only polynomial. (C) 2007 Elsevier B.V. All rights reserved.

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.

Bounds on maximal families of sets not containing three sets with A boolean AND B subset of C, A not subset of B

Lower and upper estimates are given on the size of a family of subsets of an n- element set containing no three distinct sets satisfying A boolean AND B subset of C, A not subset of B. This is a sharpening of an earlier result where the same question was solved under the condition that there are no three distinct sets such that A boolean AND B subset of C.

On the number of independent functional dependencies

We will investigate the following question: what can be the maximum number of independent functional dependencies in a database of n attributes, that is the maximum cardinality of a system of dependencies which which do not follow from the Armstrong axioms and none of them can be derived from the remaining ones using the Armstrong axioms. An easy and for long time believed to be the best construction is the following: take the maximum possible number of subsets of the attributes such that none of them contains the other one (by the wellknown theorem of Sperner [8] their number is (n / n/2)) and let them all determine all the further values. However, we will show ( n by a specific construction that it is possible to give more than (n / n/2) independent dependencies (the construction will give (I + 1 / n(2))(n / n/2) of them) and – on the other hand – the upper bound is 2(n) – 1, which is roughly root n(n / n/2).

Some contributions to the minimum representation problem of key systems

Some new and improved results on the minimum representation problem for key systems will be presented. By improving a lemma of the second author we obtain better or new results on badly representable key systems, such as showing the most badly representable key system known, namely of size 2(n(1-c.log n/ log n)), where n is the number of attributes. We also make an observation on a theorem of J. Demetrovics, Z. Furedi and the first author and give some new well representable key systems as well.

2-bases of quadruples

Let Beta(n, <= 4) denote the subsets of [n] := {1, 2,..., n} of at most 4 elements. Suppose that F is a set system with the property that every member of B can be written as a union of (at most) two members of F. (Such an F is called a 2-base of B.) Here we answer a question of Erdos proving that [GRAPHICS] and this bound is best possible for n >= 8.

Constructions via Hamiltonian theorems

Demetrovics et al [Design type problems motivated by database theory, J. Statist. Plann. Inference 72 (1998) 149-164] constructed a decomposition of the family of all k-element subsets of an n-element set into disjoint pairs (A, B) (A boolean AND B = 0, vertical bar A vertical bar = vertical bar B vertical bar = k) where two such pairs are relatively far from each other in some sense. The paper invented a proof method using a Hamiltonian-type theorem. The present paper gives a generalization of this tool, hopefully extending the power of the method. Problems where the method could be also used are shown. Moreover, open problems are listed which are related to the Hamiltonian theory. In these problems a cyclic permutation is to be found when certain restrictions are given by a family of k-element subsets. (c) 2005 Elsevier B.V. All rights reserved.

Largest family without A boolean OR B subset of C boolean AND D

Let F be a family of subsets of an n-element set not containing four distinct members such that A boolean OR B subset of C boolean AND D. It is proved that the maximum size of F under this condition is equal to the sum of the two largest binomial coefficients of order n. The maximum families are also characterized. A LYM-type inequality for such families is given, too. (c) 2005 Elsevier Inc. All rights reserved.

Preface

The 2002 Korea-Hungary Joint Workshop on Combinatorics and the 2002 Com(2)MaC Conference on Graphs and Combinatorics

On the security of individual data

We will consider the following problem in this paper: Assume there are n numeric data {x(1), x(2),..., x(n)} (like salaries of n individuals) stored in a database and some subsums of these numbers axe disclosed by making public or just available for persons not eligible to learn the original data. Our motivating question is: at most how many of these subsums may be disclosed such that none of the numbers x(1), x(2),...,x(n) can be uniquely determined from these sums. These types of problems arise in the cases when certain tasks concerning a database are done by subcontractors who are not eligible to learn the elements of the database, but naturally should be given some data to fulfill there task. In database theory such examples are called statistical databases as they are used for statistical purposes and no individual data are supposed to be obtained using a restricted list of SUM queries. This problem was originally introduced by Chin and Ozsoyoglu [1], originally solved by Miller et al. [5] and revisited by Griggs [4]. It turned out [5] that the problem is equivalent to the following question: If there are n real, non-zero numbers X = {x(1), x(2),..., x(n)} given, what is the maximum number of 0 subsums of it, that is, what is the maximum number of the subsets of X whose elements sum up to 0. This approach, together with the Sperner theorem shows that no more than ((n)(n/2)) subsums of a given set of secure data may be disclosed without disclosing at least one of the data, which upper bound is sharp as well. However, it is natural to assume that the disclosed subsums of the original elements of the database will contain only a limited number of elements, say at most k (in the applications databases are usually huge, while the number of operations is in most of the cases limited). We have now the same question: at most how many of these subsums of at most k members may be given such that none of the numbers x(1), x(2),...x(n) can be uniquely determined from these sums. The main result of this paper gives an upper bound on this number, which turns out to be sharp if we allow subsums of only k or k – 1 members and asymptotically sharp in case of subsums of at most k members.

Semantics in databases

Semantics in databases: second international workshop, Dagstuhl Castle, Germany, January 7-12, 2001 : revised papers

Search with small sets in presence of a liar

One unknown element of an n-element set is sought by asking if it is contained in given subsets. It is supposed that the question sets are of size at most k and all the questions are decided in advance, the choice of the next question cannot depend on previous answers. At most I of the answers can be incorrect. The minimum number of such questions is determined when the order of magnitude of k is n(alpha) with alpha < 1. The problem can be formulated as determination of the maximum sized l-error-correcting code (of length n) in which the number of ones in a given position is at most k. (C) 2002 Elsevier Science B.V. All rights reserved.

Error-correcting keys in relational databases

Suppose that the entries of a relational database are collected in an unreliable way, that is the actual database may differ from the true database in at most one data of each individual. An error-correcting key is such a set of attributes, that the knowledge of the actual data of an individual in this set of attributes uniquely determines the individual. It is showed that if the minimal keys are of size at most ii, then the smallest sizes of the minimal error-correcting keys can be ck(3) and this is the best possible, all minimal error-correcting keys have size at most 3k(3).

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.

External problems for finite sets and convex hulls – A survey

Let F be a family of distinct subsets of an n-element set. Define p(i)(F) (0 less than or equal to i less than or equal to n) as the number of i-element members of F. Consider the profile vectors (p(0)(F),...,p(n)(F)) for all families F belonging to a certain class A (e.g. A can be the class of all families where any two members have a non-empty intersection). Let epsilon(A) denote the set of extreme points of the convex hull of the set of these profile vectors. Results determining epsilon(A) for some classes A are surveyed. Facets and edges of these convex hulls are also described for some A. Connections to the classical extremal problems are shown.

A survey of some combinatorial results concerning functional dependencies in database relations

A databaseR has some obvious and less obvious parameters such as the number of attributes, the size |r|, the maximum size of a domain, the number of some special functional dependencies (e.g. the minimal keys), and so on. The main aim of this paper is to survey some of the results giving connections and inequalities among these parameters. The methods are of a combinatorial nature. A generalization of the numerical dependency is also considered.

Optimization Of The Reliability Polynomial In Presence Of Mediocre Elements

Some connections between extremal set theory and the optimization of the reliability polynomial are shown. Then the concept of the reliability polynomial is generalized for the case when the elements can have three different states: good, mediocre and bad. The state of the device can be described by a 0,1,2 sequence. Such a state is called operative if the device operates when its elements are in the states described by the sequence. The maximum of the generalized reliability polynomial is studied under the condition that the set of operative states forms an antichain.

Partial Dependencies In Relational Databases And Their Realization

Weakening the functional dependencies introduced by Amstrong we get the notion of the partial dependencies defined on the relational databases. We show that the partial dependencies can be characterized by the closure operations of the poset formed by the partial functions on the attributes of the databases. On the other hand, we give necessary and sufficient conditions so that for such a closure operation one can find on the given set of attributes a database whose partial dependencies generate the given closure operation. We also investigate some questions about how to realize certain structures related to databases by a database of minimal number of rows, columns or elements.

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.

Minimal 2-coverings of a finite affine space based on GF(2)

Let EG(m, 2) denote the m-dimensional finite Euclidean space (or geometry) based on GF(2), the finite field with elements 0 and 1. Let T be a set of points in this space, then T is said to form a q-covering (where q is an integer satisfying 1less-than-or-equals, slantqless-than-or-equals, slantm) of EG(m, 2) if and only if T has a nonempty intersection with every (m-q)-flat of EG(m, 2). This problem first arose in the statistical context of factorial search designs where it is known to have very important and wide ranging applications. Evidently, it is also useful to study this from the purely combinatorial point of view. In this paper, certain fundamental studies have been made for the case when q=2. Let N denote the size of the set T. Given N, we study the maximal value of m.