Cardinality Constraints

An important feature of entity-relationship schemata is the possibility of specifying cardinality constraints. These are instructions of the form "every person has exactly one mother", or "every document must have at least an author (but possibly many)". There constraints are useful because they allow to maintain the logical integrity of the database: in a logically integral database, you can always trust a document to have an author, and you can avoid to check if it is missing. ERW maintains automatically the logical integrity of your database.

An important point (often missed) about logical integrity is that it is a feature of the semantics of the entity-relationship schema, not of the underlying relational database. It must be expressed abstractly in term of properties of multirelations, and not in term of the particular relational implementation of the entity-relationship schema.

ERW uses a slight extension of the standard way of giving cardinality constraints on relations (as it has to handle multirelations). Recall that each relationship type is an arc going from an entity type (the source) to another entity type (the target). Cardinality constraints restrain the possible multirelation that an instance can assign to the relationship type. For each of the two entity types you can specify a pair of indices between parentheses and separated by colon, as in (1:N). The left character may be 0 or 1, while the right character may be 1, N, or M.

The specifiers assigned to a relationship provides restrictions on the cardinality (i.e., the number of elements) of certain relationships in an instance of the schema. More precisely:

In other words, the first index is a lower bound on the cardinality of relationships involving an entity, while the second index is a sort of upper bound. There are some standard names: if the two pairs of indices are of the form (x:1), then the relationship type is said to be one-to-one; if one is of the form (x:1) and the other of the form (x:N), then the relationship type is said to be one-to-many; finally, if the two pairs are of the form (x:N), then the relationship type is said to be many-to-many.

However, relations satisfying the restrictions above have standard mathematical names, which we will use in what follows. More precisely, we shall use the obvious extensions of these names to multirelations. A multirelation R from X to Y is said to be:

total

if for each element x in X there is at least one r in R such that R0(r)=x;

monodrome (or a partial function)

if for each element x in X there is at most one r in R such that R0(r)=x;

surjective

if for each element y of Y there is at least one element r of R such that R1(r)=y.

injective

if for each element y of Y there is at most one element r of R such that R1(r)=y;

a relation

if there are no distinct elements r and s of R such that R0(r)=R0(s) and R1(r)=R1(s).

Intuitively, a multirelation is total when every element of its source is related to something; it is monodrome if every element of its source is related (once) with at most one element of its target; it is injective if every element of its target is related (once) to at most one element of its source; it is surjective if every element of its target is related to something; and it is a relation if elements are never related twice.

These properties are strictly related: a multirelation is total if and only if its transpose is surjective, and it is monodrome if and only if its transpose is injective; finally, it is a relation if and only if its transpose is.

Note

If you look back carefully, you will notice that the cardinality constraints of a relationship type associated to the source and target entity types are really expressed in terms of the legs of multirelations: indeed, cardinality constraints have nothing to do with the entity types; they are a purely set-theoretical feature of the multirelations instantiating a relationship type. One could equivalently say that a constraint of the form (x:1) forces the corresponding leg to be an injective function, and that a constraint of the form (1:x) forces the corresponding leg to be an surjective function; this definition is equivalent to the one above.

All in all, noting that a monodrome total relation is commonly called a function, we have the following table assigning standard mathematical term to the cardinality constraints specified on the source entity types (rows) and on the target entity types (columns):

 (0:1)(1:1)(0:N)(1:N)(0:M)(1:M)
(0:1)injective partial functioninjective and surjective partial functionpartial functionsurjective partial function  
(1:1)injective functioninjective and surjective functionfunctionsurjective function  
(0:N)injective relationinjective and surjective relationrelationsurjective relation  
(1:N)injective and total relationinjective and surjective total relationtotal relationtotal surjective relation  
(0:M)    multirelationsurjective multirelation
(1:M)    total multirelationtotal surjective multirelation

The empty places represent impossible combinations. Note that if you exchange the two pairs of indices, you obtain the cardinality constraints on the transpose of the multirelation. Thus, if a multirelation has to be an injective relation, its transpose has to be a partial function, and viceversa.