Santa Fe DataBase Solutions

• FastTrack |
• Technology |
• Licensing |
• Contact |
• Site Map

PATH // www.sfdbs.com > Relationship Cardinality Types

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

cardinality	Child_Parent_fk		comment
	UNIQUE	NOT NULL
(0,1)-to-(0,M)	no	no	zero or more Child per Parent, not shared; orphans ok
1-to-(0,M)	no	yes	zero or more Child per Parent, not shared; no orphans
(0,1)-to-(0,1)	yes	no	zero or one Child per Parent, not shared; orphans ok
1-to-(0,1)	yes	yes	zero or one Child per Parent, not shared; no orphans

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

cardinality	Jnct_Parent_fk	Jnct_Child_fk	comment
	UNIQUE	UNIQUE
(0,M)-to-(0,M)	no	no	zero or more Child per Parent, shared; requires UNIQUE(Jnct_Parent_fk,Jnct_Child_fk)
(0,1)-to-(0,M)	no	yes	zero or more Child per Parent, not shared
(0,M)-to-(0,1)	yes	no	zero or one Child per Parent, shared
(0,1)-to-(0,1)	yes	yes	zero 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

row	cardinality	Aggregate_Parent_fk		Link_Aggregate_fk	Link_Child_fk	comment
		UNIQUE	NOT NULL	UNIQUE	UNIQUE
1	1-to-(0,1)	yes	yes	yes	yes	zero or one Child per Parent, not shared; one or more Parent per child; no orphans
2	(1,M)-to-(0,1)	yes	yes	yes	no	zero or one Child per Parent, shared; no orphans
3	1-to-(0,M)	yes	yes	no	yes	zero or more Child per Parent, not shared; no orphans
4	(1,M)-to-(0,M)	yes	yes	no	no	zero 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)	yes	no	yes	yes	zero or one Child per Parent, not shared; orphans ok
6	(0,M)-to-(0,1)	yes	no	yes	no	zero or one Child per Parent, shared; orphans ok
7	(0,1)-to-(0,M)	yes	no	no	yes	zero or more Child per Parent, not shared; orphans ok
8	(0,M)-to-(0,M)	yes	no	no	no	zero or more Child per Parent, shared; orphans ok; requires UNIQUE(Link_Aggregate_fk,Link_Child_fk)
9	Lattice(1)	no	yes	yes	yes	multiparents; zero or one Child per Parent, not shared; no orphans
10	Lattice(2)	no	yes	yes	no	multiparents; zero or one Child per Parent, shared; no orphans
11	Lattice(3)	no	yes	no	yes	multiparents; zero or more Child per Parent, not shared; no orphans
12	Lattice(4)	no	yes	no	no	multiparents; multichildren; no orphans
13	Lattice(5)	no	no	yes	yes	multiparents; zero or one Child per Parent, not shared; orphans ok
14	Lattice(6)	no	no	yes	no	multiparents; zero or one Child per Parent, shared; orphans ok
15	Lattice(7)	no	no	no	yes	multiparents; multiple children per Parent, not shared; orphans ok
16	Lattice(8)	no	no	no	no	multiparents; multichildren
17	Lattice(9)	yes	yes	no	no	zero or more Child per Parent, shared; no orphans; multichildren
18	Lattice(10)	yes	no	no	no	zero or more Child per Parent, shared; orphans ok; multichildren
19	Lattice(11)	no	yes	no	no	multiparents; zero or more Child per Parent; no orphans; requires UNIQUE(Link_Aggregate_fk,Link_Child_fk)
20	Lattice(12)	no	no	no	no	multiparents; 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