Relational Model

Notes on relational model

Tuples

A tuple is an unordered set of triplets (also called components) consisting of attribute names, types, and values $\{ (\alpha_1, T_1, v_1), (\alpha_2, T_2, v_2), ..., (\alpha_i, T_i, v_i) \}$. It loosely corresponds to the concept of a “row” in SQL. A tuple is also a functional mapping from attributes to their respective values.

Given a tuple $S$:

• Attribute names are unique: $\vert \{ \alpha \mid (\alpha, T, v) \in S \} \vert = \vert S \vert$
• The values of each triplet are of the right type: $\forall (\alpha, T, v) \in S \bullet v \in T$

A pair $(\alpha, T)$ is an attribute of a tuple $S$ if the tuple has a matching triplet: $\exists v \bullet (\alpha, T, v) \in S$. The set of all attributes of a tuple $S$ is the heading of $S$.

The type of a tuple of determined by its heading. Two tuples $S_1$ and $S_2$ are of the same type iff $heading(S_1) = heading(S_2)$.

Every subset of a tuple is also a valid tuple, including the empty set (the zero-tuple).

Degree (or Arity)

The arity or degree of a tuple $S$ is its set cardinality, which corresponds to the number of triplets it contains.

Notice that the degree of a tuple $S$ is also equal to the set cardinality of its heading: $degree(S) = \vert heading(S) \vert$.

Equality

Two tuples $S_1$ and $S_2$ are considered equal if they share the same heading and attribute values:

$$\begin{align} S_1 = S_2 \iff &heading(S_1) = heading(S_2) \land \\ &\forall (\alpha, T) \in heading(S_1) \exists v \in T \bullet (\alpha, T, v) \in S_1 \land (\alpha, T, v) \in S_2 \end{align}$$

Zero Tuple

The unique tuple with arity zero is called the nullary or zero tuple. Its heading is the empty set: $heading(\emptyset) = \emptyset$.

Attributes

An attribute is a pair $(\alpha, T)$ where $\alpha$ is the attribute name and $T$ corresponds to its type.

Closure

Given a relation $R$ and a set of attributes $M \subseteq heading(R)$, the closure $M^{+}$ of $M$ under a set of functional dependencies $S$ is the family union of all the attributes that are dependent of $M$ in $S^{+}$: $M^{+} = \bigcup \{ \alpha \mid (M \rightarrow \alpha) \in S^{+} \}$.

If $M^{+} = heading(R)$ then $M$ is a super key for $R$.

Headings

A heading is a set of attributes $\{ (\alpha_1, T_1), (\alpha_2, T_2), ..., (\alpha_i, T_i) \}$. The heading of a tuple $S$ determines the type of the tuple and its equal to its set of attributes: $heading(S) = \{ (\alpha, T) \mid (\alpha, T, v) \in S \}$.

Given a heading $H$:

• Attribute names are unique: $\vert dom(H) \vert = \vert H \vert$
• All subsets of a heading $H$ are also valid headings

Relations

A relation is an object $(H, B)$ containing a heading and a body where the body is an unordered set of tuples (which means no duplicates), and where $heading(H, B) = H$ and $body(H, B) = B$. The type of a relation is determined by the type of its heading.

Given a relation $R$:

• Each tuple’s heading matches the relation heading: $\forall S \in body(R) \bullet heading(S) = heading(R)$
• Every subset of $body(R)$ is also a valid body

Keys

Super Keys

Given a relation $R$, a set of attributes $M \subseteq heading(R)$ is a super key for $R$ if all the attributes of $R$ are funtionally dependent on $M$. More formally: $M \rightarrow heading(R)$.

In terms of candidate keys, super keys are sets of attributes that contain some candidate key as a subset.

Candidate Keys

A candidate key is an irreducible super key. Given a relation $R$, a set of attributes $M \subseteq heading(R)$ is a candidate key for $R$ it is the minimal $M \subseteq heading(R)$ such that $M \rightarrow heading(R)$.

Operations

Cardinality

The cardinality of a relation $R$ is equal to the cardinality of its body: $\vert R \vert = \vert body(R) \vert$.

Degree (or Arity)

