Editing Relational model (section)

== Set-theoretic formulation ==
{{unreferenced section|date=December 2023}}
Basic notions in the relational model are ''[[relation (database)|relation]] names'' and ''attribute names''. We will represent these as strings such as "Person" and "name" and we will usually use the variables <math>r, s, t, \ldots</math> and <math>a, b, c</math> to range over them. Another basic notion is the set of ''atomic values'' that contains values such as numbers and strings.

Our first definition concerns the notion of ''tuple'', which formalizes the notion of row or record in a table:

; [[Tuple]]
: A tuple is a [[partial function]] from attribute names to atomic values.
; Header
: A header is a finite set of attribute names.
; [[Projection (relational algebra)|Projection]]
: The projection of a tuple <math>t</math> on a [[finite set]] of attributes <math>A</math> is <math>t[A] = \{ (a, v) : (a, v) \in t, a \in A \}</math>.

The next definition defines ''relation'' that formalizes the contents of a table as it is defined in the relational model.

; [[Relation (database)|Relation]]
: A relation is a tuple <math>(H, B)</math> with <math>H</math>, the header, and <math>B</math>, the body, a set of tuples that all have the domain <math>H</math>.

Such a relation closely corresponds to what is usually called the extension of a predicate in [[first-order logic]] except that here we identify the places in the predicate with attribute names. Usually in the relational model a [[logical schema|database schema]] is said to consist of a set of relation names, the headers that are associated with these names and the [[constraint (database)|constraints]] that should hold for every instance of the database schema.

; Relation universe
: A relation universe <math>U</math> over a header <math>H</math> is a non-empty set of relations with header <math>H</math>.
; Relation schema
: A relation schema <math>(H, C)</math> consists of a header <math>H</math> and a predicate <math>C(R)</math> that is defined for all relations <math>R</math> with header <math>H</math>. A relation satisfies a relation schema <math>(H, C)</math> if it has header <math>H</math> and satisfies <math>C</math>.

=== Key constraints and functional dependencies ===
One of the simplest and most important types of relation [[constraint (database)|constraint]]s is the ''key constraint''. It tells us that in every instance of a certain relational schema the tuples can be identified by their values for certain attributes.

