Relational model

The relational model (RM) is an approach to managing data using a structure and language consistent with first-order predicate logic, first described in 1969 by English computer scientist Edgar F. Codd, where all data are represented in terms of tuples, grouped into relations. A database organized in terms of the relational model is a relational database.

The purpose of the relational model is to provide a declarative method for specifying data and queries: users directly state what information the database contains and what information they want from it, and let the database management system software take care of describing data structures for storing the data and retrieval procedures for answering queries.

Most relational databases use the SQL data definition and query language; these systems implement what can be regarded as an engineering approximation to the relational model. A table in a SQL database schema corresponds to a predicate variable; the contents of a table to a relation; key constraints, other constraints, and SQL queries correspond to predicates. However, SQL databases deviate from the relational model in many details, and Codd fiercely argued against deviations that compromise the original principles.

History

The relational model was developed by Edgar F. Codd as a general model of data, and subsequently promoted by Chris Date and Hugh Darwen among others. In their 1995 The Third Manifesto, Date and Darwen try to demonstrate how the relational model can accommodate certain "desired" object-oriented features.

Extensions

Some years after publication of his 1970 model, Codd proposed a three-valued logic (True, False, Missing/NULL) version of it to deal with missing information, and in his The Relational Model for Database Management Version 2 (1990) he went a step further with a four-valued logic (True, False, Missing but Applicable, Missing but Inapplicable) version.

Conceptualization

Basic concepts

thumb|A relation with 5 attributes (its degree) and 4 tuples (its cardinality) can be visualized as a table with 5 columns and 4 rows. However, unlike rows and columns in a table, a relation's attributes and tuples are unordered.

A relation consists of a heading and a body. The heading defines a set of attributes, each with a name and data type (sometimes called a domain). The number of attributes in this set is the relation's degree or arity. The body is a set of tuples. A tuple is a collection of n values, where n is the relation's degree, and each value in the tuple corresponds to a unique attribute. The number of tuples in this set is the relation's cardinality.

Two special cases of constraints are expressed as keys and foreign keys:

Keys

A candidate key, or simply a key, is the smallest subset of attributes guaranteed to uniquely differentiate each tuple in a relation. Since each tuple in a relation must be unique, every relation necessarily has a key, which may be its complete set of attributes. A relation may have multiple keys, as there may be multiple ways to uniquely differentiate each tuple.

Logical interpretation

The relational model is a formal system. A relation's attributes define a set of logical propositions. Each proposition can be expressed as a tuple. The body of a relation is a subset of these tuples, representing which propositions are true. Constraints represent additional propositions which must also be true. Relational algebra is a set of logical rules that can validly infer conclusions from these propositions.

Set-theoretic formulation

Basic notions in the relational model are 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

: 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

: 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 database schema is said to consist of a set of relation names, the headers that are associated with these names and the 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 constraints 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 – { K }

minimal := true

for each X->Y in S do

K' := (K – 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

Alternatives

Other models include the hierarchical model and network model. Some systems using these older architectures are still in use today in data centers with high data volume needs, or where existing systems are so complex and abstract that it would be cost-prohibitive to migrate to systems employing the relational model. Also of note are newer object-oriented databases. and Datalog.

Datalog is a database definition language, which combines a relational view of data, as in the relational model, with a logical view, as in logic programming. Whereas relational databases use a relational calculus or relational algebra, with relational operations, such as union, intersection, set difference and cartesian product to specify queries, Datalog uses logical connectives, such as if, or, and and not to define relations as part of the database itself.

In contrast with the relational model, which cannot express recursive queries without introducing a least-fixed-point operator, recursive relations can be defined in Datalog, without introducing any new logical connectives or operators.

References

External links

cited in Codd's 1970 paper.
.
.
.