On Sampling Representatives of Relational Schemas with a Functional Dependency
Authors
Maximilian Berens, Joachim Biskup
Abstract
We further contribute to numerous efforts to provide tools for generating sample database instances, complement a recent approach to achieve a uniform probability distribution over all samples of a specified size, and add new insight to the impact of schema normalization for a relational schema with one functional dependency and size restrictions on the attribute domains. These achievements result from studying the problem how to probabilistically generate a relation instance that is a representative of a class of equivalent or similar instances, respectively. An instance is equivalent to another instance if there are bijective domain mappings under which the former one is mapped on the other one. An instance is similar to another instance if they share the same combinatorial counting properties that can be understood as a solution to a layered system of equalities and lessthan-relationships among (non-negative) integer variables and some (non-negative) integer constants. For a normalized schema, the two notions turn out to coincide. Based on this result, we conceptually design and formally verify a probabilistic generation procedure that provides a random representative of a randomly selected class, i.e., each class is represented with the same probability or, alternatively, with the probability reflecting the number of its members. We also discuss the performance of a prototype implementation and further optimizations. For a non-normalized schema, however, the coincidence of the respective notions does not hold. So we only present some basic features of these notions, including a relationship to set unification.