Week 3. Relational Data Model

Introduction to the relational data model

The relational data model is based on the concept of a relation; a relation is a mathematical concept based on the idea of sets, a relation looks like a table of values, a relation typically contains a set of rows.

The data elements in each row represent certain facts that correspond to a real-world entity or relationship. In a formal model, we call these tuples.

Each column has a header that gives an indication of the meaning of the data items in that column. In the formal model, the column header is called the attribute.

Key of a relation: each row has a value of a data item that uniquely identifies that row in the table.

Sometimes row-ids / sequential numbers are assigned as keys to identify rows, these are called artificial or surrogate keys.

Formal Definition

Schema

The schema (description) of a Relation is denoted by $R(A_1,A_2,...,A_n)$.

• $R$ is the name of the relation.
• The attributes of the relation are $A_1$, $A_2$, …, $A_n$.
• Each attribute has a domain / set of valid values.

Example: CUSTOMER(Id, Name, Address, Phone#).

Link to original

Tuple (Databases)

A tuple (row) is an ordered set of values (enclosed in angled brackets).

• Each value is derived from a given domain.
• A row in a relation (such as the CUSTOMER relation) is a n-tuple consisting of n-values, for example:
  • <567, "A", "123 Fake Street", "+1 000 111 222">

Link to original

Relation (Databases)

A relation (table) is a set of tuples (rows).

Link to original

Domain (Databases)

A domain is a set of atomic values, has an a data-type / format defined for it and has a logical definition:

• Example: “USA_phone_numbers” are the set of 10 digit phone numbers valid in the U.S. They may have a format “(ddd)ddd-dddd” where each d is a decimal digit. The attribute name designates the role played by a domain in a relation, it is used to interpret the meaning of the data elements as they correspond to that attribute.

Link to original

State (Databases)

The relation state is a subset of the Cartesian product of the domains of its attributes, where each domain contains the set of all possible values the attribute can take.

Example: the attribute customer name is defined over the domain of character strings of maximum length 25, $\text{dom}(\text{Customer Name})=\text{varchar}(25)$.

Link to original

Summary

Given $R(A_1,A_2,...,A_n)$, $r(R)\subset \text{dom}(A_1)\times \text{dom}(A_2)\times ...\times \text{dom}(A_n)$.

• $R(A_1,A_2,...,A_n)$ is the schema of the relation.
• $R$ is the name of the relation.
• $A_1,A_2,...,A_n$ are attributes of the relation.
• $r(R)$: is a specific state of relation $R$.

Example: Relation Schema

Let $R(A_1,A_2)$ be a relation schema:

• Let $\text{dom}(A_1)=\{0,1\}$
• Let $\text{dom}(A_2)=\{a,b,c\}$

Then take $\text{dom}(A_1)\times \text{dom}(A_1)$ as all possible combinations:

$$\{<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c>\}$$

The relation state is $r(R)\subset \text{dom}(A_1)\times \text{dom}(A_2)$.

Characteristics of Relations

• All values are considered atomic.

• Domain Constraint (Databases)

  The domain constraint is an implicit constraint that every value in a tuple must be from the domain of its attribute.

  Each value in a tuple must be from the domain of the attribute for that column. If $t=<v_1,v_2,...,v_n>$, in relation state $r$ of $R(A_1,A_2,...,A_n)$ then $v_i$ must be a value from the domain $\text{dom}(A_i)$.

  Link to original

• Null (Databases)

  A null value is used to represent values that are unknown or inapplicable to certain tuples.

  Link to original

• Component Values (Databases)

  We refer to component values of a tuple $t$ by $t[A_i]$ or $t.A_i$. This is the value $v_i$ of attribute $A_i$ for tuple $t$.

  Link to original

• Sub-tuple (Databases)

  We can use $t[A_u,A_v,...,A_w]$ to refer to the sub-tuple of $t$ containing the values of the attributes $A_u,A_v,...,A_w$ in $t$.

  Link to original

Role of super-keys and keys

Superkey (Databases)

The Superkey of relation $R$ is a set of attributes $SK$ of $R$ with the following conditions:

• no two tuples in any valid relation state $r(R)$ will have the same value for $SK$ for any distinct tuples $t_1$ and $t_2$ in $r(R)$, $t_1[SK]\ne t_2[SK]$.
• this condition must hold in any valid state $r(R)$

Link to original

Key (Databases)

The Key of relation $R$ is a “minimal” Superkey (Databases). A key is a superkey $K$ such that removal of any attribute from $K$ results in a set of attributes that is not a superkey.

Link to original

Example: Key Constraints

Consider the CAR relation schema: CAR(State, Reg#, SerialNo, Make, Model, Year).

• CAR has two superkeys:
  • ${\text{Key}}_1=\{\text{State},\text{Reg\#}\}$
  • ${\text{Key}}_2=\{\text{SerialNo}\}$
• ${\text{Key}}_1$ is a superkey but not a key.

Key Constraints

In general, any key is a superkey but not vice-versa. Any set of attributes that includes a key is a superkey. A minimal superkey is also a key.

Primary Key (Databases)

If a relation has several candidate keys, one is chosen randomly to be the primary key. The primary key attribute is underlined.

Link to original

Different types of integrity in databases

Constraints (Databases)

Constraints are conditions that must hold on all valid relation states. There are three main types of constraints in the relational model:

• Key constraints
• Entity Integrity constraints
• Referential Integrity constraints

Additional constraints include:

• Domain Constraint (Databases)
• Semantic Integrity Constraint (Databases)

Link to original

Relational Database Schema

A relational database schema is a set $S$ of relation schemas that belong to the same database. $S$ is the name of the whole database schema. $S=\{R_1,R_2,...,R_n\}$ and $R_1,R_2,...,R_n$ are the names of the individual relation schemas within the database $S$.

Link to original

Entity Integrity

Entity Integrity

The primary key attributes $PK$ of each relation schema $R$ in $S$ cannot have null values in any tuple of $r(R)$.

• This is because primary key values are used to identify the tuples
• $t[PK]\ne \text{null}$ for any tuple $t$ in $r(R)$
• if $PK$ has several attributes, $\text{null}$ is not allowed in any of these attributes

Link to original

Referential Integrity

Referential Integrity

Referential Integrity deals with a constraint involving two relations. It is used to specify a relationship among tuples in two relations:

• the referencing relation; tuples in the referencing relation $R_1$ has foreign key attributes referencing the primary key
• the referenced relation; tuples in the referenced relation $R_2$ have primary key attributes referenced by the foreign key

Link to original

Foreign Key

Foreign Key (Databases)

A foreign key is a set of attributes $FK$ in a relation schema $R_1$, that references a relation $R_2$ if it satisfies the following rules:

1. Attributes in the $FK$ must have the same domain(s) as the primary key attributes $PK$, the attributes are said to refer to the relation $R_2$.
2. A value of $FK$ in tuple $t_1$ of $r_1(R_1)$ either occurs as a value of $PK$ for some tuple $t_2$ in the relation state $r_2(R_2)$ or it is null. $t_1[FK]=t_2[PK]$ In the case that the value of the $FK$ on $R_1$ is null, it should not be part of its own primary key.

Link to original

Displaying Relational Database Schema and constraints

We can represent the schema is a diagram where:

• each relation schema can be displayed as a row of attribute names
• name of the relation is written above the row
• primary key attribute(s) are underlined
• foreign key constraints are displayed as a directed arc / arrow from the $FK$ to the referenced table (or to the $PK$ for clarity)

Example: Referential Integrity constraints for COMPANY database

INSERT, DELETE, UPDATE and maintaining referential integrity

Relational Database State

The relational database state is a union of all the individual relation states. Whenever the database is changed, a new state arises.

Link to original

Update Operations on Relations

We can:

• INSERT a tuple
• DELETE a tuple
• MODIFY a tuple While doing this:
• integrity constraints should not be violated
• several update operations may have to be grouped together
• updates may propagate to cause other updates automatically

If we hit a integrity violation, we can:

• Cancel the operation causing the violation (RESTRICT or REJECT)
• Perform the operation but inform the user of the violation
• Trigger additional updates so that the violation is corrected (CASCADE, SET NULL)
• Execute a user-specified error-correction routine

INSERT violations

Update violations for INSERT

When inserting records, we may violate:

• Domain Constraint (Databases): if one of the attribute values provided for the new tuple is not of the specified attribute domain
• Key Constraint (Databases): if the value of a key attribute in the new tuple already exists in another tuple in the relation
• Referential Integrity: if a foreign key value in the new tuple references a primary key value that does not exist in the referenced relation
• Entity Integrity: if the primary key value is null in the new tuple

Link to original

DELETE violations

Update violations for DELETE

A deletion operation may only violate Referential Integrity if the primary key value of the tuple being deleted is referenced from other tuples in the database.

We can remedy this by:

• RESTRICT: rejecting the deletion
• CASCADE: deleting referencing tuples This can be rather dangerous as it could delete big chunks of the database.
• SET NULL: set the $FK$ of the referencing tuples to $\text{null}$

Link to original

UPDATE violations

Update violations for UPDATE 1

An update may violate the domain and NOT NULL constraint on an attribute being modified.

And any other constraint may also be violated depending on the attribute being updated:

• Updating primary key $PK$: similar to a DELETE, followed by INSERT
• Updating a foreign key $FK$: may violate Referential Integrity
• Updating an ordinary attribute: can only violate Domain Constraint (Databases)

Link to original