Publications of Demetrovics, J.

On the security of individual data

We will consider the following problem in this paper: Assume that there are n numerical data {x(1),x(2),.., x(n)} (like salaries of n individuals) stored in a database and some subsums of these numbers are made 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 x1; x2;...; xn 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 [ 1], originally solved by Miller et al. [ 7] and revisited by Griggs [ 4, 5]. It was shown in [ 7] 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. To calculate a subsum, it might need some operations whose number is limited. This is why 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. The goal of the present paper is to determine the maximum number of subsums of size at most k which can be disclosed without making possible to calculate any of the individual data x(i). The maximum is exactly determined for the case when the number of data is much larger than the size restriction k.

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.

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.

Asymptotic properties of keys and functional dependencies in random databases

Practical database applications give the impression that sets of constraints are rather small and that large sets are unusual and are caused by bad design decisions. Theoretical investigations, however, show that minimal constraint sets are potentially very large. Their size can be estimated to be exponential in terms of the number of attributes. The gap between observation in practice and theory results in the rejection of theoretical results. However, practice is related to average cases and is not related to worst cases. The theory used until now considered the worst-case complexity. This paper aims to develop a theory for the average-case complexity. Several probabilistic models and asymptotics of corresponding probabilities are investigated for random databases formed by independent random tuples with a common discrete distribution. Poisson approximations are studied for the distributions of some characteristics for such databases where the number of tuples is sufficiently large. We intend to prove that the exponential complexity of key sets and sets of functional dependencies is rather unusual and almost all minimal keys in a relation have a length which depends mainly on the size of the relation.

The average length of keys and functional dependencies in (random) databases

Practical database applications engender the impression that sets of constraints are rather small and that large sets are unusual and caused by bad design decisions. Theoretical investigations show, however, that minimal constraint sets are potentially very large. Their size can be estimated to be exponential in terms of the number of attributes. The gap between belief and theory causes non-acceptance of theoretical results. However, beliefs are related to average cases. The theory known so far considered worst case complexity. This paper aims at developing a theory of average case complexity. Several statistic models and asymptotics of corresponding probabilities are investigated for random databases. We show that exponential complexity of independent key sets and independent sets of functional dependencies is rather unusual. Depending on the size of relations almost all minimal keys have a length which mainly depends on the size. The number of minimal keys of other length is exponentially small compared with the number of minimal keys of the derived length. Further, if a key is valid in a relation then it is probably the minimal key. The same results hold for functional dependencies.

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.

On The Number Of Databases And Closure Operations

Closure operations are considered as models of databases. Estimates on the number of closure operations on n elements (or equivalently, on the number of databases with n attributes) are given.