Behavior of keys in random databases

The wide class of stochastic models for databases was considered. The properties of key systems and functional dependencies in stochastic databases were investigated in the average case setting. Comparing with the worst case setting the exponential size of minimal key system is rather unusual in average. For several stochastic models the Poisson approximations of characteristics of the most probable minimal key candidates have been derived in terms of the Renyi entropies. The proposed general method of analysis is based on probabilistic and information theory results. As the first and necessary step for a statistical analysis, several probabilistic models for random tables and relations have been investigated. The outline of possible further practical applications may be as the follows (i) fitting the corresponding stochastic model; (ii) estimation of the model parameters for a given data; (iii) approximation and analysis of key system characteristics. Besides the considered discrete distributions, the Markovian model for stochastic dependencies and the corresponding multivariate normal approximations for discrete distributions can be considered. For the normal distribution, the well-known technique can be applied for the estimation of the model parameters.