Linguaggi per basi di dati - Università degli Studi di ... · Basi di dati – Paolo Zirilli...

1

1

Basi di dati – Paolo Zirilli [email protected]

Capitolo 3:

ALGEBRA RELAZIONALE

2


Linguaggi per basi di dati

• operazioni sullo schema

• DDL: data definition language

• operazioni sui dati

• DML: data manipulation language

• interrogazione ("query")

• aggiornamento

3


Linguaggi di interrogazioneper basi di dati relazionali

• Dichiarativi

• specificano le proprietà del risultato

("che cosa")

• Procedurali

• specificano le modalità di generazione

del risultato ("come")

4


Linguaggi di interrogazione

• Algebra relazionale: procedurale

• Calcolo relazionale:

dichiarativo (teorico)

SQL (Structured Query Language):

parzialmente dichiarativo (reale)

• QBE (Query by Example):

dichiarativo (reale)

2

5


Algebra relazionale

• Insieme di operatori con 3 caratteristiche:

• definito su relazioni

• producono relazioni

• possono essere composti

l”algebra è chiusa

6


• Operazioni di base

• Selezione (σ) Seleziona un sottoinsieme di righe della relazione

• Proiezione (π) Cancella righe non desiderate dalla 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:

• intersezione, join, divisione, ridenominazione: non essenziali ma (molto!) utili

• Poiché ogni operazione restituisce una relazione, le operazioni possono essere composte (l’algebra è “chiusa”)

Algebra relazionale: linguaggio procedurale costituito da un insieme

di operatori definiti su relazioni

7


Operatori dell'algebra relazionale

• unione, intersezione, differenza

• ridenominazione

• selezione

• proiezione

• join (join naturale, prodotto cartesiano,

theta-join)

monadici

8


Operatori insiemistici

• le relazioni sono insiemi

• i risultati debbono essere relazioni

• è possibile applicare unione, intersezione,

differenza solo a relazioni definite sugli

stessi attributi

3

9


Laureati

Matricola

7432

9824

Età

54

45

Nome

Neri

Verdi

7274 42Rossi

Quadri

Matricola

7432

9824

9297

Età

54

45

33

Nome

Neri

Verdi

Neri

Laureati ∪ Quadri

Matricola EtàNome

7432 54Neri

9824 45Verdi

9297 33Neri

7274 42Rossi

7432 54Neri

9824 45Verdi

7274 42Rossi

7432 54Neri

9824 45Verdi

9297 33Neri

7432 54Neri

9824 45Verdi

9297 33Neri

7274 42Rossi

Unione

10


Laureati

Matricola

7432

9824

Età

54

45

Nome

Neri

Verdi

7274 42Rossi

Quadri

Matricola

7432

9824

9297

Età

54

45

33

Nome

Neri

Verdi

Neri

Laureati ∩ Quadri

Matricola EtàNome

7432 54Neri

9824 45Verdi

7432 54Neri

9824 45Verdi

7432 54Neri

9824 45Verdi

7432 54Neri

9824 45Verdi

Intersezione

11


Laureati

Matricola EtàNome

7432 54Neri

9824 45Verdi

7274 42Rossi

Quadri

Matricola

7432

9824

9297

Età

54

45

33

Nome

Neri

Verdi

Neri

Laureati – Quadri

Matricola EtàNome

7432 54Neri

9824 45Verdi

7274 42Rossi

7432 54Neri

9824 45Verdi

7274 42Rossi

Differenza

12


Paternità

Padre Figlio

Adamo Caino

Abramo Isacco

Adamo Abele

Maternità

Madre Figlio

Eva Set

Sara Isacco

Eva Abele

Paternità ∪ Maternità

??

Un’unione sensata ma impossibile

4

13


Ridenominazione

• operatore monadico (con un argomento)

• "modifica lo schema" lasciando inalterata

l'istanza dell'operando

14


Operatore di Ridenominazione (ρ REN)

Sia r una relazione definita sull’insieme di attributi X e sia Y un (altro) insieme di attributi con la stessa cardinalità. Siano A1 A2... Ak ed B1 B2... Bk rispettivamente un ordinamento per gli attributi in X ed Y allora la RIDENOMINAZIONE

ρB1B2..Bk -> A1A2..Ak

