Algebra relazionale

Le interrogazioni al database possono essere formalmente rappresentate dall'algebra relazionale.

Ogni relazione R(A1: T1, ..., An: Tn) è considerata un insieme di ennuple $\{(A_1:T_1,...,A_n:T_n)\}$, dove il grado è definito come il numero di attributi e la cardinalità il numero di ennuple.

Operatori principali

• Ridenominazione, e.g. per rinominare l'attributo $A_1$ a $B_1$:

  $${\rho }_{A_1\leftarrow B_1}(R)$$ che avrà cardinalità e grado uguali ad $R$.

  Diventa utile nelle operazioni tra relazioni con attributi con lo stesso nome.

• Unione e differenza, sulle ennuple di due relazioni $R$ ed $S$ dello stesso tipo:

  $$R\cup S$$ con cardinalità $|R|+|S|-|R\cap S|$, e $$R-S$$ con cardinalità $|R|-|R\cap S|$.

• Proiezione, e.g. per isolare gli attributi $A_1$ e $A_2$:

  $${\pi }_{A_1,A_2}(R)=\{(t.A_1,t.A_2)\mid t\in R\}$$ di cardinalità al più $|R|$ perchè le ennuple non sono distinte se gli attributi scelti non sono superchiave.

• Restrizione, per filtrare le ennuple con una condizione $\varphi$:

  $${\sigma }_{\varphi }(R)=\{t|t\in R\wedge \varphi \}$$

  Per esempio, ${\sigma }_{\text{Etaˋ}\ge 18}(\text{Studenti})$ per trovare le ennuple degli studenti maggiorenni.

• Prodotto, per il prodotto cartesiano tra le ennuple di $R$ ed $S$ aventi attributi distinti:

  $$R\times S=\{(t.A_1,...,t.A_n,u.B_1,...,u.B_m)\mid t\in R\wedge u\in S\}$$

  Per esempio, date le relazioni Studenti ed Esami:

  Matricola	Nome
  11371	Mario
  12678	Paolo

  Codice	Studente*	Voto
  10822	11371	28
  10913	12678	30

  si possono trovare: $${\pi }_{\text{Nome}}({\sigma }_{\text{Voto}=30}({\sigma }_{\text{Matricola}=\text{Studente}}(\text{Studenti}\times \text{Esami})))$$ ovvero gli studenti che hanno ottenuto Voto uguale a $30$.

Operatori derivati

Dagli operatori principali è possibile ricavare degli operatori derivati, tra cui:

• Join, per combinare le ennuple con attributi distinti ma aventi gli stessi valori su $A_i$ e $B_j$:

  $$R\underset{A_i=B_j}{\bowtie }S={\sigma }_{A_i=B_j}(R\times S)$$

• Natural join, come la join ma attraverso attributi di $R$ ed $S$ aventi lo stesso nome:

  $$R\bowtie S$$ che, se espresso con il prodotto, richiede la ridenominazione degli attributi in comune.

  Per esempio, dati

  Informazioni(CodInfo: string, Anno: int)
  	PK(CodInfo)
  Libri(ISBN: string, CodInfo*: string)
  	PK(ISBN)
  	CodInfo FK(Informazioni)
  

  si possono associare le due relazioni con $\text{Libri}\bowtie \text{Informazioni}$, oppure: $${\rho }_{\text{ICod}\leftarrow \text{CodInfo}}({\pi }_{\text{ISBN},\text{ICod},\text{Anno}}({\sigma }_{\text{LCod}=\text{ICod}}({\rho }_{\text{CodInfo}\leftarrow \text{LCod}}(\text{Libri})\times {\rho }_{\text{CodInfo}\leftarrow \text{ICod}}(\text{Informazioni}))))$$

• Outer join, come la join ma tenendo le ennuple non combinabili impostando i nuovi attributi a NULL:

  $$R\overleftrightarrow{\bowtie }S$$

• Intersezione, sulle ennuple delle relazioni $R$ ed $S$ dello stesso tipo:

  $$R\cap S=R-(R-S)$$

