Relationship Cardinality Types

Database designers classify relationships by cardinality, an imprecise term that refers to the minimum and maximum number of child tuples related to one parent tuple and the minimum and maximum number of parent tuples related to one child tuple. (There is no agreed upon naming convention for different cardinalities. The Object Management Group's Unified Modelling Language (UML) is an attempt at standardization for names and graphical representation of relationship cardinality types.)

In an SQL RDBMS, the cardinality of a relationship type is determined by the UNIQUE / NOT UNIQUE and NULL / NOT NULL integrity constraints declared by the database designer on the foreign keys in the relation schema and enforced by the RDBMS. There are 2**2=4 combinations of these two integrity constraints that can be declared for each foreign key. With one-, two- and three foreign keys respectively, the Primary Key / Foreign Key (PKFK), Junction Table (JT) and Aggregate-Link (A-L) representations could potentially admit 4**1=4, 4**2=16 and 4**3=64 different relationship types respectively. However, NULL foreign key values can be ambiguous for JT and A-L, so that the actual number of effective types for PKFK, JT and A-L are 4, 4 and 20 respectively. Some of the A-L relationship types cannot be represented at all with the more traditional PKFK and JT representations.

The Primary Key / Foreign Key Relationship Cardinality Types

Figure 1 depicts the most widely used database data structure for representing relationships between one tuple in a Parent relation and zero or more tuples in a second (or the same) Child relation. We refer to this as the Primary Key / Foreign Key or PKFK representation. In addition to the relationship between the Parent tuple and Child tuple, there is an implicit sibling relationship among all Child tuples with the same parent.

Figure 1. The PKFK Representation

Table 1. Primary Key / Foreign Key Relationship Cardinality
cardinalityChild_Parent_fkcomment
UNIQUENOT NULL
(0,1)-to-(0,M)nonozero or more Child per Parent, not shared; orphans ok
1-to-(0,M)noyeszero or more Child per Parent, not shared; no orphans
(0,1)-to-(0,1)yesnozero or one Child per Parent, not shared; orphans ok
1-to-(0,1)yesyeszero or one Child per Parent, not shared; no orphans
NOTATION: We use the convention that a relationship between relations P and C has cardinality "(minP,maxP)-to-(minC,maxC)" if one parent tuple P can be related to as few as minC child tuples and as many as maxC, and one child tuple C can be related to as few as minP and as many as maxP parent tuples. A term like "(minX,maxX)" reduces to "N" if minP = maxP = N. A relationship of cardinality (0,1)-to-(0,M) admits zero or more child tuples per parent tuple and zero or one parent tuples per child, whereas a relationship of cardinality 1-to-(0,M) admits exactly one parent per child. (The parent may be shared among several children, but no child can be parentless.)

The Junction Table Relationship Cardinality Types

In the PKFK representation, the single foreign key in the Child relation implies that a Child tuple can be related to at most one Parent tuple. To relate a Child tuple to multiple Parent tuples and vice versa, the Junction Table or JT representation is used. Figure 2 depicts the JT representation.

Figure 2. The JT (Junction Table) Representation

Table 2. Junction Table Relationship Cardinality
cardinalityJnct_Parent_fkJnct_Child_fkcomment
UNIQUEUNIQUE
(0,M)-to-(0,M)nonozero or more Child per Parent, shared; requires UNIQUE(Jnct_Parent_fk,Jnct_Child_fk)
(0,1)-to-(0,M)noyeszero or more Child per Parent, not shared
(0,M)-to-(0,1)yesnozero or one Child per Parent, shared
(0,1)-to-(0,1)yesyeszero or one Child per Parent, not shared

The primary key Jnct_pk in the Junction Table can be omitted, in which case the composite key (Jnct_Parent_fk,Jnct_Child_fk) is the primary key and must be declared UNIQUE. If Jnct_pk is omitted and the composite key not declared UNIQUE, the RDBMS will assign (and value) an invisible primary key attribute, implying that duplicate (Jnct_Parent_fk,Jnct_Child_fk) value pairs are allowed. (This is not usually what is desired.) If the composite (Jnct_Parent_fk,Jnct_Child_fk) is declared UNIQUE but not declared as the primary key, the RDBMS will allow NULL values for one or both foreign keys. (Also not usually desired.) NULLs are prohibited in primary keys, but allowed in composite "candidate" keys.

With two foreign key fields, the Junction Table representation potentially provides 4 x 4 = 16 cardinality types. (Each foreign key could be declared UNIQUE / NOT UNIQUE and NOT NULL / NULL, a total of 4 combinations.) However, a NULL value in either foreign key field of the Junction Table tuple is ambiguous. For example, a tuple (NULL, X) could imply that the child tuple has no parent, but there are no integrity constraints that would allow for (0,M)-to-(0,M) cardinality and still prevent tuple (Y, X) from appearing also in the Junction Table. What would be the interpretation in that case? What would be the interpretation of (NULL, NULL)? Both foreign keys Jnct_Parent_fk and Jnct_Child_fk should be declared NOT NULL.

To avoid ambiguity, only the 4 relationship cardinality types in Table 2 can actually be represented with JT.

The Aggregate-Link Relationship Cardinality Types

The Aggregate-Link (A-L) schema is a new method for representing relationships. Figure 3 depicts it schematically.

Figure 3. The Aggregate-Link Representation

The following table lists the valid combinations of integrity constraint on the 3 foreign keys in the A-L representation: Aggregate_Parent_fk, Link_Aggregate_fk, Link_Child_fk:

Table 3. Aggregate-Link Relationship Cardinality
rowcardinalityAggregate_Parent_fkLink_Aggregate_fkLink_Child_fkcomment
UNIQUENOT NULLUNIQUEUNIQUE
11-to-(0,1)yesyesyesyeszero or one Child per Parent, not shared; one or more Parent per child; no orphans
2(1,M)-to-(0,1)yesyesyesnozero or one Child per Parent, shared; no orphans
31-to-(0,M)yesyesnoyeszero or more Child per Parent, not shared; no orphans
4(1,M)-to-(0,M)yesyesnonozero or more Child per Parent, shared; one or more Parent per Child; no orphans; requires UNIQUE(Link_Aggregate_fk,Link_Child_fk)
5(0,1)-to-(0,1)yesnoyesyeszero or one Child per Parent, not shared; orphans ok
6(0,M)-to-(0,1)yesnoyesnozero or one Child per Parent, shared; orphans ok
7(0,1)-to-(0,M)yesnonoyeszero or more Child per Parent, not shared; orphans ok
8(0,M)-to-(0,M)yesnononozero or more Child per Parent, shared; orphans ok; requires UNIQUE(Link_Aggregate_fk,Link_Child_fk)
9Lattice(1)noyesyesyesmultiparents; zero or one Child per Parent, not shared; no orphans
10Lattice(2)noyesyesnomultiparents; zero or one Child per Parent, shared; no orphans
11Lattice(3)noyesnoyesmultiparents; zero or more Child per Parent, not shared; no orphans
12Lattice(4)noyesnonomultiparents; multichildren; no orphans
13Lattice(5)nonoyesyesmultiparents; zero or one Child per Parent, not shared; orphans ok
14Lattice(6)nonoyesnomultiparents; zero or one Child per Parent, shared; orphans ok
15Lattice(7)nononoyesmultiparents; multiple children per Parent, not shared; orphans ok
16Lattice(8)nonononomultiparents; multichildren
17Lattice(9)yesyesnonozero or more Child per Parent, shared; no orphans; multichildren
18Lattice(10)yesnononozero or more Child per Parent, shared; orphans ok; multichildren
19Lattice(11)noyesnonomultiparents; zero or more Child per Parent; no orphans; requires UNIQUE(Link_Aggregate_fk,Link_Child_fk)
20Lattice(12)nonononomultiparents; zero or more Child per Parent; requires UNIQUE(Link_Aggregate_fk,Link_Child_fk)

Notice that rows 1-8 and 17-18 have Aggregate_Parent_fk UNIQUE. If Aggregate_Parent_fk is NOT UNIQUE (rows 9-16, 19-20), then the same Parent tuple can be parent to more than one group of child tuples. We refer to these as "lattice" relationship types.

If Link_Aggregate_fk and Link_Child_fk are both declared NOT UNIQUE, then the composite key (Link_Aggregate_fk, Link_Child_fk) may or may not be UNIQUE. If (Link_Aggregate_fk, Link_Child_fk) is not UNIQUE, then the same child tuple can occur more than once as a child linked to a single Aggregate tuple. This is another lattice relationship type. Notice than in the most unrestricted case (row 16, no integrity constraints on any foreign key), a parent tuple can occur multiple times as a parent and a child tuple can occur multiple times as child to a parent.

With 3 foreign keys, the Aggregate-Link representation could potentially provide 4 x 4 x 4 = 64 cardinality types. However, foreign key attributes Link_Aggregate_fk and Link_Child_fk should not allow NULLs. (A NULL Link_Aggregate_fk would imply a Link tuple unconnected to any Aggregate tuple. If the intent is that the parent is NULL, this is handled with a NULL Aggregate_Parent_fk. A NULL Link_Child_fk would imply a NULL child. What would that mean?) That would seem to imply 4 x 2 x 2 = 16 integrity constraint combinations, but there are 4 additional variants of Aggregate_Parent_fk for the case where both Link_Aggregate_fk and Link_Child_fk are NOT UNIQUE but the composite (Link_Aggregate_fk, Link_Child_fk) is UNIQUE.

The value of lattice relationships has not been explored.

Page Content first published: November 13, 2007
Page Content last updated: November 13, 2007