(r)

Contiene una tupla t’ per ciascuna tupla t in r tale che t’[Bi]=t[Ai] i=1,...,n

15


Operatore di Ridenominazione2 (ρ REN)

La RIDENOMINAZIONE modifica solamente il nome degli

attributi agendo sullo schema della relazione e lasciando inalterata la sua istanza

ρ (R(F),E) R=nome nuovo, E relazione F lista di ridenominazione :

posizione nuovonome

nuovonome vecchionome

16


Paternità

Padre Figlio

Adamo Caino

Abramo Isacco

Adamo Abele

RENGenitore ← Padre (Paternità)

Padre Figlio

Adamo Caino

Abramo Isacco

Adamo Abele

Genitore

5

17


Paternità

Padre Figlio

Adamo Caino

Abramo Isacco

Adamo Abele

Maternità

Madre Figlio

Eva Set

Sara Isacco

Eva Abele


Genitore Figlio

Adamo Caino

Abramo Isacco

Adamo Abele

RENGenitore ← Madre (Maternità)

Genitore Figlio

Eva Set

Sara Isacco

Eva Abele

18



RENGenitore ← Madre (Maternità)

Genitore Figlio

Adamo Caino

Abramo Isacco

Adamo Abele

Genitore Figlio

Eva Set

Sara Isacco

Eva Abele

Genitore Figlio

Adamo Caino

Abramo Isacco

Adamo Abele

Eva Set

Sara Isacco

Eva Abele


RENGenitore ← Madre (Maternità) ∪

19


REN Sede, Retribuzione ← Ufficio, Stipendio (Impiegati)

REN Sede, Retribuzione ← Fabbrica, Salario (Operai) ∪

Impiegati Cognome

Neri

Rossi

Ufficio

Milano

Roma

Stipendio

64

55

Operai Cognome

Verdi

Bruni

Fabbrica

Latina

Monza

Salario

55

45

Cognome RetribuzioneSede

Neri

Rossi

64

55

Milano

Roma

Verdi

Bruni

Latina

Monza

55

45

20


Selezione

• operatore monadico

• produce un risultato che

• ha lo stesso schema dell'operando

• contiene un sottoinsieme delle ennuple

dell'operando,

• quelle che soddisfano una condizione

6

21


Impiegati

Cognome Filiale StipendioMatricola

Neri Milano 645998

Rossi Roma 557309

Neri Napoli 645698

Milano Milano 449553

• impiegati che

• guadagnano più di 50

• guadagnano più di 50 e lavorano a Milano

• hanno lo stesso nome della filiale presso cui lavorano

22


Selezione, sintassi e semantica

• sintassi

SEL Condizione (Operando)

• Condizione: espressione booleana

(come quelle dei vincoli di ennupla)

• semantica

• il risultato contiene le ennuple

dell'operando che soddisfano la

condizione

23


Operatore di Selezione (σ)

σeta’=18(S)

18

19

18

età

3.8bi@ttBianchi0033

3.2bi@ecVerdi0072

3.4ro@ecRossi0012

gpaloginnomesid

18

18

età

3.8bi@ttBianchi0033

3.4ro@ecRossi0012

gpaloginnomesid

S

Produce una relazione avente lo stesso schema di r econtenente le tuple di r per le quali F e’ vera

σF(r)

Formula proposizionale F su X è una formula booleana (¬,٨,٧) di termini T.

Dove T e’ definito come:

attr op attr o attr op c

op è un operatore di confronto (=,≠,≤,≥,<,>);

Formula proposizionale

24



Neri Milano 645998

Rossi Roma 557309

Neri Napoli 645698


Impiegati


• impiegati che guadagnano più di 50

SELStipendio > 50 (Impiegati)

Neri Napoli 645698

SELStipendio > 50 (Impiegati)

7

25


Impiegati


Neri Milano 645998

Rossi Roma 557309

Neri Napoli 645698


• impiegati che guadagnano più di 50 e lavorano a Milano

SELStipendio > 50 AND Filiale = 'Milano' (Impiegati)

Rossi Roma 557309

Neri Napoli 645698


Neri Milano 645998

SELStipendio > 50 AND Filiale = 'Milano' (Impiegati)

26


Impiegati


