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 :

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) \thinspace \land \\ &\forall (\alpha, T) \in heading(S_1) \thinspace \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 :

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 :

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:

Dee

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

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) :

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

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:

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