The Relational Model

Mathjax may have issues to display math symbols in particular styles, such as \(\mathcal{A}\).
You can try to mitigate this by changing the Math Renderer to Common HTML (right click on any math expressions): \( \newcommand{\att}{\textbf{att}} \) \( \newcommand{\attTotalOrder}{\leq_{\att}} \) \( \newcommand{\dom}{\textbf{dom}} \) \( \newcommand{\Dom}{\textit{Dom}} \) \( \newcommand{\relname}{\textbf{relname}} \) \( \newcommand{\sort}{\textit{sort}} \) \( \newcommand{\arity}{\textit{arity}} \) \( \newcommand{\finPowerSet}{\mathcal{P}^{\text{fin}}} \) \( \newcommand{\dbschema}[1]{\textbf{#1}} \) \( \newcommand{\dbinst}[1]{\textbf{#1}} \) \( \newcommand{\rel}[1]{\textit{#1}} \) \( \newcommand{\attname}[1]{\textit{#1}} \) \( \newcommand{\varSet}{\textbf{var}} \)

Informal Terminology

• Relation: table
  • Relation Name: name of the table
• Attribute: column name
• Tuple/Record: line in the table
• Domain: set of constants that entries of tuples can take
• Database Schema: specifying the structure of the database
• Database Instance: specifying the actual content in the database

Formal Definitions

• \(\att\): a countably infinite set of attributes
  • assume \(\att\) is fixed
• \(\attTotalOrder\): a total order on \(\att\)
  • the elements of a set of attributes \(U\) are written according to \(\attTotalOrder\) unless otherwise specified
• \(\dom\): a countably infinite set of domains (disjoint from \(\att\))
  • assume \(\dom\) is fixed
  • a constant is an element of \(\dom\)
  • for most cases, the same domain of values is used for all attributes;
    • otherwise, assume a mapping \(\Dom\) on \(\att\), where \(\Dom(A)\) is a set called the domain of attribute \(A\)
• \(\relname\): a countably infinite set of relation names (disjoint from \(\att\) and \(\dom\))
• \(\sort\): a function from \(\relname\) to \(\finPowerSet(\att)\) (the finitary powerset of \(\att\))
  • \(\sort^{-1}(U)\) is inifinite for each (possibly empty) finite set of attributes \(U\)
    • which allows multiple relations to have the same set of attributes
  • \(\sort(R)\) is called the \(\sort\) of a relation name \(R\)
  • \(\arity(R) = |\sort(R)|\): the \(\arity\) of relation name \(R\)
• \(R\): a relation name or a relation schema
  • Alternative notations:
    • \(R[U]\): indicating \(\sort(R) = U\)
    • \(R[n]\): indicating \(\arity(R) = n\)
• \(\dbschema{R}\): a database schema
  • a nonempty finite set of relation names
  • might be written as \(\dbschema{R} = \{R_1[U_1], \ldots, R_n[U_n]\}\)

Examples

Table Movies

Table Location

Table Pariscope

• The database schema \(\dbschema{CINEMA} = \{ \rel{Movies}, \rel{Location}, \rel{Pariscope} \}\)
• The sorts of the relation names
  • \(\sort(\rel{Movies}) = \{ \attname{Title}, \attname{Director}, \attname{Actor} \}\)
  • \(\sort(\rel{Location}) = \{ \attname{Theater}, \attname{Address}, \attname{Phone} \}\)
  • \(\sort(\rel{Pariscope}) = \{ \attname{Theater}, \attname{Title}, \attname{Schedule} \}\)

Named v.s. Unnamed Attributes/Tuples

Named Perspective

E.g. \( \langle A:5, B:3 \rangle \)

a tuple over a finite set of attributes \(U\) (or over a relation schema \(R[U]\)) is a total mapping (viewed as a function) \(u\) from \(U\) to \(\dom\).

• \(u(U)\): \(u\) is a tuple over \(U\)
• \(u(A)\): the value of \(u\) on an attribute \(A\) in \(U\) (\(A \in U\))
• \(u[V] = u \vert_V\): the restriction of \(u\) to a subset \(V \subseteq U\), i.e., \(u[V]\) denotes the tuple \(v\) over \(V\) such that \(v(A) = u(A)\) for all \(A \in V\)

Unnamed Perspective

E.g. \( \langle 5, 3 \rangle \)

a tuple is an ordered n-tuple (\(n \geq 0\)) of constants (i.e., an element of the Cartesian product \(\dom^n\))

• \(u(i)\): the \(i\)-th coordinate of \(u\)

Correspondence

Because of the total order \(\attTotalOrder\), a tuple \(\langle A_1:a_1, A_2:a_2 \rangle\) (defined as a function) can be viewed as an ordered tuple with \((A_1:a_1)\) as a first component and \((A_2:a_2)\) as a second component. Ignoring the names, this tuple can be viewed as the ordered tuple \(\langle a_1, a_2 \rangle\).

Conversely, the ordered tuple \(t = \langle a_1, a_2 \rangle\) can be viewed as a function over the set of integers \(\{1, 2\}\) with \(t(i) = a_i\) for each \(i\).

Conventional v.s. Logic Programming Relational Model

Conventional Perspective

a relation (instance) over a relation schema \(\rel{R}[U]\) is a finite set of tuples \(I\) with sort \(U\).

a database instance of database schema \(\dbschema{R}\) is a mapping \(\dbinst{I}\) with domain \(\dbschema{R}\), such that \(\dbinst{I}(\rel{R})\) is a relation over \(\rel{R}\) for each \(\rel{R} \in \dbschema{R}\).

Logic Programming Perspective

This perspective is used primarily with the ordered-tuple perspective on tuples.

A fact over \(\rel{R}\) is an expression of the form \(\rel{R}(a_1, \ldots, a_n)\), where \(a_i \in \dom\) for \(i \in [1, n]\).
If \(u = \langle a_1, \ldots, a_n \rangle\), we sometimes write \(\rel{R}(u)\) for \(\rel{R}(a_1, \ldots, a_n)\).

a relation (instance) over a relation schema \(\rel{R}\) is a finite set of facts over \(\rel{R}\).

a database instance of database schema \(\dbschema{R}\) is a finite set \(\dbinst{I}\) that is the union of relation instances over \(\rel{R}\) for all \(\rel{R} \in \dbschema{R}\).

Examples

Assume \(\sort(R) = AB, \sort(S) = A\).

Named and Conventional

\[ \begin{split} I(R) = \{ f_1, f_2, f_3 \} \quad && \\ & f_1(A) = a &\quad f_1(B) = b \\ & f_2(A) = c &\quad f_2(B) = b \\ & f_3(A) = a &\quad f_3(B) = a \\ I(S) = \{g\} \quad && \\ & g(A) = d & \end{split} \]

Unnamed and Conventional

\[ \begin{split} I(R) = \{ \langle a, b \rangle, \langle c, b \rangle, \langle a, a \rangle \} \quad && \\ I(S) = \{ \langle d \rangle \} \quad && \end{split} \]

Named and Logic Programming

\[ \{ R(A:a, B:b), R(A:c, B:b), R(A:a, B:a), S(A:d) \} \]

Unnamed and Logic Programming

\[ \{ R(a, b), R(c, b), R(a, a), S(d) \} \]

Variables

an infinite set of variables \(\varSet\) will be used to range over elements of \(\dom\).

• a free tuple over \(U\) or \(\rel{R}(U)\) is a function \(u\) from \(U\) to \(\dom \cup \varSet\)
• an atom over \(\rel{R}\) is an expression of the form \(\rel{R}(e_1, \ldots, e_n)\), where \(n = \arity(\rel{R})\) and each term \(e_i \in \dom \cup \varSet\)
• a ground atom is an atom with no variables, i.e., a fact (see Logic Programming Perspective)

• Notations

Notations