Neri Milano 645998

Rossi Roma 557309

Neri Napoli 645698


• impiegati che hanno lo stesso nome della filiale presso cui lavorano

SEL Cognome = Filiale(Impiegati)

Neri Milano 645998

Rossi Roma 557309

Neri Napoli 645698


SEL Cognome = Filiale(Impiegati)

27


Selezione e proiezione

• operatori "ortogonali"

• selezione:

• decomposizione orizzontale

• proiezione:

• decomposizione verticale

28


selezione

proiezione

8

29


Proiezione

• operatore monadico

• produce un risultato che

• ha parte degli attributi dell'operando

• contiene ennuple cui contribuiscono

tutte le ennuple dell'operando

30


Impiegati


Neri Milano 645998

Neri Napoli 557309

Rossi Roma 645698

Rossi Roma 449553

• per tutti gli impiegati:

• matricola e cognome

• cognome e filiale

31


Proiezione, sintassi e semantica

• sintassi

PROJ ListaAttributi (Operando)

• semantica

• il risultato contiene le ennuple ottenute

da tutte le ennuple dell'operando

ristrette agli attributi nella lista

32


Operatore di Proiezione (π)

π età (S)

18

19

18

età

3.8bi@ttBianchi0033

3.2bi@ecVerdi0072

3.4ro@ecRossi0012

gpaloginnomesid

19

18

età

S

Tutte le tuple della relazione r contribuiscono al risultato di unaproiezione, ma soltanto con i valori corrispondenti agli attributispecificati dalla condizione C.

π C(r)

Distinte

Condizione

Condizione di proiezione C su r è l’elenco degli attributi dello schema X di r che debbono venire ‘proiettati’:

attr1, attr2 , ... ,attrn

attriЄX per 1≥i≤n

9

33



Neri Milano 645998

Neri Napoli 557309

Rossi Roma 645698

Rossi Roma 449553

• matricola e cognome di tutti gli impiegati

PROJ Matricola, Cognome (Impiegati)

34



Neri Milano 645998

Neri Napoli 557309

Rossi Roma 645698

Rossi Roma 449553

• cognome e filiale di tutti gli impiegati

PROJ Cognome, Filiale (Impiegati)

35


Cardinalità delle proiezioni

• una proiezione

• contiene al più tante ennuple quante

l'operando

• può contenerne di meno

• se X è una superchiave di R, allora

PROJX(R) contiene esattamente tante

ennuple quante R

36


Selezione e proiezione

• Combinando selezione e proiezione,

possiamo estrarre interessanti informazioni

da una relazione

10

37



Neri Milano 645998

Rossi Roma 557309

Neri Napoli 645698

Milano Milano 449553 Milano Milano 449553 Neri Napoli 645698

• matricola e cognome degli impiegati che guadagnano più di 50

SELStipendio > 50 (Impiegati) PROJMatricola,Cognome ( )

38


• Combinando selezione e proiezione,

possiamo estrarre informazioni da una

relazione

• non possiamo però correlare

informazioni presenti in relazioni diverse,

né informazioni in ennuple diverse di

una stessa relazione

39


Esempi di divisione A/B

sno pno

s1 p1

s1 p2

s1 p3

s1 p4

s2 p1

s2 p2s3 p2

s4 p2

s4 p4

pno

p2

p4

pno

p1

p2

p4

A

B1B2

B3

A/B1 A/B2 A/B3

sno

s1

s2

s3

s4

pno

p2

sno

s1

s4

sno

s1

40


Operazione di Divisione

p4s1

p3s1

p2s1

p1s2

p2

p1

pno

s3

s1

sno

Non e’ supportato come primitiva ma e’ utile per esprimere query del tipo:Trova i marinai che hanno prenotato tutte le barcheA/B={ <x> | ∃∃∃∃<x,y>ЄA ∀∀∀∀<y>ЄB }

A/B

s1

s3

snoA/B1

p2

pno

B1

A B2p4

p2

pno A/B2

s1

sno

11

41


Divisione• Sia A una relazione con due campi, x e y; sia B una

relazione con il solo campo y:

• a/b = {⟨x⟩ | ⟨x, y⟩ ∈ A , ⟨y⟩ ∈ B}• cioè, A/B contiene tutte le tuple x (velisti) tali che per