; [[Superkey]]
A superkey is a set of column headers for which the values of those columns concatenated are unique across all rows. Formally:
: A superkey is written as a finite set of attribute names.
: A superkey <math>K</math> holds in a relation <math>(H, B)</math> if:
:* <math>K \subseteq H</math> and
:* there exist no two distinct tuples <math>t_1, t_2 \in B</math> such that <math>t_1[K] = t_2[K]</math>.
: A superkey holds in a relation universe <math>U</math> if it holds in all relations in <math>U</math>.
: '''Theorem:''' A superkey <math>K</math> holds in a relation universe <math>U</math> over <math>H</math> if and only if <math>K \subseteq H</math> and <math>K \rightarrow H</math> holds in <math>U</math>.
; [[Candidate key]]
A candidate key is a superkey that cannot be further subdivided to form another superkey.
: A superkey <math>K</math> holds as a candidate key for a relation universe <math>U</math> if it holds as a superkey for <math>U</math> and there is no [[proper subset]] of <math>K</math> that also holds as a superkey for <math>U</math>.
; [[Functional dependency]]
Functional dependency is the property that a value in a tuple may be derived from another value in that tuple.
: A functional dependency (FD for short) is written as <math>X \rightarrow Y</math> for <math>X, Y</math> finite sets of attribute names.
: A functional dependency <math>X \rightarrow Y</math> holds in a relation <math>(H, B)</math> if:
:* <math>X, Y \subseteq H</math> and
:* <math>\forall</math> tuples <math>t_1, t_2 \in B</math>, <math>t_1[X] = t_2[X]~\Rightarrow~t_1[Y] = t_2[Y]</math>
: A functional dependency <math>X \rightarrow Y</math> holds in a relation universe <math>U</math> if it holds in all relations in <math>U</math>.
; Trivial functional dependency
: A functional dependency is trivial under a header <math>H</math> if it holds in all relation universes over <math>H</math>.
: '''Theorem:''' An FD <math>X \rightarrow Y</math> is trivial under a header <math>H</math> if and only if <math>Y \subseteq X \subseteq H</math>.
; Closure
: [[Armstrong's axioms]]: The closure of a set of FDs <math>S</math> under a header <math>H</math>, written as <math>S^+</math>, is the smallest superset of <math>S</math> such that:
:* <math>Y \subseteq X \subseteq H~\Rightarrow~X \rightarrow Y \in S^+</math> (reflexivity)
:* <math>X \rightarrow Y \in S^+ \land Y \rightarrow Z \in S^+~\Rightarrow~X \rightarrow Z \in S^+</math> (transitivity) and
:* <math>X \rightarrow Y \in S^+ \land Z \subseteq H~\Rightarrow~(X \cup Z) \rightarrow (Y \cup Z) \in S^+</math> (augmentation)
: '''Theorem:''' Armstrong's axioms are sound and complete; given a header <math>H</math> and a set <math>S</math> of FDs that only contain subsets of <math>H</math>, <math>X \rightarrow Y \in S^+</math> if and only if <math>X \rightarrow Y</math> holds in all relation universes over <math>H</math> in which all FDs in <math>S</math> hold.
; Completion
: The completion of a finite set of attributes <math>X</math> under a finite set of FDs <math>S</math>, written as <math>X^+</math>, is the smallest superset of <math>X</math> such that:
:* <math>Y \rightarrow Z \in S \land Y \subseteq X^+~\Rightarrow~Z \subseteq X^+</math>
: The completion of an attribute set can be used to compute if a certain dependency is in the closure of a set of FDs.
: '''Theorem:''' Given a set <math>S</math> of FDs, <math>X \rightarrow Y \in S^+</math> if and only if <math>Y \subseteq X^+</math>.
; Irreducible cover
: An irreducible cover of a set <math>S</math> of FDs is a set <math>T</math> of FDs such that:
:* <math>S^+ = T^+</math>
:* there exists no <math>U \subset T</math> such that <math>S^+ = U^+</math>
:* <math>X \rightarrow Y \in T~\Rightarrow Y</math> is a singleton set and
:* <math>X \rightarrow Y \in T \land Z \subset X~\Rightarrow~Z \rightarrow Y \notin S^+</math>.

=== Algorithm to derive candidate keys from functional dependencies ===
 '''algorithm''' derive candidate keys from functional dependencies '''is'''
     '''input:''' a set ''S'' of FDs that contain only subsets of a header ''H''
     '''output:''' the set ''C'' of superkeys that hold as candidate keys in
             all relation universes over ''H'' in which all FDs in ''S'' hold
 
     ''C'' := ∅         // found candidate keys
     ''Q'' := { ''H'' }      // superkeys that contain candidate keys
     '''while''' ''Q'' <> ∅ '''do'''
         let ''K'' be some element from ''Q''
         ''Q'' := ''Q''&nbsp;– { ''K'' }
         ''minimal'' := '''true'''
         '''for each''' ''X->Y'' '''in''' ''S'' '''do'''
             ''K' '':= (''K''&nbsp;– ''Y'') ∪ ''X''   // derive new superkey
             '''if''' ''K' ''⊂ ''K'' '''then'''
                 ''minimal'' := '''false'''
                 ''Q'' := ''Q'' ∪ { ''K' ''}
             '''end if'''
         '''end for'''
         '''if''' ''minimal'' '''and''' there is not a subset of ''K'' in ''C'' '''then'''
             remove all supersets of ''K'' from ''C''
             ''C'' := ''C'' ∪ { ''K'' }
         '''end if'''
     '''end while'''