Abstract
Bounded cardinality occurs when the cardinality of a relationship is within a specified range. Bounded cardinality is closely linked to symmetric relationships. This article describes these two notions, notes some of the problems they present, and discusses their implementation in a relational database.
TopBounded Cardinality And Symmetric Relationships
Bounded Cardinality
An entity relationship diagram (ERD) shows the cardinality of each entity in a relationship. In an ERD, minimum cardinalities can be either 0 or 1, and maximum cardinalities can be 1 or infinity. Bounded cardinality occurs when a relationship between entities has cardinality within a specified range. Problems displaying bounded cardinality might include team rosters that must have exactly 5, 9, 11, or some other number of players. Figure 1 illustrates how UML (unified modeling language) provides for modeling specified-range relationships in a class diagram (Dennis, Wixom, & Tegarden, 2005). ERD, as described by Chen (1976), does not, although there are extensions to the ERD model that do (Webre, 1981). The SQL-92 standard provides for such constraints, but many relational database management systems (RDBMSs) do not support these features, and consequently do not allow for easy implementation of such a constraint (Lewis, Bernstein, & Kifer, 2002).
Figure 1. Specified range / bounded cardinality
Bounded cardinality presents some interesting problems. For example, Boufares and Kraïem (2001) point out that cardinality constraints may result in conflicts. Figure 2 illustrates one of their examples. In Figure 2, if we let ei be the number of instances of entity Ei and ri be the number of instances of relationship Ri, then we get the following constraints.
r1 =
e1r1 >
e2r2 <
e2r2 > 2
e1Figure 2. Inconsistent cardinality constraints
These lead in turn to e1 > e2 and e2 > 2 e1. Clearly these allow only the solution e1 = e2 =0, that is, an empty database. Boufares and Bennaceur (2004) offer a mathematical programming technique to detect inconsistent constraints.
Key Terms in this Chapter
Specified Range: UML term used to describe bounded cardinality in class diagrams.
Relationship: An association between entities.
Multiset: A collection in which elements may occur more than once.
Relation: For sets A and B, a relation R is a subset of the Cartesian product AXB, that is, R ? {(a, b)/a ? A, b ? B}. The relation may be written R(a,b) indicating that (a,b) is in R.
Procedural Constraint Support: Implementation of a constraint on a database via a procedure.
Bounded Cardinality: A specific finite upper and/or lower bound on the cardinality of a relationship between entities.
Reflexive Relation: If R is a relation on A, then a in A implies R(a,a). Sometimes it is erroneously used as a synonym for a symmetric relation.
Symmetric Relation: If R is a relation on AXA, then R is symmetric if and only if R(a,b) implies R(b,a).
Declarative Constraint Support: The ability of a database engine to implement constraints as part of the definition of the schema.
Semantic Constraint: In contrast to a structural constraint, a constraint that does not place a limit on the database structure.
Cardinality: The number of instances of an entity associated with a relationship.