ogni tupla y (barca) in B, ci sia una tupla xy in A

• Oppure. Se 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 di campi; y è l’elenco di campi in B, e x ∪ y è l’elenco dei campi in A

42


Esempi di divisione A/B

sno pno

s1 p1

s1 p2

s1 p3

s1 p4

s2 p1

s2 p2

s3 p2

s4 p2

s4 p4

pno

p2

p4

pno

p1

p2

p4

A

B1B2

B3

A/B1 A/B2 A/B3

sno

s1

s2

s3

s4

pno

p2

sno

s1

s4

sno

s1

43


Esprimere A/B usando operatori di base

• La divisione non è una operazione essenziale; 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 interdette44


Join

• il join è l'operatore più interessante

dell'algebra relazionale

• permette di correlare dati in relazioni

diverse

12

45


Prove scritte in un concorso pubblico

• I compiti sono anonimi e ad ognuno è

associata una busta chiusa con il nome del

candidato

• Ciascun compito e la relativa busta

vengono contrassegnati con uno stesso

numero

46


1 25

2 13

3 27

4 28

1 Mario Rossi

2 Nicola Russo

3 Mario Bianchi

4 Remo Neri

25Mario Rossi

13Nicola Russo

27Mario Bianchi

28Remo Neri

47


1 25

2 13

3 27

4 28

Numero Voto

1 Mario Rossi

2 Nicola Russo

3 Mario Bianchi

4 Remo Neri

Numero Candidato

25Mario Rossi

13Nicola Russo

27Mario Bianchi

28Remo Neri

VotoCandidato

1

2

3

4

Numero

48


Join naturale

• operatore binario (generalizzabile)

• produce un risultato

• sull‘ unione degli attributi degli

operandi

• con ennuple costruite ciascuna a partire

da una ennupla di ognuno degli operandi

Le enn sono ottenute combinando le tuple

con valori uguali sugli attributi in comune

13

49


Join, sintassi e semantica

• R1(X1), R2(X2)

• R1 JOIN R2 è una relazione su X1X2

{ t su X1X2 | esistono t1∈R1e t2∈R2

con t[X1] =t1 e t[X2] =t2 }

50


A Mori

B Bruni

Reparto Capo

Rossi A

Neri B

Bianchi B

Impiegato Reparto

Rossi A Mori

Neri B Bruni

Impiegato Reparto Capo

Bianchi B Bruni

Rossi A

Neri B

Bianchi B

Rossi A

Neri B

Bianchi B

A Mori

B Bruni

A Mori

B BruniB BruniB Bruni

• ogni ennupla contribuisce al risultato:

• join completo

51


Neri B Mori


Bianchi B Mori

Impiegato Reparto

Rossi A

Neri B

Bianchi B

Reparto Capo

B Mori

C Bruni

A

C

Un join non completo

52


Impiegato Reparto

Rossi A

Neri B

Bianchi B

Reparto Capo

D Mori

C Bruni


Un join vuoto

14

53



Rossi A

Neri B

Impiegato Reparto

Rossi A

Neri B

Rossi B

Neri B

A Mori

B Bruni

Reparto Capo

A Mori

B Bruni

B Mori


Rossi B Mori

Neri B Mori

Neri B Bruni

Rossi B Bruni

Un join completo, con n x m ennuple

54


Cardinalità del join

• Il join di R1 e R2 contiene un numero di ennuple …• compreso fra zero e il prodotto di |R1| e |R2|

• se il join coinvolge una chiave di R2, allora il numero di ennuple è …• compreso fra zero e |R1|

• se il join coinvolge una chiave di R2 e un vincolo di integrità referenziale, allora il numero di ennuple è• pari a |R1|

55


Cardinalità del join, 2

• R1(A,B) , R2 (B,C)

• in generale

0 ≤ |R1 JOIN R2| ≤ |R1| × |R2| • se B è chiave in R2

0 ≤ |R1 JOIN R2| ≤ |R1|• se B è chiave in R2 ed esiste vincolo di

integrità referenziale fra B (in R1) e R2:

|R1 JOIN R2| = |R1|

56


Impiegato Reparto

Rossi A

Neri B

Bianchi B

Reparto Capo