The arity or degree of a relation $R$ is equal to the arity of its heading: $degree(R) = degree(heading(R))$.

Membership

Given relation $R$ and tuple $S$, we may use the set membership operator to express that a relation contains a tuple in its body: $S \in R \iff S \in body(R)$.

Equality

Two relations $R_1$ and $R_2$ are considered equal if they have the same heading (i.e. they are of the same type) and the same body: $R_1 = R_2 \iff heading(R_1) = heading(R_2) \land body(R_1) = body(R_2)$.

Subset

A relation $R_1$ is a subset of another relation $R_2$ if they have the same type (i.e. they share the same heading) and the body of $R_1$ is a subset of the body of $R_2$: $R_1 \subseteq R_2 \iff heading(R_1) = heading(R_2) \land body(R_1) \subseteq body(R_2)$.

Special Relations

Dum

The special relation $Dum$ contains an empty heading and an empty body:

• $heading(Dum) = \emptyset$
• $body(Dum) = \emptyset$
• $degree(Dum) = 0$

Dee

The special relation $Dee$ contains an empty heading and a body containing the empty tuple, which matches the type of the empty heading:

• $heading(Dee) = \emptyset$
• $body(Dee) = \{ \emptyset \}$
• $degree(Dee) = 0$

The relation $Dee$ can only have at most the empty tuple as an element.

Functional Dependency

Given a relation $R$ and two sets of attributes $X \subseteq heading(R)$ and $Y \subseteq heading(R)$, the functional dependency $X \rightarrow Y$ means that in $R$ the values of $Y$ are determined by the values of $X$. The set of attributes at the left hand side of the arrow ($X$) is called the determinant, and the other set of attributes ($Y$) is called the dependent.

Trivial Dependencies

A functional dependency $X \rightarrow Y$ is trivial if its dependent is a subset of its determinant: $Y \subseteq X$. For example: $\{ P, Q \} \rightarrow \{ P \}$.

Armstrong’s Axioms (Inference Rules)

Also called inference rules, are a set of primary rules to infer new functional dependencies from an existing set of functional dependencies. Given relation $R$ and $A, B, C \subseteq heading(R)$:

• Reflexivity: If $B \subseteq A$, then $A \rightarrow B$
• Augmentation: If $A \rightarrow B$, then $(A \cup C) \rightarrow (B \cup C)$
• Transitivity: If $A \rightarrow B$ and $B \rightarrow C$, then $A \rightarrow C$

The following additional inference rules are derived from the primary rules:

• Decomposition: If $A \rightarrow (B \cup C)$, then $A \rightarrow B$ and $A \rightarrow C$
• Union: If $A \rightarrow B$ and $A \rightarrow C$, then $A \rightarrow (B \cup C)$
• Composition: If $A \rightarrow B$ and $C \rightarrow D$, then $(A \cup C) \rightarrow (B \cup D)$
• Self-determination: $A \rightarrow A$

General Unification Theorem

The theorem states that if $A \rightarrow B$ and $C \rightarrow D$, then $(A \cup (C \setminus B)) \rightarrow (B \cup D)$.

Closure

The closure of functional dependency of a set of functional dependencies $S$ is denoted $S^{+}$, and it corresponds to the union of $S$ and the functional dependencies that are derived from $S$.

Cover

Given two sets of functional dependencies $P$ and $Q$ for a given relation, $Q$ is a cover for $P$ if $P^{+} \subseteq Q^{+}$.

Equivalence

Given two sets of functional dependencies $P$ and $Q$ for a given relation, $P$ is equivalent to $Q$ if $P^{+} = Q^{+}$, which means that $P$ is a cover for $Q$ and $Q$ is a cover for $P$.

Irreducibility

A set of functional dependencies $S$ is irreducible (also called minimal) if and only if:

• The dependent of every functional dependency in $S$ involves only one attribute (has cardinality 1)
• Removing any functional dependency from $S$ affects $S^{+}$
• All the functional dependencies are left irreducible, which means that removing any attributes from their determinant affects $S^{+}$

Every set of functional dependencies has at least one equivalent set that is irreducible. These sets are called irreducible equivalents.