The Relational Model

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

• $\text{att}$: a countably infinite set of attributes
  • assume $\text{att}$ is fixed
• ${\le }_{\text{att}}$: a total order on $\text{att}$
  • the elements of a set of attributes $U$ are written according to ${\le }_{\text{att}}$ unless otherwise specified
• $\text{dom}$: a countably infinite set of domains (disjoint from $\text{att}$)
  • assume $\text{dom}$ is fixed
  • a constant is an element of $\text{dom}$
  • for most cases, the same domain of values is used for all attributes;
    • otherwise, assume a mapping $\text{Dom}$ on $\text{att}$, where $\text{Dom}(A)$ is a set called the domain of attribute $A$
• $\text{relname}$: a countably infinite set of relation names (disjoint from $\text{att}$ and $\text{dom}$)
• $\text{sort}$: a function from $\text{relname}$ to ${\mathcal{P}}^{\text{fin}}(\text{att})$ (the finitary powerset of $\text{att}$)
  • ${\text{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
  • $\text{sort}(R)$ is called the $\text{sort}$ of a relation name $R$
  • $\text{arity}(R)=|\text{sort}(R)|$: the $\text{arity}$ of relation name $R$
• $R$: a relation name or a relation schema
  • Alternative notations:
    • $R[U]$: indicating $\text{sort}(R)=U$
    • $R[n]$: indicating $\text{arity}(R)=n$
• $\text{R}$: a database schema
  • a nonempty finite set of relation names
  • might be written as $\text{R}=\{R_1[U_1],\dots ,R_n[U_n]\}$

Examples

Table Movies

Table Location

Table Pariscope

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

Named v.s. Unnamed Attributes/Tuples

Named Perspective

E.g. $⟨A:5,B:3⟩$

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 $\text{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{|}_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. $⟨5,3⟩$

a tuple is an ordered n-tuple ($n\ge 0$) of constants (i.e., an element of the Cartesian product ${\text{dom}}^n$)

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

Correspondence

Because of the total order ${\le }_{\text{att}}$, a tuple $⟨A_1:a_1,A_2:a_2⟩$ (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 $⟨a_1,a_2⟩$.

Conversely, the ordered tuple $t=⟨a_1,a_2⟩$ 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 $\text{R}[U]$ is a finite set of tuples $I$ with sort $U$.

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

Logic Programming Perspective

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

A fact over $\text{R}$ is an expression of the form $\text{R}(a_1,\dots ,a_n)$, where $a_i\in \text{dom}$ for $i\in [1,n]$.
If $u=⟨a_1,\dots ,a_n⟩$, we sometimes write $\text{R}(u)$ for $\text{R}(a_1,\dots ,a_n)$.

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

a database instance of database schema $\text{R}$ is a finite set $\text{I}$ that is the union of relation instances over $\text{R}$ for all $\text{R}\in \text{R}$.

Examples

Assume $\text{sort}(R)=AB,\text{sort}(S)=A$.

Named and Conventional

$$\begin{array}{rlr}I(R)=\{f_1,f_2,f_3\}& & \\ & f_1(A)=a& f_1(B)=b\\ & f_2(A)=c& f_2(B)=b\\ & f_3(A)=a& f_3(B)=a\\ I(S)=\{g\}& & \\ & g(A)=d& \end{array}$$

Unnamed and Conventional

$$\begin{array}{rlr}I(R)=\{⟨a,b⟩,⟨c,b⟩,⟨a,a⟩\}& & \\ I(S)=\{⟨d⟩\}& & \end{array}$$

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 $\text{var}$ will be used to range over elements of $\text{dom}$.

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

Notations