ALGEBRA RELAZIONALE - diee.unica.itgiacinto/didattica/05BD.Algebra Relazionale.pdf · ALGEBRA...

ALGEBRARELAZIONALE

Giorgio Giacinto 2010 Basi di Dati 2

Linguaggi di interrogazionerelazionale! Linguaggi di interrogazione (LI) permettono la

manipolazione e il reperimento di dati da una basedi dati

! Il modello relazionale supporta LI semplici e potenti! Forte base formale basata sulla logica! Ottimizzazione

! Linguaggi di interrogazione ! linguaggi diprogrammazione!! I LI non sono necessariamente “Turing completi”! I LI non sono fatti per essere usati in calcoli complessi! I LI supportano un accesso semplice ed efficiente a grandi

insiemi di dati


Linguaggi formali diinterrogazione relazionale! Due linguaggi di interrogazione matematici

formano la base per i linguaggi “reali” (es.SQL) e per l’implementazione! Algebra relazionale: operazionale, utilissima

per rappresentare i piani di esecuzione! Calcolo relazionale: permette agli utenti di

descrivere ciò che vogliono, piuttosto che ilmodo in cui calcolarlo (non operazionale, madichiarativo)

! Capire l’algebra e il calcolo è la chiave per la comprensionedell’SQL e dell’elaborazione delle interrogazioni!


Nozioni Preliminari! Una interrogazione si applica alle istanze di

relazione, e il risultato di una interrogazione èanch’esso una istanza di relazione! Gli schemi delle relazioni in ingresso sono fissi! Anche lo schema per il risultato di una data interrogazione

è fisso e determinato dalla definizione dei costrutti dellinguaggio di interrogazione.

! Notazione posizionale rispetto a notazione nominaledei campi! La notazione posizionale è più semplice per definizioni

formali, la notazione nominale è più leggibile! In SQL sono usate entrambe


Schema base di dati diesempio

Velisti(vid:integer,vnome:string, esperienza:integer,età:real)

Barche(bid:integer,bnome:string, colore:string)

Prenotazioni(vid:integer,bid:integer, giorno:data)


Istanze diesempio

P1

V1

V2

Useremo la notazioneposizionale o a campinominati.Useremo laconvenzione che inomi dei campi neirisultati delleinterrogazioni siano“ereditati” dai nomi deicampi delle relazioni iningresso.

vid bid giorno 22 101 10/10/96 58 103 11/12/96

vid vnome espe-rienza

età

22 dustin 7 45.0 31 lubber 8 55.5 58 rusty 10 35.0


età

28 yuppy 9 35.0 31 lubber 8 55.5 44 guppy 5 35.0 58 rusty 10 35.0


Algebra relazionale!Operazioni di base

!Proiezione (!)Cancella colonne non desiderate dalla relazione

