ASYMPTOTIC PROPERTIES OF KEYS AND FUNCTIONAL-DEPENDENCIES IN RANDOM DATABASES

Practical database applications give the impression that sets of const raints are rather small and that large sets are unusual and are caused by bad design decisions. Theoretical investigations, however, show th at minimal constraint sets are potentially very large. Their size can be estimated to be exponential in terms of the number of attributes. T he gap between observation in practice and theory results in the rejec tion of theoretical results. However, practice is related to average c ases and is not related to worst cases. The theory used until now cons idered the worst-case complexity. This paper aims to develop a theory for the average-case complexity. Several probabilistic models and asym ptotics of corresponding probabilities are investigated for random dat abases formed by independent random tuples with a common discrete dist ribution. 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 mai nly on the size of the relation.