ERW: The Manual | ||
---|---|---|

<<< Previous | Overall System Design | Next >>> |

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:

if the first character is

`0`, it imposes no bound;if the first character is

`1`, it forces each entity to be in relation with at least another entity;if the second character is

`M`, it imposes no bound;if the second character is

`N`, then a multirelation instantiating the relationship type must be a relation, that is, it cannot happen that entities are related twice;if the second character is

`1`, it forces each entity of to be in relation with at most another entity (and it must be related once).

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

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 R

_{0}(r)=x;- monodrome (or a partial function)
if for each element x in X there is at most one r in R such that R

_{0}(r)=x;- surjective
if for each element y of Y there is at least one element r of R such that R

_{1}(r)=y.- injective
if for each element y of Y there is at most one element r of R such that R

_{1}(r)=y;- a relation
if there are no distinct elements r and s of R such that R

_{0}(r)=R_{0}(s) and R_{1}(r)=R_{1}(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.

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
(1: forces the
corresponding leg to be an surjective function; this definition is
equivalent to the one above.)x |

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 function | injective and surjective partial function | partial function | surjective partial function | ||

(1:1) | injective function | injective and surjective function | function | surjective function | ||

(0:N) | injective relation | injective and surjective relation | relation | surjective relation | ||

(1:N) | injective and total relation | injective and surjective total relation | total relation | total surjective relation | ||

(0:M) | multirelation | surjective multirelation | ||||

(1:M) | total multirelation | total 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.

<<< Previous | Home | Next >>> |

Overall System Design | Up | Weak Entities |