Relational Model

Relational Model

Relation

$r \subseteq D_1 \times D_2 \times \cdots \times D_n$

Given sets $D_1, D_2, \cdots, D_n$, relation $r$ is a subset of $D_1 \times D_2 \times \cdots \times D_n$

Relation Schema

Given attributes $A_1, A_2, \cdots, A_n$, $R = (A_1, A_2, \cdots, A_n)$ is a relation schema. (Structure of relation)

$r(R)$ is a relation (variable) on the schema $R$.

Relation Instance

The current values of a relation are called relation instance. A relation is specified by a table. An element $t$ of relation $r$ is a tuple, represented by a row.

Domain

A set of allowed values for each attribute is called domain. Denoted by $D_1, D_2, \cdots$ for each attribute $A_1, A_2, \cdots$.

Atomic

Attribute values are usually required to be atomic (indivisible).

Null

Null represents unknown or missing, which is a member of every domain.

Unordered

Relations are unordered sets.

Relational Database

A database consistes of multiple relations.

Keys

Key $K \subseteq R$

Superkey

$S = {K \subseteq R \vert K \rightarrow R}$

Sufficient to identify a unique tuple of possible relation instance $r(R)$.

Candidate Key

$C = {K \subseteq R \vert \forall \alpha \subset K, \alpha \notin S}$

Superkey which is minimal.

Primary Key

The most representative candidate key is selected to be primary key.

Foreign Key

Value in one relation must appear in another. (Referencing/Referenced)

Relational Algebra

• Selection: $\sigma_{\rho}(r) = {t \in r \vert \rho(t) }$
  • Selection of tuples
  • Selection predicate $\rho$
• Projection: $\Pi_{A_1, A_2, \cdots, A_k}(r)$
  • Selection of columns.
  • Duplicated rows removed from result.
• Union: $r \cup s = {t \vert t \in r \lor t \in s}$
  • Compatibility: same arity (# of attributes) & compatible domain
• Set Difference: $r - s = {t \vert t \in r \land t \notin s}$
  • Must be compatible.
• Cartesian Product: $r \times s = {tq \vert t \in r \land q \in s}$
  • If $R \cap S \ne \phi$, renaming attribute is required.
• Rename: $\rho_{N}(E)$ returns the expression $E$ under name $N$.
  • $\rho_{N (A_1, \cdots, A_k)}(E)$ also renames the attributes.
• Intersection: $r \cap s = {t \vert t \in r \land t \in s}$
  • Must be compatible.
  • $r \cap s = r - (r - s)$
• Natural Join: $(r \Join s)(R \cup S)$, where $r(R)$ and $s(S)$
  • $t[R] = t_r$, $t[S] = t_s$
  • $r \Join s = \Pi_{R \cup S}(\sigma_{r.(R \cap S) = s.(R \cap S)}(r \times s))$
  • commutative & associative => trivial (reflexivity)
  • $R \cap S = \phi \Rightarrow r \Join s = r \times s$
    Pf. Suppose $R \cap S = \phi$.
    By definition of join, $r \Join s = \Pi_{R \cup S}(\sigma_{r.(R \cap S) = s.(R \cap S)}(r \times s)) = r \times s$
  • $R = S \Rightarrow r \Join s = r \cap s$
    Pf. Suppose $R = S$.
    By definition of join, $r \Join s = \Pi_{R \cup S}(\sigma_{r.(R \cap S) = s.(R \cap S)}(r \times s)) = \Pi_R(\theta_{r.R = s.R}(r \times s)) = r \cap s$
  • Theta Join: $r \Join_\theta s = \sigma_\theta(r \times s)$
• Assignment: $temp \leftarrow some_query$
  • assign temporary variable to complex expression
  • write expression as a sequence consisting assignments

Discussion

Candidate Key

Q. Why do you think “key”, without any qualifier, is meant to be candidate key instead of super key?

A. Non-candidate superkey is inefficient since the record is still identifiable with its subset, which is smaller.

Foreign Key Constraint

Q. Give examples of inserts and deletes, which can cause a violation of the foreign key constraint.

• Insert: Cannot insert non-existing foreign key value
• Delete: Cannot delete referenced column unless handled

Name as SuperKey

Q. In general, can we use name attribute as a superkey?

A. Usually name is not unique. Possible duplication in the future.

Operator Precedence

Precedence	Operators	Associativity
0	parenthesis
1	unary: $\rho$, $\sigma$, $\Pi$
2	multiplication without compatibility: $\times$, $\Join$	left to right
3	multiplication under compatibiltiy: $\cap$	left to right
4	addition under compatiblity: $-$, $\cup$	left to right

Back