ALGEBRA
RELAZIONALE
DB -Algebra Relazionale
1
LINGUAGGI PER MODELLI
RELAZIONALI
Algebrici: una query è definita da
un’espressione algebrica sulle relazioni
dello schema
 Logici: una query è definita da una formula
della logica del primo ordine; in particolare
se è una collezione di formule di Horn
senza funzioni si ha il Datalog

DB -Algebra Relazionale
2
ESEMPIO DI QUERY
NOME
Mario Rossi
Ugo Bianchi
Teo Verdi
MATRICOL
123456
234567
345678
CORSO
Programmazione
Architetture
Matematica Discreta
INDIRIZZO
Via Etnea 1
Via Roma 2
Via Enna 3
TELEFONO
222222
333333
444444
PROFESSORE
Ferro
Pappalardo
Lizzio
CORSO
Programmazione
Architetture
Programmazione
Matematica
Discreta
Architettura
MATRICOLA
345678
123456
234567
345678
VOTO
27
30
18
22
345678
30
Quali Professori hanno
dato piu' di 24 a Teo
Verdi ed in quali corsi?
PROFESSORE CORSO
Programmazione Ferro
Architetture
Pappalardo
DB -Algebra Relazionale
3
OPERATORI DELL’ALGEBRA

Gli operatori primitivi dell’Algebra Relazionale
sono:
 Ridenominazione;
 Unione;
 Differenza;
 Proiezione;
 Restrizione
(o Selezione);
 Prodotto.

I simboli R,S,... denotano relazioni, A,
B,…attributi e X,Y,…insiemi di attributi
DB -Algebra Relazionale
4
Ridenominazione

Siano X gli attributi di R, A in X, B not in X .

Allora AB(R) è con attributi (X-{A}){B}

 AB(R)={t | u R t[B] = u[A]  t[C]=u[C]
se C e’ diverso da B}.
DB -Algebra Relazionale
5
ESEMPIO di Ridenominazione

Corso
Programmazione
EINN
Matricola
123456
23456
Voto
27
28
Corso
Programmazione
EINN
Codice Studente
123456
23456
Voto
27
28
Matricola  Codice Studente(Esami)
DB -Algebra Relazionale
6
Unione e Differenza



Siano R ed S relazioni dello stesso tipo allora
RS = {t | t R  t  S}
R-S = {t | t R  tS}
DB -Algebra Relazionale
7
Esempi
A
X
X
U
B
Y
Y
Y
C
Z
W
Z
A
X
X
B
Y
M
C
Z
W
S
S
R
R
A
X
X
U
X
B
Y
Y
Y
M
C
Z
W
Z
W
A
X
U
B
Y
Y
C
W
Z
R-S
R-S
RS
RS
DB -Algebra Relazionale
8
Proiezione

Sia R una relazione e siano A1, A2,…,
An alcuni suoi attributi allora:

 A1, A2,…, An (R) = {t[A1, A2,…, An ] |
tR}
DB -Algebra Relazionale
9
Esempio
A
X
X
U
B
Y
Y
Y
R
A
X
U
R
C
Z
W
Z
Proiezione
B
Y
Y
A,B (R)

A,B
(R)
DB -Algebra Relazionale
10
Restrizione(Selezione)



Sia R una relazione allora
  (R) = {t | t R  (t)}
dove  e’ una formula proposizionale
costruita a partire dagli atomi AB, dove A e
B sono attributi di R o costanti e   {=,<,
>}, utilizzando i connettivi proposizionali
,,.
DB -Algebra Relazionale
11
Esempio
A
X
X
U
B
Y
Y
Y
C
Z
W
Z
Selezione
R
A
X
X
B
Y
Y

C
Z
W
(R)
A=X

A=X
(R)
DB -Algebra Relazionale
12
Prodotto

Siano R(A1: T1,…, An: Tn) ed S (An+1: Tn+1,…,
An+m: Tn+m) con {A1,…, An} {An+1,…, An+m}=
. Allora si pone

