lezione-3

Algebra relazionale

L’algebra relazionale è quella che ci permette di gestire i dati e si basa su degli operatori che:

• Sono definiti sulle relazioni
• Producono come risultato una relazione

Gli operatori primitivi sono:

• Ridenominazione
• Unione
• Differenza
• Proiezione
• Restrizione
• Prodotto

Ridenominazione

La ridenominazione è un operatore espresso dal simbolo ${\delta }_{name\to newName}$ che va a rinominare una colonna da $name$ a $newName$

EXAMPLE

$\delta Matricola\leftarrow CodiceStudente(STUDENTE)$

Unione, differenza e intersezione

Dato che le relazioni sono degli insiemi (di ennuple) possiamo applicare gli operatori che di solito usiamo con gli insiemi, dati $R$ ed $S$ due relazioni dello stesso tipo allora abbiamo che:

• $R\cup S=\{t|t\in R\vee t\in S\}$
• $R-S=\{t|t\in R\wedge t\notin S\}$
• $R\cap S=\{t|t\in R\wedge t\in S\}$

Proiezione

La proiezione è un operatore che ci permette di selezionare solo specifici attributi della nostra tabella. Sia $R$ una relazione e siano $A_1,A_2,...A_n$ alcuni suoi attributi allora una proiezione di $R$ sarebbe: ${\pi }_{A_1,A_2,...A_n}(R)=\{t[A_1,A_2,...A_n]t\in R\}$

Selezione

La selezione è un operatore che produce un risultato con lo stesso schema dell’operando iniziale ma con un sottoinsieme di ennuple. Data $\lambda$ una formula proposizionale e dato $R$ una relazione allora la selezione di $R$ rispetto al formula $\lambda$ sarebbe: ${\sigma }_{\lambda }(R)=\{t|t\in R\wedge \lambda (t)=\text{TRUE}\}$

Prodotto cartesiano

Date due relazione $R$ e $S$ con $R\cap S=\text{insieme vuoto}$ l’operatore prodotto cartesiano ci permette di creare $R\times S=\{tu|t\in R\wedge u\in S\}$

JOIN

Questo operatore ci permette di combinare tuple da relazioni diverse basandosi sui valori degli attributi, ne abbiamo principalmente due tipi:

• Natural JOIN Sia $R$ con attributi $XY$ ed $S$ con attributi $YZ$ allora $R\bowtie S$ è una relazione $XYZ$ quindi: $R\bowtie S=\{t|t[XY]\in R\text{ e }t[YZ]\in S\}$ cioè: le ennuple del risultato sono ottenute combinando le ennuple di $R$ e $S$ che hanno gli stessi valori negli attributi con lo stesso nome
• Theta JOIN viene specificato un predicato per la selezione delle ennuple, definito in questo modo: $R{\bowtie }_{F}S={\sigma }_F(R\times S)$ quando la congiunzione $F$ è di uguaglianza allora si parla di equi-JOIN questa theta-join è anche una equi-join

Dimostrazione che equi-join è derivata

Siano $R(A_1:T_1,\dots ,A_n:T_n)$ ed $S(A_{n+1}:T_{n+1},\dots ,A_{n+m}:T_{n+m})$ con $\{A_1,\dots ,A_n\}\cap \{A_{n+1},\dots A_{n+m}\}=\varnothing$ Allora ponendo:

• $R{\bowtie }_{A_i=A_k}S=\{tu\mid t\in R,u\in S,t.A_i=u.A_k\}$
• $\text{Con }1\le i\le n\text{e}n+1\le k\le n+m.$ Arriviamo a capire che la equi-join è derivata perché $R{\bowtie }_{A_i=A_k}S={\sigma }_{A_i=A_k}(R\times S)$ ovvero la equi-join è una theta join con una congiunzione di uguaglianza

Dimostrazione che natural-join è derivata

Siano $R$ con attributi $XY$ ed $S$ con attributi $YZ$, allora $R\bowtie S$ è una relazione di attributi $XYZ$ costituita da tutte le ennuple tali che: $t[XY]$ in $R$, $t[YZ]$ in $S$ ovvero che: $R\bowtie S=\{t|t[XY]\in R\text{ e }t[YZ]\in S\}$ Possiamo affermare che la congiunzione è derivata perché se rinominiamo gli attributi di $S$ come $Y^{\prime }Z$ ottenendo $S^{\prime }$ capiamo subito che usando una equi-join (con $Y=Y^{\prime }$) e una proiezione rispetto $XYZ$ otteniamo la stessa cosa che facendo una natural join: $R\bowtie S={\pi }_{XYZ}(R{\bowtie }_{Y=Y^{\prime }}{S}^{\prime })$ essendo la equi-join un operatore derivata allora anche la natural join lo è.

Dimostrazione che l’intersezione è derivata

Data due relazioni $R$ ed $S$ allora $A\wedge R=R-(R-S)$

Query

Una query è una funzione che da una istanza di una database (insiemi di relazioni) ci da una relazione come risultato