B Mori

C Bruni

Neri B Mori


Bianchi B Mori

A

C

Join, una difficoltà

• alcune ennuple non contribuiscono al risultato: vengono "tagliate fuori"

15

57


Join esterno

• Il join esterno estende, con valori nulli, le

ennuple che verrebbero tagliate fuori da un

join (interno)

• esiste in tre versioni:

• sinistro, destro, completo

58


Join esterno

• sinistro: mantiene tutte le ennuple del

primo operando, estendendole con valori

nulli, se necessario

• destro: ... del secondo operando ...

• completo: … di entrambi gli operandi ...

59


Impiegato Reparto

Rossi A

Neri B

Bianchi B

Impiegati

Reparto Capo

B Mori

C Bruni

Reparti

Neri B Mori


Bianchi B Mori

Impiegati JOINLEFT Reparti

C

Rossi A NULL

ARossi

60


Impiegato Reparto

Rossi A

Neri B

Bianchi B

Impiegati

Reparto Capo

B Mori

C Bruni

Reparti

Neri B Mori


Bianchi B Mori

Impiegati JOINRIGHT Reparti

A

NULL C Bruni

C Bruni

16

61


Impiegato Reparto

Rossi A

Neri B

Bianchi B

Impiegati

Reparto Capo

B Mori

C Bruni

Reparti

Neri B Mori


Bianchi B Mori

Impiegati JOINFULL Reparti

NULL C Bruni

C Bruni

ARossi

Rossi A NULL

62


Join e proiezioni

Impiegato Reparto

Rossi A

Neri B

Bianchi B

Reparto Capo

B Mori

C Bruni

Neri B Mori


Bianchi B Mori

Impiegato Reparto

Neri B

Bianchi B

Reparto Capo

B Mori

63


Proiezioni e join

Neri B Mori


Bianchi B Bruni

Verdi A Bini

Neri BImpiegato Reparto

Bianchi BVerdi A

B MoriReparto Capo

B BruniA Bini

Verdi A Bini

Neri B Mori


Neri B BruniBianchi B Mori

Bianchi B Bruni

64


Join e proiezioni

• R 1(X1), R 2(X2)

PROJX1 (R 1 JOIN R2 ) ⊆ R 1

• R(X), X = X1 ∪ X2

(PROJX1 (R)) JOIN (PROJX2

(R)) ⊇ R

17

65


Prodotto cartesiano

• un join naturale su relazioni senza attributi

in comune

• contiene sempre un numero di ennuple

pari al prodotto delle cardinalità degli

operandi

(le ennuple sono tutte combinabili )

Se l’insieme di attributi sono disgiunti ?

66


Rossi A

Neri B

Bianchi B

Impiegato Reparto

Impiegati

A Mori


Codice Capo

Reparti

Impiegati JOIN Reparti

Impiegato Reparto CapoCodice

Rossi A MoriAAARossi A B Bruni

Neri B MoriA

Neri B B Bruni

Bianchi B MoriA

Bianchi B B Bruni

67


• Il prodotto cartesiano, in pratica, ha senso

(quasi) solo se seguito da selezione:

SELCondizione (R1 JOIN R2)

• L'operazione viene chiamata theta-join e

indicata con

R1 JOINCondizione R2

n.b. sul libro di testo chiamato join condizionale

68


Perché "theta-join"?

• La condizione C è spesso una congiunzione

(AND) di atomi di confronto A1ϑ A2 dove ϑ è uno degli operatori di confronto (=, >, <, …)

18

69


Operazioni di join

R��CS

Condizione di Join

55.5

45.0

age

103

103

bid

58

58

(sid)

8

7

rating

11/12/02Luca31

11/12/02Davide22

daysname(sid)

R��S1.sid<R1.sidS

σC(RXS)=

La relazione risultante avrà lo schema del prodotto cartesiano di R ed S e l’istanza composta dalle tuple delprodotto cartesiano che soddisfano la condizione C

Senza nome

70


Operazioni di Equi-Join e Natural-Join

R��CS

Condizione di Join

35.0

45.0

age

103

101

bid

58

22

(sid)

10

7

rating

11/12/02Remo58

11/10/03Davide22

daysname(sid)

R��sidS