R x S = {tu | tR  u  S}
DB -Algebra Relazionale
13
Esempio
A
X
X
B
Y
Y
D
X
X
C
Z
W
E
Y
M
R
R
A
X
X
X
X
SS
B
Y
Y
Y
Y
C
Z
Z
W
W
D
X
X
X
X
E
Y
M
Y
M
RxS
RxS
DB -Algebra Relazionale
14
Operatori Derivati
Sono operatori utili che si possono
esprimere in funzioni di quelli primitivi.
 Intersezione: Siano R ed S dello stesso
tipo

 RS

= {t | tR  t  S}.
Essa si può esprimere in funzione degli
operatori primitivi:
R
 S = R-(R-S)
DB -Algebra Relazionale
15
Divisione(Quoziente)

Divisione: Siano XY gli attributi di R ed Y
quelli di S, allora

R/S = {w | {w} x S  R}.

Per far vedere che / e’ derivato basta
osservare che R/S =  X (R) - T dove
T
=  X (( X (R) x S) - R).
DB -Algebra Relazionale
16
Uso della divisione

La divisione serve a rispondere a query del tipo:
trova tutte le n-uple di R associate a tutte le nuple di S. Ad esempio
 {‘DBI’,’Progr’}=
 Corso Corso=‘DBI’  Corso=‘Progr’
(Esami)
(
 Matricola,Corso Esami)/ {‘DBI’,’Progr’} = matricole
di studenti che hanno superato DBI e Progr.
DB -Algebra Relazionale
17
Giunzione(Equijoin)

Siano R(A1: T1,…, An: Tn) ed S (An+1: Tn+1,…,
An+m: Tn+m) con {A1,…, An}  {An+1,…, An+m}=
. Allora si pone
1 Ai = Ak S = {tu | tR, u  S , t.Ai =u.Ak}
 i=1…. n, k= n+1…. n+m.
 La giunzione e’ derivata perche’
 R 1 Ai = Ak S =  Ai = Ak (R x S)
R
DB -Algebra Relazionale
18
Studenti 1 Codice= MatricolaEsami
NOME
CODICE
Mario Rossi 123456
Ugo Bianchi 234567
INDIRIZZO TELEFONO
Via Etnea 1 222222
Via Roma 2 333333
CORSO
Architetture
Programmazione
MATRICOLA VOTO
123456
30
234567
18
NOME
CODICE
MATRICOLA
INDIRIZZO
TELEFONO
CORSO
VOTO
Mario Rossi
123456
123456
Via Etnea 1
222222
Architetture
30
Ugo Bianchi
234567
234567
Via Roma 2
333333
Programmazio
ne
18
DB -Algebra Relazionale
19
Giunzione Naturale(Natural join)


Siano R con attributi XY ed S con attributi YZ
R 1 S e’ una relazione di attributi XYZ costituita da
tutte le n-uple t tali che: t[XY] R , t[YZ]  S.




R 1 S = {t | t[XY]  R  t[YZ]  S}
La giunzione e’ derivata perché
Si rinominano gli attributi Y in S come Y’ e si ottiene S’.
Si opera la giunzione (equijoin) rispetto ad Y ed Y’. Si
proietta rispetto a XYZ
R 1 S=  XYZ (R 1 Y=Y’ S’)
DB -Algebra Relazionale
20
Studenti 1 Esami
NOME
MATRICOLA INDIRIZZO TELEFONO
Mario Rossi 123456
Via Etnea 1
222222
Ugo Bianchi 234567
Via Roma 2 333333
CORSO
Architetture
Programmazione
Architetture
MATRICOLA
123456
234567
234567
NOME
MATRICOLA
INDIRIZZO
TELEFONO
CORSO
VOTO
Mario Rossi
123456
Via Etnea 1
222222
Architetture
30
Ugo Bianchi
234567
Via Roma 2
333333
Programmazion
e
18
Ugo Bianchi
234567
Via Roma 2
333333
Architetture
27
DB -Algebra Relazionale
VOTO
30
18
27
21
Semi-giunzione(Semi-join)


