Relational Schemas with Multiplicity Bounds, Diversity Bounds and Functional Dependencies

As yet another semantically enriched data model, we consider relational schemas with finite domain sizes and multiplicity bounds and diversity bounds together with functional dependencies as semantic constraints. As a simple variant of cardinality constraints, for a set of attributes, a multiplicity bound requires that a possible value combination occurs at most as often as the bound extension says. As a new kind of constraint, for a set of attributes, a diversity bound describes how many different value combinations under these attributes may at most occur in a relation instance. A multiplicity bound and a diversity bound together are seen as a weak abstraction of a so-called structure for the set of attributes on the left-hand side of a functional dependency. Such a structure specifies the exact size of the active domain of that set and the respective exact numbers of occurrences, summing up to a given instance size. We study how multiplicity bounds, diversity bounds and functional dependencies under finite sizes of attribute domains interact. We exhibit a powerful sound derivation system for all these items, together with a generation procedure for approximating the entailment closure of such constraints. We further analyze how to construct relation instances that exactly achieve the strongest entailed multiplicity or diversity bound extension, respectively, for some attribute set or even all of them.