:PROPERTIES:
:ID: d38dac96-015e-4386-873c-3a1e16911ef2
:mtime: 20231024031952
:ctime: 20231024031950
:END:
#+title: relational algebra
#+filetags: :public:project:
* Relational Algebra
Relational Algebra is a way of working
with mathematical relations.
Relational algebra is the mathematical
foundation of [[id:182cf1ea-feba-4962-9cf0-d1d28fd62f1b][relational Database]].
* Parts of relational algebra
** Syntax of Relational Algebra
| Syntax | name | denotation |
|--------------------+-------------------+---------------------------------------------------------|
| $R$ | base relation | |
| $\sigma_p(Q)$ | selection | Select elements from $Q$ that satisfy the predicate $p$ |
| $\pi_X(Q)$ | projection | Project the columns of $Q$ that are in $x$ |
| $Q_1 \times Q_2$ | cartesian product | The cartesian product of $Q_1$ and $Q_2$ |
| $Q_{1} - Q_{2}$ | difference | the elements in $Q_1$ but not in $Q_2$ |
| $Q_1 \cup Q_2$ | union | The elements in either $Q_1$ or $Q_2$ |
| $Q_{1} \cap Q_{2}$ | intersection | The elements in both $Q_1$ and $Q_2$ |
| $\rho_M(Q)$ | renaming | rename the columns of $Q$ using $M$ |
** Relational Algebra as Inductive Datatype
#+BEGIN_SRC agda2
data RA : Set where
relation : Relation -> RA
selection : RA -> Predicate -> RA
projection : RA -> Attriubtes -> RA
product : RA -> RA -> RA
difference : RA -> RA -> RA
intersection : RA -> RA -> RA
union : RA -> RA -> RA
rename : RA -> Map -> RA
#+END_SRC
* Relational Algebra vs [[id:5f12c4b1-8767-43ee-94cc-a1bd2cd5b23a][SQL]]
[[id:5f12c4b1-8767-43ee-94cc-a1bd2cd5b23a][SQL]] is based on Relational Algebra
| Relational Algebra | [[id:5f12c4b1-8767-43ee-94cc-a1bd2cd5b23a][SQL]] |
|--------------------+----------------------------|
| $\sigma_p(Q)$ | SELCT * FROM $Q$ WHERE $p$ |
| $\pi_x(Q)$ | SELECT $x$ from $Q$ |
| $\rho_M(Q)$ | SELECT AS $M$ from $Q$ |
| $Q_1 \cup Q_2$ | $Q_1$ UNION $Q_2$ |
| $Q_1 \cap Q_2$ | $Q_1$ INTERSECT $Q_2$ |
| $Q_1 - Q_2$ | $Q_1$ EXCEPT $Q_2$ |
| $Q_1 \times Q_2$ | $Q_1$ , $Q_2$ |
* Joins
** Natural Join
If
$R(A,B)$ is a relation over $A$ and $B$, and
$S(B,C)$ is a relation over $B$ and $C$, then
$R \bowtie S$ is a relation over $A,B,C$ defined
by
\[R \bowtie S := \pi_{\{A,B<C\}}(\sigma_{B =B'}(R \times \rho_{\{B \mapsto B'\}}(S)))\]
In set comprehension syntax, we could write the natural join as
\[R \bowtie S := \{ (u.A, u.B , v.C) | \forall u in R , \forall v in S , u.B = b.B \}\]