Siano R con attributi XY ed S con attributi YZ
R  S e’ una relazione di attributi XY
costituita da tutte le n-uple di R che
partecipano a R 1 S.
semi-giunzione e’ derivata perché
 R  S=  XY (R 1 S)
 La
DB -Algebra Relazionale
22
Studenti  Esami
NOME
MATRICOLA INDIRIZZO TELEFONO
Mario Rossi 123456
Via Etnea 1
222222
Ugo Bianchi 234567
Via Roma 2 333333
Teo Verdi
345678
CORSO
Architetture
Programmazione
Architetture
MATRICOLA
123456
234567
234567
VOTO
30
18
27
Via Totino 3 444444
NOME
MATRICOLA
INDIRIZZO
TELEFONO
Mario Rossi
123456
Via Etnea 1
222222
Ugo Bianchi
234567
Via Roma 2
333333
DB -Algebra Relazionale
23
Giunzione Esterna

La giunzione esterna è la giunzione naturale
estesa con tutte le n-uple che non
appartengono alla giunzione naturale,
completate con valori null per gli attributi
mancanti. Siano R[XY],S[YZ]

R

S = (R 1 S) 
((R-  XY (R 1 S)){Z=null} 
{X=null}  ((S-  YZ (R 1 S)))
DB -Algebra Relazionale
24
Ordini 1/ Agenti
ORDINE
1
2
CLIENTE ARTICOLO AGENTE
123456
A1
222222
234567
A2
333333
3
345678
A3
444444
AGENTE
222222
333333
555555
ZONA
PISA
CATANIA
ROMA
ORDINE
CLIENTE
ARTICOLO
AGENTE
ZONA
1
123456
A1
222222
PISA
2
234567
A2
333333
CATANIA
3
345678
A3
444444
NULL
NULL
NULL
NULL
555555
ROMA
DB -Algebra Relazionale
25
Altre Giunzioni Esterne


Nelle giunzioni esterne sinistre e destre si
aggiungono solo le parti sinistre e destre.
Siano R[XY],S[YZ]
(giunzione esterna sinistra)
R

1  S = (R 1 S) 
((R-  XY (R 1 S){Z=null}
(giunzione esterna destra)
R
1  S = (R 1 S) 
{X=null}  ((S-  YZ (R 1 S)))
DB -Algebra Relazionale
26
Ordini 1  Agenti
ORDINE
1
2
CLIENTE ARTICOLO AGENTE
123456
A1
222222
234567
A2
333333
3
345678
A3
444444
AGENTE
222222
333333
555555
ZONA
PISA
CATANIA
ROMA
ORDINE
CLIENTE
ARTICOLO
AGENTE
ZONA
1
123456
A1
222222
PISA
2
234567
A2
333333
CATANIA
3
345678
A3
444444
NULL
DB -Algebra Relazionale
27
Ordini 1  Agenti
ORDINE
1
2
CLIENTE ARTICOLO AGENTE
123456
A1
222222
234567
A2
333333
3
345678
A3
444444
AGENTE
222222
333333
555555
ZONA
PISA
CATANIA
ROMA
ORDINE
CLIENTE
ARTICOLO
AGENTE
ZONA
1
123456
A1
222222
PISA
2
234567
A2
333333
CATANIA
NULL
NULL
NULL
555555
ROMA
DB -Algebra Relazionale
28
Unione Esterna
 Siano
R[XY], S[YZ] due relazioni
allora
 L’unione esterna R [  S si ottiene
estendendo le due tabelle con le
colonne dell’altro con valori nulli e si
fa l’unione.
DB -Algebra Relazionale
29
Esempio di Unione Esterna
A
X
X
X
X
B
Y
Y
Y
Y
C
Z
Z
W
W
R
B
Y
Y
Y
Y
D
X
X
X
X
C
Z
Z
W
W
D
X
X
X
X
S
E
Y
M
Y
M
S
R
A
X
X
X
X
NULL
NULL
NULL
NULL
B
Y
Y
Y
Y
Y
Y
Y
Y
C
Z
Z
W
W
Z
Z
W
W
D
X
X
X
X
X
X
X
X
E
NULL
NULL
NULL
NULL
Y
Y
Y
M
RU$ S
RUS
DB -Algebra Relazionale
30
Algoritmo di
Query Optimization
DB -Algebra Relazionale
31
Espressione Algebrica di Query

L’Algebra Relazionale può essere
utilizzata come linguaggio per interrogare
una base di dati.

Infatti consideriamo l’esempio del
database degli studenti costituito dalle tre
tabelle Studenti, Esami, Corsi.
DB -Algebra Relazionale
32
Esempio di Query

Supponiamo che vogliamo trovare tutti i
professori che hanno dato a Mario Rossi
piu’ di 27. (1 e’ natural join)

ProfessoreNome=‘Mario Rossi’& Voto>27 (Studenti 1
Esami 1 Corsi)
DB -Algebra Relazionale
33
Query Optimization

La stessa query
 PNome=‘Mario Rossi’& Voto>27
(Studenti 1 Esami 1
Corsi)

può essere espressa come
 P
(Nome=‘Mario Rossi’Studenti 1 ( Voto>27 Esami 1
Corsi))

Che risulta essere molto più efficiente!
DB -Algebra Relazionale
34
Regole per la query optimization
Anticipare l’applicazione delle proiezioni e
delle restrizioni rispetto al prodotto (e
quindi alle giunzioni), in modo da ridurre la
dimensione delle tabelle a cui applicare il
prodotto (e le giunzioni).
 Le seguenti regole possono essere
utilmente utilizzate per l’ottimizzazione di
espressioni:

DB -Algebra Relazionale
35
Regole sulla restrizione
1.
Raggruppamento di restrizioni
a.
2.
C(X) (C(Y)(E))=C(X)&C(Y)(E)
Commutativita’ di  e 
C(X)(Y(E))=Y(C(X)(E)) ,se XY;
b. Y(C(X)(XY(E)))=Y(C(X)(E))se X  Y.
a.
DB -Algebra Relazionale
36
Restrizione e Prodotto
3.
Anticipazione di  rispetto a .
a.
b.
c.
C(X)(E  F)= C(X)(E)  F, se X attr(E).
C(X)&C(Y)(E  F)= C(X)(E)  C(Y)(F), se X attr(E),
Y attr(F).
C(X)&C(Y)&C(Z)(E  F)= C(Z)( C(X)(E)  C(Y)(F)), se
X attr(E), Y attr(F), Z attr(E) , Z
attr(F)
DB -Algebra Relazionale
37
Regole per la proiezione
4.
Raggruppamento di proiezioni.
a.
5.
Eliminazione di proiezioni superflue.
a.
6.
X(Y(E))= X(E) , se XY.
X(E)=E , se X = attr.(E).
Anticipazione della  rispetto a .
a.
XY(E  F)= X(E)  Y(F) , se Xattr(E), Yattr.(F).
DB -Algebra Relazionale
38
L’ALGORITMO

Si applicano le seguenti tre regole
(per anticipare la selezione) finché è
possibile
Si anticipa  rispetto a  usando la 2.a.
B. Si raggruppano le restrizioni usando la 1.
C. Si anticipa l’esecuzione di  su  usando la
3.
A.
DB -Algebra Relazionale
39
Anticipazione delle proiezioni
Si eliminano le proiezioni superflue usando
la 5.
E. Si raggruppano le proiezioni mediante la
regola 4.
F. Si anticipa l’esecuzione delle proiezioni
rispetto al prodotto usando ripetutamente la
2 (quando E è un prodotto, da destra verso
sinistra) e la 6.
D.
DB -Algebra Relazionale
40
Esercitazioni?
DB -Algebra Relazionale
41