Equi-Join è un join in cui la condizione C e’ composta solamente di operazioni di uguaglianza.Natural Join e’un Equi-Join su tutti gli attributi in comune

X

Viene eliminata

71


Equi-join

• Se l'operatore di confronto nel theta-join èsempre l'uguaglianza (=) allora si parla di equi-join

Nota: ci interessa davvero l’equi-join, non il theta-join più generale

Perché ?

correla dati in relazioni diverse confrontando i

valori ….72


Rossi A

Neri B

Bianchi B

Impiegato Reparto

Impiegati

A Mori


Codice Capo

Reparti

Impiegati JOINReparto=Codice Reparti

Impiegato Reparto CapoCodice

Rossi A MoriAAARossi A B Bruni

Neri B MoriA

Neri B B Bruni

Bianchi B MoriA

Bianchi B B Bruni

Rossi A MoriAAANeri B B Bruni

Bianchi B B Bruni

19

73


Rossi A

Neri B

Bianchi B

Impiegato Reparto

Impiegati

A Mori


Reparto Capo

Reparti


74


Join naturale ed equi-join

Impiegato Reparto

Impiegati

Reparto Capo

Reparti


PROJImpiegato,Reparto,Capo (

)RENCodice ← Reparto (Reparti)Impiegati JOIN

SELReparto=Codice

( )

75


Esempi

Impiegati Nome Età StipendioMatricola

Bianchi 37 385998

Rossi 34 457309

Bruni 43 425698

Neri 42 359553

Mori 45 504076

Lupi 46 608123

Supervisione Impiegato Capo

5998

7309

5698

9553

4076

5698

5698

4076

4076

812376


Esempi


Bianchi 37 385998

Rossi 34 457309

Bruni 43 425698

Neri 42 359553

Mori 45 504076

Lupi 46 608123


5998

7309

5698

9553

4076

5698

5698

4076

4076

8123

20

77


• Trovare matricola, nome, età e stipendio

degli impiegati che guadagnano più di 40

SELStipendio>40(Impiegati)


Bianchi 37 385998Rossi 34 457309

Bruni 43 425698Neri 42 359553

Mori 45 504076Lupi 46 608123


59987309

56989553

4076

56985698

40764076

8123

78


• Trovare matricola, nome ed età degli

impiegati che guadagnano più di 40

PROJMatricola, Nome, Età (SELStipendio>40(Impiegati))


Bianchi 37 385998Rossi 34 457309

Bruni 43 425698Neri 42 359553

Mori 45 504076Lupi 46 608123


59987309

56989553

4076

56985698

40764076

8123

79


• Trovare le matricole dei capi degli impiegati

che guadagnano più di 40

PROJCapo (Supervisione

JOIN Impiegato=Matricola

(SELStipendio>40(Impiegati)))


59987309

56989553

4076

56985698

40764076

8123


Bianchi 37 385998Rossi 34 457309

Bruni 43 425698Neri 42 359553

Mori 45 504076Lupi 46 608123 80


• Trovare nome e stipendio dei capi degli

impiegati che guadagnano più di 40PROJNome,Stipendio (

Impiegati JOIN Matricola=Capo

PROJCapo(SupervisioneJOIN Impiegato=Matricola (SELStipendio>40(Impiegati))))


59987309

56989553

4076

56985698

40764076

8123


Bianchi 37 385998Rossi 34 457309

Bruni 43 425698Neri 42 359553

Mori 45 504076Lupi 46 608123

21

81


• Trovare gli impiegati che guadagnano più del

proprio capo, mostrando matricola, nome e

stipendio dell'impiegato e del capoPROJMatr,Nome,Stip,MatrC,NomeC,StipC

(SELStipendio>StipC(RENMatrC,NomeC,StipC,EtàC ← Matr,Nome,Stip,Età(Impiegati)

JOIN MatrC=Capo

(Supervisione JOIN Impiegato=Matricola Impiegati)))


59987309

56989553

4076

56985698

40764076

8123


Bianchi 37 385998Rossi 34 457309

Bruni 43 425698Neri 42 359553

Mori 45 504076Lupi 46 608123 82


• Trovare le matricole dei capi i cui impiegati

guadagnano tutti più di 40

PROJCapo (Supervisione) -