• Divisione, per raggruppare tutte le ennuple di $R$ associate a tutti gli attributi di $S\ne \varnothing$:

  $$R÷S={\pi }_X(R)-{\pi }_X(({\pi }_X(R)\times S)-R)$$ dove $R$ contiene gli attributi $X$ e $Y$, mentre $S$ contiene solamente gli attributi $Y$.

  Per esempio, siano $E={\pi }_{\text{Studente},\text{Materia}}(\text{Esami})$ e $A={\pi }_{\text{Materia}}({\sigma }_{\text{Studente}=\text{"76366"}}(E))$, allora $E÷A$ restituisce gli studenti che hanno fatto al minimo tutti gli esami $A$.

  Inoltre, le ennuple associate esattamente (né più né meno) a tutte quelle in $S$ si possono ottenere con: $$R÷S\cap ({\pi }_X(R)-{\pi }_X(R-({\pi }_X(R)\times S)))$$ dove il secondo termine contiene le ennuple in $R$ associate al più a quelle in $S$.

Operatori speciali

• Proiezione generalizzata, per dare un nome a delle espressioni:

  $${\pi }_{{\text{Expr}}_1\text{ as }{A}_1,...,{\text{Expr}}_n\text{ as }{A}_n}(R)$$

  Per esempio, ${\pi }_{\text{Codice},\text{Prezzo}\ast \text{Qty}\text{ as }\text{Totale}}(\text{Acquisti})$ saranno ennuple di tipo (Codice, Totale).

• Raggruppamento, per raggruppare più ennuple attraverso delle funzioni di aggregazione:

  $${}_{A_1,...,A_n}{\gamma }_{f_1,...,f_n}(R)$$

  dove $f_1,...,f_n$ sono espressioni che aggregano più ennuple che hanno gli stessi $A_1,...,A_n$:

  • $\mathrm{sum}(A_i)$: somma i valori sull'attributo $A_i$
  • $\mathrm{avg}(A_i)$: fa la media di tutti i valori di $A_i$
  • $\mathrm{count}(\ast )$: conta le ennuple
  • $\min (A_i)$ e $\max (A_i)$: trovano il minimo e il massimo dei valori su $A_i$
  • $\text{-distinct}(A_i)$, suffisso alle precedenti funzioni per rimuovere i duplicati

  Per esempio, dato $${}_{\text{Candidato}}{\gamma }_{\mathrm{count}(\ast ),\min (\text{Voto}),\max (\text{Voto}),\mathrm{avg}(\text{Voto})}(\text{Esami})$$ si trovano il numero di esami, il minimo, il massimo e la media dei voti di ogni Candidato.

Operatori sui multiinsiemi

Se nelle relazioni sono presenti più ennuple uguali, vanno sfruttati gli operatori per i multiinsiemi:

• Proiezione senza rimuovere duplicati:

  $${\pi }_{A_1,...,A_n}^b(R)$$

• Eliminazione duplicati, per rimuovere le ennuple con gli stessi valori:

  $$\delta (R)$$

• Ordinamento, per ordinare lessicograficamente le ennuple con priorità da $A_1$ fino ad $A_n$:

  $${\tau }_{A_1,...,A_n}(R)$$

• Unione, intersezione e differenza, e.g. con un ennupla $t$ che appare $n$ volte in $R$ e $m$ volte in $S$:

  $$R{\cup }^{b}S$$ su cui $t$ appare $n+m$ volte.

  $$R{\cap }^{b}S$$ su cui $t$ appare $\min (n,m)$ volte.

  $$R{-}^{b}S$$ su cui $t$ appare $\max (0,n-m)$ volte.

Trasformazioni

Agli operatori possono essere applicate delle regole di equivalenza per manipolare le espressioni:

• ${\pi }_{A_1}({\pi }_{A_1,A_2}(R))={\pi }_{A_1}(R)$
• ${\sigma }_{{\varphi }_1}({\sigma }_{{\varphi }_2}(R))={\sigma }_{{\varphi }_1\wedge {\varphi }_2}(R)$
• $R\times (S\times T)=(R\times S)\times T$
• $R\times S=S\times R$
• ${\sigma }_{\varphi }{(}_{A_1}{\gamma }_{f_1}(R)){=}_{A_1}{\gamma }_{f_1}({\sigma }_{\varphi }(R))$