ConceptDBISAI-written · not yet proofread

Relational Model

In the relational model a table with k columns is a triple (C, D, R) of column names, column domains and a multiset of rows, and a database is a collection of such tables linked by primary and foreign keys.

Definition

A table (relation) with $k$ columns is a triple $T = (C, D, R)$ :

$C = (c_1, \ldots, c_k)$ — tuple of column names,
$D = (D_1, \ldots, D_k)$ — tuple of domains, $D_j$ being the set of allowed values in column $j$ ,
$R$ — multiset of rows $r = (r_1, \ldots, r_k)$ with $r_j \in D_j$ for all $j$ .

The schema of $T$ is the pair $(C, D)$ (fixed); the instance is the current multiset $R$ (rows can be added, changed and deleted; $R$ may be empty). For a row $r$ , $r[j] := r_j$ is its value in column $j$ ; columns are numbered from 1. A relational database is a collection of tables, each with its own schema, together with integrity constraints such as primary and foreign keys.

Properties#

Terminology#

Term	Meaning
Relation	Synonym for table
Tuple / row	A single element $r \in R$
Attribute / column	A position $j$ with name $c_j$ and domain $D_j$
Degree	Number of columns $k = \\|C\\|$
Cardinality	Number of rows $\\|R\\|$
Schema	The pair $(C, D)$ describing the structure
Instance	The current multiset $R$ of rows

Multiset, not set#

A set contains each element at most once, a multiset may contain it several times: $M = \{1, 7, 3, 7, 7\}$ has $|M| = 5$ . Codd’s original relational model (1969) allowed only sets; most modern systems (and the course definition) allow multisets, because checking for duplicates costs time and space. If uniqueness is needed, it is declared as a constraint (UNIQUE, PRIMARY KEY).

No order#

Neither sets nor multisets have an order: a database need not remember insertion order and may reorder rows to work more efficiently. An order of the final result is requested with ORDER BY (see Ordering); a persistent order needs an explicit counter column (e.g. an auto-increment column, which costs time and space).

Primary key#

A set of key columns $K \subseteq \{1, \ldots, k\}$ is a primary key if no two distinct rows agree on all of them:

\forall\, r, r' \in R,\; r \neq r' \implies \exists\, j \in K : r_j \neq r'_j.

Usually a single ID column (e.g. movies.id); it gives each row a unique ID and is the canonical way to reference a row from another table.

Foreign key#

A primary key used in another table is a foreign key there. A foreign key $F$ in $T_1$ referencing the primary key $K$ of $T_2$ requires referential integrity:

\forall\, r \in R_1 \;\exists\, r' \in R_2 : r[F] = r'[K].

With PRIMARY KEY and REFERENCES declared, the RDBMS checks that every row has a primary key, that it is unique, and that every foreign-key value exists in the referenced table.

Relationships between tables#

Two tables $A$ , $B$ linked by keys (directly or via other tables) stand in one of four relationships:

Kind	Meaning
1:1	each record in $A$ is associated with exactly one record in $B$
1:N	a record in $A$ can be associated with several records in $B$ , but each record in $B$ with only one in $A$
N:1	the same, the other way round
N:M	records in $A$ can be associated with several in $B$ and vice versa

A link via a primary key and a foreign key is typically 1:N (never N:M); a link via a table of two foreign keys is typically N:M.

Closure#

The operations on tables (Relational Algebra: projection, selection, Cartesian Product, Join, Grouping) take tables and return a table, so they can be composed into query plans. SQL references columns by name $c_j$ ; the formal operations reference them by index $j$ .

Example#

ExampleMovies and actors with keys

CREATE TABLE movies(id TEXT PRIMARY KEY, title TEXT, year INTEGER, score REAL);
CREATE TABLE persons(id TEXT PRIMARY KEY, name TEXT, birth_date DATE);
CREATE TABLE roles(movie_id TEXT REFERENCES movies(id),
                   person_id TEXT REFERENCES persons(id));

movies.id and persons.id are primary keys; roles.movie_id and roles.person_id are foreign keys. movies–roles and persons–roles are 1:N, movies–persons (via roles) is N:M.

Sources#

Slides 03, p. 8 (table definition), p. 9–10 (multisets, order), p. 22–27 (IDs, keys, relationships)
Slides 04, p. 7–8 (recap, concatenation and column access)
DBIS_VL03 > Tables, DBIS_VL03 > Sets vs. multisets, DBIS_VL03 > Primary key and foreign key, DBIS_VL03 > Relationships between tables, DBIS_VL04 > Notation

Connections

Mentioned in inline links9

ACID
Consistency is a correctness guarantee about pre-defined properties (e.g. primary and foreign keys, see Relational Model), not a performance concept. What counts as “valid” is defined by these constraints. §
Cartesian Product
For tables $T_1 = (C_1, D_1, R_1)$ and $T_2 = (C_2, D_2, R_2)$ of the Relational Model, the Cartesian product cartesian-product(T1, T2) $= T_1 \times T_2$ is the table $T = (C, D, R)$ with §
Ordering
Tables are multisets of rows and have no inherent order (Relational Model). For the final result of a query, an order is requested with §
Relational Algebra
Relational algebra is the set of operations on tables $T = (C, D, R)$ of the Relational Model that an RDBMS implements internally. Each operation takes one or two tables and returns a single table, so operations compose. The three basic op… §
SPARQL to SQL Translation
Related: Relational Model — the triples table is a relation with columns $(\text{subject}, \text{predicate}, \text{object})$ §
VL03 – Database Basics
Table (Relational Model) §
Relational Model — formal definition of a table as $(C, D, R)$ with a multiset of rows; primary and foreign keys §
VL04 – Query Planning Basics
Recap from Lecture 3 (Relational Model, Slide 7): a table is a triple $T = (C, D, R)$ with column names $C = (c_1, \dots, c_k)$ , domains $D = (D_1, \dots, D_k)$ and a multiset $R$ of tuples $(r_1, \dots, r_k)$ with $r_j \in D_j$ . A tuple f… §
Relational Model — the table definition $(C, D, R)$ on which the operations are defined §
VL05 – Joins and more SQL
A table is a triple $T = (D, C, R)$ in the sense of the Relational Model: $C$ the tuple of column names, $D$ the tuple of domains, $R$ the multiset of rows. §
SQL and Query Planning
Relational Model — tables $(C, D, R)$ as multisets of rows, primary and foreign keys §
From a query to a result. A query SELECT … FROM … WHERE … is defined by a chain of operations on tables: the FROM tables are combined by the Cartesian Product, the WHERE expression selects rows ( $\sigma$ ), the SELECT list projects columns… §

Search in these mentions →