PROJCapo (Supervisione

JOIN Impiegato=Matricola

(SELStipendio ≤ 40(Impiegati)))


59987309

56989553

4076

56985698

40764076

8123


Bianchi 37 385998Rossi 34 457309

Bruni 43 425698Neri 42 359553

Mori 45 504076Lupi 46 608123

83


Una convenzione e notazione alternativa per i join

• Nota: è sostanzialmente l'approccio usato in SQL

• Ignoriamo il join naturale (cioè non consideriamo implicitamente condizioni su attributi con nomi uguali)

• Per "riconoscere" attributi con lo stesso nome gli premettiamo il nome della relazione

• Usiamo "assegnazioni" (viste) per ridenominarele relazioni (e gli attributi solo quando serve per l'unione)

84


• Trovare gli impiegati che guadagnano più del proprio capo, mostrando matricola, nome e stipendio dell'impiegato e del capo

PROJMatr,Nome,Stip,MatrC,NomeC,StipC

(SELStipendio>StipC(RENMatrC,NomeC,StipC,EtàC ← Matr,Nome,Stip,Età(Impiegati)

JOIN MatrC=Capo

(Supervisione JOIN Impiegato=Matricola Impiegati)))


59987309

56989553

4076

56985698

40764076

8123


Bianchi 37 385998Rossi 34 457309

Bruni 43 425698Neri 42 359553

Mori 45 504076Lupi 46 608123

22

85


PROJMatr,Nome,Stip,MatrC,NomeC,StipC

(SELStip>StipC(RENMatrC,NomeC,StipC,EtàC ← Matr,Nome,Stip,Età(Imp)

JOIN MatrC=Capo

(Sup JOIN Imp=Matr Imp)))

PROJImp.Matr, Imp.Nome, Imp.Stip,Capi.Matr,Capi.Nome, Capi.Stip

(SELImp.Stip>Capi.Stip(

Capi JOIN Capi.Matr=Capo (Sup JOIN Imp=Imp.Matr Imp)))

Capi := Imp

86


Equivalenza di espressioni

• Due espressioni sono equivalenti se

producono lo stesso risultato qualunque sia

l'istanza attuale della base di dati

• L'equivalenza è importante in pratica

perché i DBMS cercano di eseguire

espressioni equivalenti a quelle date, ma

meno "costose“ (QUERY OPTIMIZER)

87


Un'equivalenza importante

• Push selections (se A è attributo di R2 )

SEL A=10 (R1 JOIN R2) = R1 JOIN SEL A=10 ( R2)

• Riduce in modo significativo la dimensione

del risultato intermedio (e quindi il costo

dell'operazione)

88


Nota

• In questo corso, ci preoccupiamo poco

dell’efficienza:

• l’obiettivo è di scrivere interrogazioni

corrette e leggibili

• Motivazione:

• I DBMS si preoccupano di scegliere le

strategie realizzative efficienti

23

89


Selezione con valori nulli

Cognome Filiale EtàMatricola

Neri Milano 455998

Rossi Roma 327309

Bruni Milano NULL9553

Impiegati

SEL Età > 40 (Impiegati)

• la condizione atomica è vera solo per valori non nulli

90


Un risultato non desiderabile

SEL Età>30 (Persone) ∪ SEL Età≤30 (Persone) ≠Persone

• Perché?

Perché le selezioni vengono valutate separatamente!

• Ma anche

SEL Età>30 ∨ Età≤30 (Persone) ≠ Persone• Perché?

• Perché anche le condizioni atomiche vengono valutate separatamente!

91


Selezione con valori nulli: soluzione

SEL Età > 40 (Impiegati)

• la condizione atomica è vera solo per valori non nulli

• per riferirsi ai valori nulli esistono forme apposite di condizioni:

IS NULL

IS NOT NULL

• si potrebbe usare (ma non serve) una "logica a tre valori" (vero, falso, sconosciuto)

92


• Quindi:

SEL Età>30 (Persone) ∪ SEL Età≤30 (Persone) ∪SEL Età IS NULL (Persone)

=

SEL Età>30 ∨ Età≤30 ∨ Età IS NULL (Persone)

=

Persone

24

93


Cognome Filiale EtàMatricola

Neri Milano 455998


Impiegati

SEL (Età > 40) OR (Età IS NULL) (Impiegati)

Rossi Roma 327309 Rossi Roma 327309 Neri Milano 455998


94


Viste (relazioni derivate)

• Rappresentazioni diverse per gli stessi dati (schema esterno)

• Relazioni derivate:• relazioni il cui contenuto è funzione del contenuto di altre

relazioni (definito per mezzo di interrogazioni)

• Relazioni di base: contenuto autonomo

• Le relazioni derivate possono essere definite su altre derivate, ma …a condizione che esista un ordinamento tra le r derivate

ogni r sia def solo in termini di r di base e r der che la precedono nell’ordinamento

95


Architettura standard (ANSI/SPARC)a tre livelli per DBMS

BD

Schema logico

Schemaesterno

Schema interno

Schemaesterno

Schemaesterno

utenteutente

utenteutente utente

96


Viste, esempio

• una vista:

Supervisione =

PROJ Impiegato, Capo (Afferenza JOIN Direzione)

A Mori

B Bruni

Reparto CapoRossi A

Neri B

Bianchi B

Impiegato RepartoAfferenza Direzione

25

97


Viste virtuali e materializzate

• Due tipi di relazioni derivate:

• viste materializzate

• relazioni virtuali (o viste)

98


Viste materializzate

• relazioni derivate memorizzate nella base di dati

• vantaggi:

• immediatamente disponibili per le interrogazioni

• svantaggi:

• ridondanti

• appesantiscono gli aggiornamenti

• sono raramente supportate dai DBMS

99


Viste virtuali

• relazioni virtuali (o viste):

• sono supportate dai DBMS (tutti)

• una interrogazione su una vista viene

eseguita "ricalcolando" la vista (o quasi)

100


Interrogazioni sulle viste

• Sono eseguite sostituendo alla vista la sua

definizione:

SELCapo='Leoni' (Supervisione)

viene eseguita comeSELCapo='Leoni'(

PROJ Impiegato, Capo (Afferenza JOIN Direzione))

26

101


Viste, motivazioni (vantaggi)

• Schema esterno: ogni utente vede solo • ciò che gli interessa e nel modo in cui gli interessa,

senza essere distratto dal resto• ciò che e' autorizzato a vedere (autorizzazioni)

• Strumento di programmazione:

• si può semplificare la scrittura di interrogazioni: espressioni complesse e sottoespressioni ripetute

• Utilizzo di programmi esistenti su schemi ristrutturati

102


Viste come strumento di programmazione

• Trovare gli impiegati che hanno lo stesso capo diRossi

• Senza vista:PROJ Impiegato ((Afferenza JOIN Direzione) JOIN

REN ImpR,RepR ← Imp,Reparto (SEL Impiegato='Rossi' (Afferenza JOIN Direzione)))

• Con la vista:PROJ Impiegato (Supervisione JOIN

REN ImpR,RepR ← Imp,Reparto (SEL Impiegato='Rossi' (Supervisione)))

103


Viste e aggiornamenti, attenzione

• Vogliamo inserire, nella vista, il fatto che Lupi ha come capo Bruni; oppure che Belli ha come capo Falchi; come facciamo?

Afferenza Direzione

A Mori

B Bruni

Reparto Capo

Rossi A

Neri B

Impiegato Reparto

Neri BNeri B B BruniB BruniB BruniB Bruni

Verdi A B BruniB BruniB BruniB BruniC Bruni

Rossi

Neri

Impiegato

Rossi

Neri

Rossi

Neri

Verdi

SupervisioneMori

Bruni

Capo

Mori

Bruni

Mori

BruniBruniBruni

Mori

104


Viste e aggiornamenti

• "Aggiornare una vista":

• modificare le relazioni di base in modo che la vista, "ricalcolata" rispecchi l'aggiornamento

• L'aggiornamento sulle relazioni di base corrispondente a quello specificato sulla vista deve essere univoco

• In generale però non è univoco!

• Ben pochi aggionamenti sono ammissibili sulle viste

Linguaggi per basi di dati - Università degli Studi di ... · Basi di dati – Paolo Zirilli...

Documents

Transcript of Linguaggi per basi di dati - Università degli Studi di ... · Basi di dati – Paolo Zirilli...