!Selezione (")Seleziona un sottoinsieme di righe della relazione

!Prodotto cartesiano (!)Consente di combinare due relazioni

!Differenza insiemistica (")Tuple presenti nella relazione 1, ma non nella relazione 2

!Unione (#)Tuple presenti nella relazione 1 e nella relazione 2


Altre Operazioni diAlgebra Relazionale

! Altre operazioni! intersezione, join, divisione, ridenominazione

non essenziali ma (molto!) utili! Poiché ogni operazione restituisce una relazione,

le operazioni possono essere composte (l’algebraè “chiusa”)


Proiezione! Cancella gli attributi che non sono

nella lista di proiezione! Lo schema del risultato contiene

esattamente i campi nella lista diproiezione, con gli stessi nomi cheavevano nella (unica) relazione iningresso

! L’operatore di proiezione deveeliminare i duplicati (perché??)! Nota: i sistemi reali tipicamente non

eliminano i duplicati a meno chel’utente non lo richiedaesplicitamente (perché no?)

rusty 10

vnome espe -rienza

yuppy 9 lubber 8 guppy 5

!vnome,esperienza (V2)

età 35.0 55.5

!età (V2)


Selezione! Seleziona le righe che

soddisfano una condizione(<, >, =, ", #, ! , ¬, $, %)

! Niente duplicati nelrisultato! (Perché?)

! Lo schema del risultato èidentico allo schema della(unica) relazione iningresso

! La relazione risultato puòessere l’ingresso perun’altra operazione dialgebra relazionale!(Composizione dioperatori)


età

28 yuppy 9 35.0 58 rusty 10 35.0

! esperienza>8 (V2)

vnome espe-rienza

yuppy 9 rusty 10

"vnome,esperienza(!esperienza>8 (V2))


Unione, intersezione, differenzainsiemistica! Tutte queste operazioni

prendono in ingresso duerelazioni che devono esserecompatibili rispetto all’unione! stesso numero di campi! campi “corrispondenti” sono

dello stesso dominio! Qual è lo schema del risultato?

vid vnome espe-rienza età

22 dustin 7 45.0 31 lubber 8 55.5 58 rusty 10 35.0 44 guppy 5 35.0 28 yuppy 9 35.0

V1#V2


31 lubber 8 55.5 58 rusty 10 35.0

V1&V2


22 dustin 7 45.0

V1 – V2


Prodotto cartesianoV1 ' P1

! Ciascuna riga di V1 è accoppiata con ciascuna riga diP1

! Lo schema del risultato ha un campo per ogni campo diV1 e P1, i cui nomi sono, se possibile, “ereditati”! Conflitto: sia V1 che P1 hanno un campo chiamato vid

! Operatore per ridenominare i campi ((C(1 → vid1, 5 → vid2), V1 ! P1)

(vid) vnome espe-rienza

età (vid) bid giorno

22 dustin 7 45.0 22 101 10/10/96 22 dustin 7 45.0 58 103 11/12/96 31 lubber 8 55.5 22 101 10/10/96 31 lubber 8 55.5 58 103 11/12/96 58 rusty 10 35.0 22 101 10/10/96 58 rusty 10 35.0 58 103 11/12/96


Join

• Join condizionale: = "c(P $ V)! Lo schema del risultato è lo stesso del prodotto

scalare! Meno tuple del prodotto scalare

! potrebbe essere calcolato più efficientemente! A volte chiamato theta-join

(vid) vnome espe-rienza età (vid) bid giorno

22 dustin 7 45.0 58 103 11/12/96 31 lubber 8 55.5 58 103 11/12/96

P !"c V

V1 !"V1.vid <P1.vid P1


Join! Equi-join: un caso speciale di join condizionale dove

la condizione c contiene solo uguaglianze! Lo schema del risultato è simile al prodotto scalare,

ma c’è solo una copia dei campi per i quali èspecificata l’uguaglianza

! Join naturale: equi-join su tutti i campi in comune


età bid giorno

22 dustin 7 45.0 101 10/10/96 58 rusty 10 35.0 103 11/12/96

V1!"V1.vid =P1.vid P1


Divisione! Non supportata come operatore primitivo, ma utile per

esprimere interrogazioni comeTrovare i velisti che hanno prenotato tutte le barche

! Sia A una relazione con due campi, x e ysia B una relazione con il solo campo y! A/B = {)x* | +)y* , B, -)x, y* , A}

cioè, A/B contiene tutte le tuple x (velisti) tali che per ogni tupla y(barca) in B, ci sia una tupla xy in AoppureSe l’insieme di valori y (barche) associato con un valore x (velista)in A contiene tutti i valori y in B, il valore x è in A/B

! In generale, x e y possono essere un qualunque elenco dicampi! y è l’elenco di campi in B! x # y è l’elenco dei campi in A


Esempi di divisione A/B

sno pnos1 p1s1 p2s1 p3s1 p4s2 p1s2 p2s3 p2s4 p2s4 p4

pnop2

pnop2p4

pnop1p2p4

snos1s2s3s4

snos1s4

snos1

A

B1B2

B3A/B1A/B2

A/B3


Esprimere A/B usandooperatori di base! La divisione non è una operazione essenziale ma solo

un’utile scorciatoia! Vero anche per i join, ma i join sono così comuni che i

sistemi li implementano esplicitamente! Idea: per A/B, calcolare tutti i valori x che non sono

“interdetti” da qualche valore y in B! Un valore x è “interdetto” se associandogli valori y da B

otteniamo una tupla xy che non è in A

Valori x interdetti:

A/B !x ((!x(A)!B)"A)

! x A( ) " Tutte le tuple interdette


Istanze per alcuni esempi


Trovare i nomi dei velisti che hannoprenotato la barca #103

! Soluzione 1:

! Soluzione 2:

! Soluzione 3:

"vnome ((!bid=103 Prenota) Velisti)

! "( , Re )Temp servesbid1 103=Prenota

! ( , )Temp Temp Sailors2 1!" Velisti)

"vnome(Temp2)

"vnome ((!bid=103 (Prenota Velisti)


Trovare i nomi dei velisti chehanno prenotato una barca rossa

• Informazioni sul colore sono disponibili solo inBarche, quindi abbiamo bisogno di un ulteriore join

• Una soluzione più efficiente

! Un ottimizzatore di interrogazioni può trovare la secondasoluzione data la prima!

"vnome((!colore=‘rosso’Barche) Prenota Velisti

"vnome("vid(("bid!colore=‘rosso’Barche) Prenota) Velisti)


#(Tempbarche, (!colore=‘rosso’ % colore=‘verde’Barche))

"vnome(Tempbarche Prenota Velisti)

Trovare i nomi dei velisti che hannoprenotato una barca rossa o una verde

! Possiamo identificare tutte le barche rosse o verdi,poi trovare i velisti che hanno prenotato una di esse

! Possiamo anche definire TempBarche usandol’unione (come?)

! Che succede se % è sostituito da $ in questainterrogazione?


#(Temprosse,!vid ((!colore=‘rosso’ Barche) Prenota)

#(Tempverdi,!vid ((!colore=‘verde’ Barche) Prenota)

"vnome(Temprosse & Tempverdi) Velisti)

Trovare i nomi dei velisti che hannoprenotato una barca rossa e una verde

! L’approccio precedente non funziona! Dobbiamoidentificare i velisti che hanno prenotato barcherosse, i velisti che hanno prenotato barche verdi, poitrovare l’intersezione (notate che vid è una chiaveper Velisti)


!(Prenotate,"vid ,vnome,bid (Velisti !"Prenotazioni)

!(CoppiePrenotate(1! vid1,2! vnome, 3! bid1,4! vid2,5! vnome2, 6! bid2),Prenotate"Prenotate)"vnome1#(vid1=vid 2)#(bid1$bid 2)CoppiePrenotate

Trovare i nomi dei velisti che hannoprenotato almeno due barche

! Occorre trovare tutte le tuple di Prenotateriferite allo stesso velista ma con barcheprenotate diverse.! Per confrontare tuple di una stessa relazione

serve un join fra due copie della stessa relazione


Trovare i nomi dei velisti che hannoprenotato tutte le barche

! Uso della divisione! gli schemi delle relazioni in ingresso alla divisione devono

essere scelti con cura

# (Tempvids, ("vid,bid Prenota) / ("bidBarche))

"vnome (Tempvids Velisti)

! Per trovare i velisti che hanno prenotato tutte lebarche “Interlago”

..... / "bid (!bnome=‘Interlago’Barche)


Altre interrogazioni

1. Trovare i colori delle barche prenotate daLubber

2. Trovare i nomi dei velisti che hannoprenotato almeno una barca

3. Trovare i vid dei velisti con età superiore a20 che non hanno prenotato una barcarossa

4. Trovare il nome del velista più giovane5. Trovare i dati della prenotazione più vecchia


Soluzioni! colore B1!" !bid ! vid " vnome=LubberV 3( )!" P2( )( )( )! vnome V 3!" ! vidP2( )( )

V 4 = ! vid ,età V 3( )V5 = ! vid1,età1 " età1>età2 # (1$ vid1,2$ età1,3$ vid2,4$ età2)V 4 %V 4( )( )! vnome V 3!" ! vid V 4 &V5( )( )

! vid " età>20 V 3( )( )#! vid P2( )$! vid P2 !" !bid " colore=rossoB1( )( )

1.

2.

3.

4.

ALGEBRA RELAZIONALE - diee.unica.itgiacinto/didattica/05BD.Algebra Relazionale.pdf · ALGEBRA...

Documents

Transcript of ALGEBRA RELAZIONALE - diee.unica.itgiacinto/didattica/05BD.Algebra Relazionale.pdf · ALGEBRA...