Download - ALGEBRA RELAZIONALE

Transcript
Page 1: ALGEBRA RELAZIONALE

ALGEBRA RELAZIONALEALGEBRA RELAZIONALE

Page 2: ALGEBRA RELAZIONALE

Algebra Relazionale 2

Le basi di dati rappresentano le informazioni di interesse per applicazioni che gestiscono i dati

E’ importante considerare linguaggi per la specifica di operazioni sui dati stessi, che siano legati al modello dei dati scelto (modello relazionale)

Page 3: ALGEBRA RELAZIONALE

Algebra Relazionale 3

Linguaggi per basi di dati

operazioni sullo schema DDL: data definition language per definire lo

schema VDL: view definition language per definire le

viste d’utente operazioni sui dati

DML: data manipulation language interrogazione ("query") inserimento, cancellazione e aggiornamento dei dati

Page 4: ALGEBRA RELAZIONALE

Algebra Relazionale 4

Linguaggi per l’interrogazione

Una base di dati richiede un insieme di operazioni che consentano all’utente di specificare le richieste di recupero fondamentali

Le operazioni di questo tipo producono nuove relazioni, sulle quali è ulteriormente possibile applicare operazioni

Page 5: ALGEBRA RELAZIONALE

Algebra Relazionale 5

Linguaggi di interrogazioneper basi di dati relazionali

Dichiarativi (di alto livello) le espressioni specificano le proprietà del

risultato ("che cosa")

Procedurali (di basso livello) specificano le modalità di generazione del

risultato ("come")

Page 6: ALGEBRA RELAZIONALE

Algebra Relazionale 6

Linguaggi di interrogazione

Algebra relazionale: procedurale (teorico) Calcolo relazionale: dichiarativo (teorico) SQL (Structured Query Language): combina

gli aspetti dichiarativi del calcolo e quelli procedurali dell’algebra (linguaggio reale)

Page 7: ALGEBRA RELAZIONALE

Algebra Relazionale 7

Algebra relazionale

Insieme di operatori, definiti su relazioni, che producono ancora relazioni come risultati insiemistici: unione, intersezione, differenza specifici: ridenominazione, selezione, proiezione join: join naturale, prodotto cartesiano, theta-join raggruppamento: divisione

Page 8: ALGEBRA RELAZIONALE

Algebra Relazionale 8

Operatori insiemistici

le relazioni sono insiemi i risultati debbono essere relazioni

- è sensato applicare le operazioni insiemistiche classiche di unione,intersezione, differenza

- è possibile applicare solo a relazioni definite sugli stessi attributi

Page 9: ALGEBRA RELAZIONALE

Algebra Relazionale 9

Laureati

Matricola

74329824

Età

5445

Nome

NeriVerdi

7274 42Rossi

Quadri

Matricola

74329824

9297Età

5445

33Nome

NeriVerdi

Neri

Laureati Quadri

Matricola EtàNome

7432 54Neri9824 45Verdi9297 33Neri

7274 42Rossi7432 54Neri9824 45Verdi

7274 42Rossi7432 54Neri9824 45Verdi9297 33Neri

7432 54Neri9824 45Verdi9297 33Neri

7274 42Rossi

Unione

Page 10: ALGEBRA RELAZIONALE

Algebra Relazionale 10

Laureati

Matricola

74329824

Età

5445

Nome

NeriVerdi

7274 42Rossi

Quadri

Matricola

74329824

9297Età

5445

33Nome

NeriVerdi

Neri

Laureati Quadri

Matricola EtàNome7432 54Neri9824 45Verdi

7432 54Neri9824 45Verdi

7432 54Neri9824 45Verdi

7432 54Neri9824 45Verdi

Intersezione

Page 11: ALGEBRA RELAZIONALE

Algebra Relazionale 11

Laureati

Matricola EtàNome

7432 54Neri9824 45Verdi

7274 42Rossi

Quadri

Matricola

74329824

9297Età

5445

33Nome

NeriVerdi

Neri

Laureati – QuadriMatricola EtàNome

7432 54Neri9824 45Verdi

7274 42Rossi7432 54Neri9824 45Verdi

7274 42Rossi

Differenza

Page 12: ALGEBRA RELAZIONALE

Algebra Relazionale 12

Paternità

Padre Figlio

Adamo CainoAbramo Isacco

Adamo Abele

Maternità

Madre Figlio

Eva SetSara Isacco

Eva Abele

Paternità Maternità

??

Una unione sensata ma impossibile

Page 13: ALGEBRA RELAZIONALE

Algebra Relazionale 13

Ridenominazione

operatore unario "modifica lo schema" lasciando inalterata

l'istanza dell'operando, cambia solo il nome degli attributi

Page 14: ALGEBRA RELAZIONALE

Algebra Relazionale 14

Ridenominazione: definizione formale

Siano R una relazione su X, e Y un altro insieme di attributi con la stessa cardinalità

X = {A1,……. Ak}

Y = {B1,……. Bk}La ridenominazione

A1,……. Ak B1,……. Bk (R)contiene una ennupla t’ per ogni ennupla t in R tale che:

t’ è una ennupla su Y t’[Bi]=t[Ai], per ogni i=1,…,k

Page 15: ALGEBRA RELAZIONALE

Algebra Relazionale 15

Paternità

Padre Figlio

Adamo CainoAbramo Isacco

Adamo Abele

Genitore Padre (Paternità)

Padre Figlio

Adamo CainoAbramo Isacco

Adamo AbeleGenitore

Page 16: ALGEBRA RELAZIONALE

Algebra Relazionale 16

Paternità

Padre Figlio

Adamo CainoAbramo Isacco

Adamo Abele

Maternità

Madre Figlio

Eva SetSara Isacco

Eva Abele

Genitore Padre (Paternità)

Genitore Madre (Maternità)

Genitore Figlio

Adamo CainoAbramo Isacco

Adamo Abele

Genitore Figlio

Eva SetSara Isacco

Eva Abele

Page 17: ALGEBRA RELAZIONALE

Algebra Relazionale 17

Genitore Padre (Paternità)

Genitore Madre (Maternità)

Genitore Figlio

Adamo CainoAbramo Isacco

Adamo Abele

Genitore Figlio

Eva SetSara Isacco

Eva Abele

Genitore Figlio

Adamo CainoAbramo Isacco

Adamo Abele

Eva SetSara Isacco

Eva Abele

Genitore Padre (Paternità)

Genitore Madre (Maternità)

Page 18: ALGEBRA RELAZIONALE

Sede, Retribuzione Ufficio, Stipendio (Impiegati)

Sede, Retribuzione Fabbrica, Salario (Operai)

Impiegati Cognome

NeriRossi

Ufficio

MilanoRoma

Stipendio

6455

Operai Cognome

VerdiBruni

Fabbrica

LatinaMonza

Salario

5545

Cognome RetribuzioneSede

NeriRossi

6455

MilanoRoma

VerdiBruni

LatinaMonza

5545

Page 19: ALGEBRA RELAZIONALE

Algebra Relazionale 19

Selezione

operatore unario su una tabella produce un risultato che

ha lo stesso schema della relazione di partenza (colonne della tabella)

contiene un sottoinsieme delle ennuple dell'operando (righe della tabella),

quelle che soddisfano una condizione

Page 20: ALGEBRA RELAZIONALE

Algebra Relazionale 20

Selezione

A B C A B C

Page 21: ALGEBRA RELAZIONALE

Algebra Relazionale 21

Impiegati Cognome Filiale StipendioMatricola

Neri Milano 645998Rossi Roma 557309

Neri Napoli 645698Milano 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

Page 22: ALGEBRA RELAZIONALE

Algebra Relazionale 22

Selezione, sintassi e semantica

sintassi

Condizione (Operando) Condizione: espressione booleana Operando: una espressione dell’algebra relazionale

semantica il risultato è una relazione sugli stessi attributi che

contiene le ennuple dell'operando che soddisfano la condizione

Page 23: ALGEBRA RELAZIONALE

Algebra Relazionale 23

Condizione di selezione

F formula proposizionale formata da• operatori booleani: (AND), (OR), ¬ (NOT)• condizioni atomiche: termini che possono contenere

confronti fra attributi, o fra attributi e costanti. Hannoforma: AB oppure Ac dove

– operatore di confronto (=, , >, <, , )– A, B attributi in X– c costante compatibile con dominio di

attributo (A) con cui c viene confrontata

Page 24: ALGEBRA RELAZIONALE

Algebra Relazionale 24

Condizioni di selezione, esempi

Esempi: (Stipendio > 50)

Filiale='Milano'

Cognome = Filiale

(Stipendio > 50) AND (Filiale='Milano')

NOT (Cognome='Neri')

Page 25: ALGEBRA RELAZIONALE

Algebra Relazionale 25

Cognome Filiale StipendioMatricola

Neri Milano 645998Rossi Roma 557309

Neri Napoli 645698Milano Milano 449553

Impiegati

Milano Milano 449553 Neri Napoli 645698

impiegati che guadagnano più di 50

Stipendio > 50 (Impiegati)

Page 26: ALGEBRA RELAZIONALE

Algebra Relazionale 26

Impiegati Cognome Filiale StipendioMatricola

Neri Milano 645998Rossi Roma 557309

Neri Napoli 645698Milano Milano 449553

impiegati che guadagnano più di 50 e lavorano a Milano

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

Rossi Roma 557309

Neri Napoli 645698Milano Milano 449553

Neri Milano 645998

Page 27: ALGEBRA RELAZIONALE

Algebra Relazionale 27

Impiegati Cognome Filiale StipendioMatricola

Neri Milano 645998Rossi Roma 557309

Neri Napoli 645698Milano Milano 449553

impiegati che hanno lo stesso nome della filiale presso cui lavorano

Cognome = Filiale(Impiegati)

Neri Milano 645998Rossi Roma 557309

Neri Napoli 645698

Milano Milano 449553

Page 28: ALGEBRA RELAZIONALE

Algebra Relazionale 28

Osservazioni

l’operazione di selezione è commutativa

<Cond1> ( <Cond2> (R)) =

<Cond2> ( <Cond1> (R)) =

<Cond1> AND <Cond2> (R) il numero delle t-uple della relazione R dopo

l’applicazione di una selezione è minore o uguale al numero delle t-uple di R

| <Cond> (R) | | R |

Page 29: ALGEBRA RELAZIONALE

Algebra Relazionale 29

Selezione con valori nulli

Cognome Filiale EtàMatricola

Neri Milano 455998

Rossi Roma 327309Bruni Milano NULL9553

Impiegati

Età > 40 (Impiegati)

• la condizione atomica è vera solo per valori non nulli

Page 30: ALGEBRA RELAZIONALE

Algebra Relazionale 30

Un risultato non desiderabile

Età>30 (Persone) Età30 (Persone) Persone Perché? Perché le selezioni vengono valutate

separatamente! Ma anche

Età>30 Età30 (Persone) Persone Perché? Perché anche le condizioni atomiche

vengono valutate separatamente!

Page 31: ALGEBRA RELAZIONALE

Algebra Relazionale 31

Età > 40 (Impiegati)

la condizione atomica è vera solo per valori non nulli

per riferirsi ai valori nulli esiste la apposita di condizione:

IS NULL

Page 32: ALGEBRA RELAZIONALE

Algebra Relazionale 32

A questo punto:

Età>30 (Persone) Età30 (Persone) Età IS NULL

(Persone) =

Età>30 Età30 (Età IS NULL) (Persone) =

Persone

Page 33: ALGEBRA RELAZIONALE

Algebra Relazionale 33

Logica con il valore NULL

Oltre ai valori di verità Vero (V) e Falso (F), si introduce NULL (?)

NOT ( A IS NULL) si scrive anche A IS NOT NULL

Page 34: ALGEBRA RELAZIONALE
Page 35: ALGEBRA RELAZIONALE

Algebra Relazionale 35

Cognome Filiale EtàMatricola

Neri Milano 455998Rossi Roma 327309

Bruni Milano NULL9553

Impiegati

Neri Milano 455998Bruni Milano NULL9553

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

Neri Milano 455998Bruni Milano NULL9553

Page 36: ALGEBRA RELAZIONALE

Algebra Relazionale 36

Selezione e proiezione

operatori "ortogonali" selezione:

decomposizione orizzontale

proiezione: decomposizione verticale

Page 37: ALGEBRA RELAZIONALE

selezione

proiezione

Page 38: ALGEBRA RELAZIONALE

Algebra Relazionale 38

Proiezione

operatore unario su una tabella produce un risultato che

ha parte degli attributi della tabella contiene ennuple (righe) cui contribuiscono tutte

le ennuple della tabella iniziale

Page 39: ALGEBRA RELAZIONALE

Algebra Relazionale 39

Impiegati Cognome Filiale StipendioMatricola

Neri Milano 645998Neri Napoli 557309

Rossi Roma 645698Rossi Roma 449553

per tutti gli impiegati:matricola e cognomecognome e filiale

Page 40: ALGEBRA RELAZIONALE

Algebra Relazionale 40

Proiezione, sintassi e semantica

sintassi

<ListaAttributi> (Operando)

<ListaAttributi> è un elenco di attributi di Operando

Operando è una espressione nell’algebra relazionale

semantica il risultato contiene le ennuple ottenute da tutte le

ennuple dell'operando ristrette agli attributi nella lista

Page 41: ALGEBRA RELAZIONALE

Algebra Relazionale 41

Cognome Filiale StipendioMatricola

Neri Milano 645998Neri Napoli 557309

Rossi Roma 645698Rossi Roma 449553

matricola e cognome di tutti gli impiegati

Matricola, Cognome (Impiegati)

Page 42: ALGEBRA RELAZIONALE

Algebra Relazionale 42

Cognome Filiale StipendioMatricola

Neri Milano 645998Neri Napoli 557309

Rossi Roma 645698Rossi Roma 449553

cognome e filiale di tutti gli impiegati

Cognome, Filiale (Impiegati)

Page 43: ALGEBRA RELAZIONALE

Algebra Relazionale 43

Cardinalità delle proiezioni

una proiezione contiene al più tante ennuple quante l'operando può contenerne di meno

se X è una superchiave di R, allora X(R) contiene esattamente tante ennuple quante R

Page 44: ALGEBRA RELAZIONALE

Algebra Relazionale 44

Selezione e proiezione

Combinando selezione e proiezione, possiamo estrarre interessanti informazioni da una relazione

Cond ( A,B,C (R) ) = ( A,B,C Cond (R) ) ?

Sono commutative a certe condizioni !

Page 45: ALGEBRA RELAZIONALE

Algebra Relazionale 45

Cognome Filiale StipendioMatricola

Neri Milano 645998Rossi Roma 557309

Neri Napoli 645698Milano Milano 449553 Milano Milano 449553 Neri Napoli 645698

matricola e cognome degli impiegati che guadagnano più di 50

Stipendio > 50 (Impiegati) Matricola,Cognome ( )

Page 46: ALGEBRA RELAZIONALE

Algebra Relazionale 46

combinando selezione e proiezione, possiamo estrarre informazioni da una relazione

non possiamo però correlare informazioni presenti in relazioni diverse

Page 47: ALGEBRA RELAZIONALE

Algebra Relazionale 47

Join

il join è l'operatore più interessante dell'algebra relazionale

permette di correlare dati in relazioni diverse sfrutta la caratteristica fondamentale del

modello relazionale, che è quella di essere basato su valori

Page 48: ALGEBRA RELAZIONALE

Idea del join naturalematricola cognome data_nasc

2021 Rossi 1-3-1975

2424 Bianchi 23-3-1974

3445 Neri 2-2-1975

matricola corso voto

2021 Basi dati 28

2021 Calcolo 25

3445 Algebra 30

matricola cognome data_nasc corso voto

2021 Rossi 1-3-1975 Basi dati 28

2021 Rossi 1-3-1975 Calcolo 25

3545 Neri 2-2-1975 Algebra 30

2021 Rossi 1-3-1975 Basi dati 28

2021 Rossi 1-3-1975 2021 Basi dati 28

2021 Rossi 1-3-1975 Calcolo 25

2021 Rossi 1-3-1975

2021 Calcolo 25

3445 Neri 2-2-1975 3445 Algebra 30

3445 Neri 2-2-1975 Algebra 30

Page 49: ALGEBRA RELAZIONALE

Algebra Relazionale 49

Join naturale

operatore binario (generalizzabile a più relazioni)

produce un risultato sull'unione degli attributi degli operandi

(schema) con ennuple costruite ciascuna a partire da una

ennupla di ognuno degli operandi (istanza)

Page 50: ALGEBRA RELAZIONALE

Algebra Relazionale 50

Join, sintassi e semantica

R1(X1), R2(X2)

R1 R2 è una relazione su X1X2

{ t su X1 X2 : esistono t1R1e t2R2

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

Page 51: ALGEBRA RELAZIONALE

Algebra Relazionale 51

Join, proprietà

Il join naturale è commutativo:

R1 R2 = R2 R1

Il join naturale è associativo:

( R1 R2 ) R3 = R1 ( R2 R3 )

Page 52: ALGEBRA RELAZIONALE

Matricola Cognome Nome6554 Rossi Mario8765 Neri Paolo

3456 Rossi Maria9283 Verdi Luisa

studenti

Corso Titolo Docente01 Analisi Mario02 Chimica Bruni04 Chimica Verdi

corsi

Matricola Voto Corso3456 30 043456 24 029283 28 01

esami

6554 26 01

(studenti esami) ((studenti esami) corsi )

Page 53: ALGEBRA RELAZIONALE

A MoriB Bruni

Reparto CapoRossi ANeri B

Bianchi B

Impiegato Reparto

Rossi A MoriNeri B Bruni

Impiegato Reparto Capo

Bianchi B Bruni

Rossi ANeri B

Bianchi B

Rossi ANeri B

Bianchi B

A MoriB BruniA MoriB BruniB BruniB Bruni

ogni ennupla contribuisce al risultato:join completo

Page 54: ALGEBRA RELAZIONALE

Algebra Relazionale 54

Neri B MoriImpiegato Reparto Capo

Bianchi B Mori

Impiegato RepartoRossi ANeri B

Bianchi B

Reparto CapoB MoriC Bruni

AC

Un join non completo

Page 55: ALGEBRA RELAZIONALE

Algebra Relazionale 55

Impiegato RepartoRossi ANeri B

Bianchi B

Reparto CapoD MoriC Bruni

Impiegato Reparto Capo

Un join vuoto

Page 56: ALGEBRA RELAZIONALE

Algebra Relazionale 56

Rossi B Mori

Neri B Mori

Impiegato Reparto Capo

Bianchi B Bruni

Rossi ANeri B

Impiegato RepartoRossi ANeri B

Rossi BNeri B

A MoriB Bruni

Reparto CapoA MoriB BruniB MoriB BruniB BruniB Bruni

Rossi B Bruni

Un join completo, con n x m ennuple

Ogni n-upla di ciascuna tabella è combinabile con tutte le n-uple dell’altro

Page 57: ALGEBRA RELAZIONALE

Algebra Relazionale 57

Cardinalità del join

Il join di R1(A) e R2(B) contiene un numero di ennuple compreso fra zero e il prodotto di |R1| e |R2|

Page 58: ALGEBRA RELAZIONALE

Algebra Relazionale 58

Impiegato RepartoRossi ANeri B

Bianchi B

Rossi A MoriImpiegato Reparto Capo

Neri B Bruni

Impiegato CapoRossi MoriNeri BruniNeri Bianchi

se il join coinvolge una chiave di R1 allora il numero di ennuple è compreso tra zero e |R2|

Neri B Bianchi

Verdi Bianchi

Page 59: ALGEBRA RELAZIONALE

Algebra Relazionale 59

Impiegato RepartoRossi ANeri B

Bianchi B

Rossi A MoriImpiegato Reparto Capo

Neri B Bruni

Impiegato CapoRossi MoriNeri BruniNeri Bianchi

se il join coinvolge una chiave di R1 e c’è un vincolo di integrità allora il numero di ennuple è compreso uguale a |R2|

Neri B Bianchi

Page 60: ALGEBRA RELAZIONALE

Algebra Relazionale 60

Cardinalità del join, riepilogo

R1(A,B) , R2 (B,C) in generale:

0 |R1 R2| |R1| · |R2| se B è chiave in R1

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

integrità referenziale fra B (in R2) e R1

|R1 R2| = |R2|

Page 61: ALGEBRA RELAZIONALE

Algebra Relazionale 61

Join naturale e valori nulli

Page 62: ALGEBRA RELAZIONALE

Algebra Relazionale 62

Impiegato RepartoRossi ANeri B

Bianchi B

Reparto CapoB MoriC Bruni

Neri B MoriImpiegato Reparto Capo

Bianchi B Mori

AC

Join, una difficoltà

alcune ennuple non contribuiscono al risultato: vengono "tagliate fuori'': si possono omettere informazioni importanti

Page 63: ALGEBRA RELAZIONALE

Algebra Relazionale 63

Join esterno

Il join esterno estende, con valori nulli, le ennuple che verrebbero tagliate fuori da un join (naturale)

esiste in tre versioni: sinistro, destro, completo

Page 64: ALGEBRA RELAZIONALE

Algebra Relazionale 64

Join esterno

sinistro: prevede che tutte le ennuple del primo operando, estendendole con valori nulli, se necessario, diano un contributo al join

destro: ... del secondo operando ... completo: … di entrambi gli operandi … OSSERVAZIONE: il Join esterno non è commutativo

Page 65: ALGEBRA RELAZIONALE

Impiegato RepartoRossi ANeri B

Bianchi B

ImpiegatiReparto Capo

B MoriC Bruni

Reparti

Neri B MoriImpiegato Reparto Capo

Bianchi B Mori

Impiegati LEFT Reparti

C

Rossi A NULL

ARossi

Page 66: ALGEBRA RELAZIONALE

Impiegato RepartoRossi ANeri B

Bianchi B

ImpiegatiReparto Capo

B MoriC Bruni

Reparti

Neri B MoriImpiegato Reparto Capo

Bianchi B Mori

Impiegati RIGHT Reparti

A

NULL C Bruni

C Bruni

Page 67: ALGEBRA RELAZIONALE

Impiegato RepartoRossi ANeri B

Bianchi B

ImpiegatiReparto Capo

B MoriC Bruni

Reparti

Neri B MoriImpiegato Reparto Capo

Bianchi B Mori

Impiegati FULL Reparti

NULL C Bruni

C BruniARossi

Rossi A NULL

Page 68: ALGEBRA RELAZIONALE

Matr Cognome Nome Data di nascita6554 Rossi Mario 05/12/19784678 Neri Paolo 03/11/1976

3456 Rossi Maria 01/02/19789283 Verdi Luisa 12/11/1979

studenti

Codice Titolo Docente01 Analisi Mari02 Chimica Mari04 Chimica Verdi

corsiCorso

04

esami

Matr Voto Codice

3456 30 04

3456 24 02

9283 30 01

6554 26 01

esami

Esercizio 1

Determinare i corsi tenuti dal Prof. Mari

Titolo ( Docente=‘Mari’(corsi) )

Page 69: ALGEBRA RELAZIONALE

Matr Cognome Nome Data di nascita6554 Rossi Mario 05/12/19784678 Neri Paolo 03/11/1976

3456 Rossi Maria 01/02/19789283 Verdi Luisa 12/11/1979

studenti

Codice Titolo Docente01 Analisi Mari02 Chimica Mari04 Chimica Verdi

corsiCorso

04

esami

Matr Voto Codice

3456 30 04

3456 24 02

9283 30 01

6554 26 01

esami

Esercizio 2

Determinare nome, cognome e numero di matricola degli studenti che hanno ricevuto la votazione di 30

Nome, Cognome, Matr ( Voto=30( esami studenti ))

Page 70: ALGEBRA RELAZIONALE

Matr Cognome Nome Data di nascita6554 Rossi Mario 05/12/19784678 Neri Paolo 03/11/1976

3456 Rossi Maria 01/02/19789283 Verdi Luisa 12/11/1979

studenti

Codice Titolo Docente01 Analisi Mari02 Chimica Mari04 Chimica Verdi

corsi

Corso

04

esami

Matr Voto Codice

3456 30 04

3456 24 02

9283 30 01

6554 26 01

esami

Esercizio 3

Determinare il nome e il cognome degli studenti che hanno sostenuto l'esame di Analisi

Page 71: ALGEBRA RELAZIONALE

Algebra Relazionale 71

Matr Cognome Nome Data di nascita6554 Rossi Mario 05/12/19784678 Neri Paolo 03/11/1982

3456 Rossi Maria 01/02/19839283 Verdi Luisa 12/11/1979

studenti

Codice Titolo Docente01 Analisi Mari02 Chimica Mari04 Chimica Verdi

corsi

Corso

04

esami

Matr Voto Codice

3456 30 04

3456 24 01

9283 30 01

6554 26 01

esami

Esercizio 4

Determinare nome, cognome ed eventuali esami sostenuti da tutti gli studenti del corso di laurea che hanno più di 25 anni.

Page 72: ALGEBRA RELAZIONALE

Algebra Relazionale 72

Matr Cognome Nome Data di nascita6554 Rossi Mario 05/12/19784678 Neri Paolo 03/11/1982

3456 Rossi Maria 01/02/19839283 Verdi Luisa 12/11/1979

studenti

Codice Titolo Docente01 Analisi Mari02 Chimica Mari04 Chimica Verdi

corsi

Corso

04

esami

Matr Voto Codice

3456 30 04

3456 24 01

9283 30 01

6554 26 01

esami

Esercizio 5

Determinare nome, cognome degli studenti del corso di laurea che non hanno sostenuto alcun esame.

Page 73: ALGEBRA RELAZIONALE

Join e proiezioniImpiegato Reparto

Rossi ANeri B

Bianchi B

Reparto CapoB MoriC Bruni

Neri B MoriImpiegato Reparto Capo

Bianchi B Mori

Impiegato RepartoNeri B

Bianchi B

Reparto CapoB Mori

Page 74: ALGEBRA RELAZIONALE

Proiezioni e join

Neri B MoriImpiegato Reparto Capo

Bianchi B BruniVerdi A Bini

Neri BImpiegato Reparto

Bianchi BVerdi A

B MoriReparto Capo

B BruniA Bini

Verdi A Bini

Neri B MoriImpiegato Reparto Capo

Bianchi B BruniNeri B Bruni

Bianchi B Mori

Page 75: ALGEBRA RELAZIONALE

Algebra Relazionale 75

Join e proiezioni

R 1(X1), R 2(X2)

X1 (R 1 R2 ) R 1

R(X), X = X1 X2

( X1 (R)) ( X2

(R)) R

Page 76: ALGEBRA RELAZIONALE

Algebra Relazionale 76

Prodotto cartesiano

Che cosa accade se si effettua un join naturale su relazioni senza attributi in comune?

Prodotto cartesiano tra le due relazioni contiene sempre un numero di ennuple pari al

prodotto delle cardinalità degli operandi (le ennuple sono tutte combinabili )

Page 77: ALGEBRA RELAZIONALE

Rossi ANeri B

Bianchi B

Impiegato Reparto

Impiegati

A MoriB BruniB BruniB Bruni

Codice Capo

Reparti

Impiegati Reparti Impiegato Reparto CapoCodice

Rossi A MoriAAARossi A B BruniNeri B MoriANeri B B Bruni

Bianchi B MoriABianchi B B Bruni

Page 78: ALGEBRA RELAZIONALE

Algebra Relazionale 78

Il prodotto cartesiano, in pratica, ha senso solo se seguito da selezione:

Condizione (R1 R2)

L'operazione viene chiamata theta-join e indicata con:

R1 Cond R2

Page 79: ALGEBRA RELAZIONALE

Algebra Relazionale 79

Perché "theta-join"?

La condizione C è spesso una congiunzione (AND) di atomi di confronto A1 A2 dove è uno degli operatori di confronto (=, >, <, …)

se l'operatore è sempre l'uguaglianza (=) allora si parla di equi-join

Page 80: ALGEBRA RELAZIONALE

Rossi ANeri B

Bianchi B

Impiegato Reparto

Impiegati

A MoriB BruniB BruniB Bruni

Codice Capo

Reparti

Impiegati Reparto=Codice Reparti Impiegato Reparto CapoCodice

Rossi A MoriAAARossi A B BruniNeri B MoriANeri B B Bruni

Bianchi B MoriABianchi B B Bruni

Rossi A MoriAAANeri B B Bruni

Bianchi B B Bruni

Equi-join

Page 81: ALGEBRA RELAZIONALE

Algebra Relazionale 81

Rossi ANeri B

Bianchi B

Impiegato Reparto

Impiegati

A MoriB BruniB BruniB Bruni

Reparto Capo

Reparti

Impiegati Reparti

Page 82: ALGEBRA RELAZIONALE

Algebra Relazionale 82

Join naturale ed equi-join

Impiegato Reparto

Impiegati

Reparto Capo

Reparti

Impiegati Reparti

Impiegato,Reparto,Capo (

) Codice Reparto (Reparti)Impiegati Reparto=Codice

( ) )

Producono lo stesso risultato !

Page 83: ALGEBRA RELAZIONALE

Algebra Relazionale 83

prodotto cartesiano o join naturale?

Prodotto cartesiano e Join naturale possono essere ottenuti l’uno a partire dall’altro

R(A,B), S(B,C) Prodotto cartesiano :

R S = A,B,C (R.B=S.B (R S) ) Join naturale :

R S = ( BB’ (R) S)

Page 84: ALGEBRA RELAZIONALE

Operatore di divisione

trovare gli studenti che hanno sostenuto tutti gli esami del corso di laurea Algebra Relazionale 84

Matr Cognome Nome Data di nascita6554 Rossi Mario 05/12/19784678 Neri Paolo 03/11/1982

3456 Rossi Maria 01/02/19839283 Verdi Luisa 12/11/1979

studenti

Codice Titolo Docente01 Analisi Mari02 Chimica Mari04 Fisica Verdi

corsi

Corso

04

esami

Matr Voto Codice

3456 30 04

3456 24 01

9283 30 01

6554 26 01

esami

6554

65542830

0204

Page 85: ALGEBRA RELAZIONALE

Algebra Relazionale 85

Corso

04

esami

Matr Codice

3456 04

3456 01

9283 01

6554 01

Matr,Codice(esami)

6554

65540204

Codice010204

Codice(corsi)

Matr,Codice(esami) Codice(corsi)

Matr

6554

R(XY) / S(X) è una relazione su T(Y) tale che tT(Y) se e solo seesistono n-uple tR in R tali che:-tR [Y]=t-tR [X]=l per ogni n-unpla l di S

Si considerano solo le righe della prima tabella che si combinano con tutte le righe della seconda tabella

Page 86: ALGEBRA RELAZIONALE

Algebra Relazionale 86

Un insieme completo di operazioni

Teorema: L’insieme delle operazioni

{ , , , , - }

è un insieme completo. ESEMPIO

R S=(R S) - (( R-S) ( S- R )) Join naturale = Prod. Cartesiano + Selezione +

Proiezione Divisione= Prodotto Cartesiano + Differenza + Proiezione

Page 87: ALGEBRA RELAZIONALE

Algebra Relazionale 87

Alcune operazioni in algebra relazionale

Esempio: qual è la squadra prima in classifica?

Classifica

Squadra Punti

Inter 36Juve 34

Siena 40

Page 88: ALGEBRA RELAZIONALE

Algebra Relazionale 88

Ridenominazione + Join

Squadra1

Punti1 Squadra2 Punti2

Siena 40 Siena 40

Inter 36 Siena 40

Siena 40 Juve 34

Inter 36 Juve 34

…. … …. …

Page 89: ALGEBRA RELAZIONALE

Algebra Relazionale 89

Squadra1 Punti1 Squadra2 Punti2

Juve 34 Siena 40

Inter 36 Siena 40

Juve 34 Inter 36

Selezione sulla condizione:

(Punti1 Punti2) AND (Squadra1 Squadra2)

Proiezione su

Squadra1, Punti1

Squadra1 Punti1

Juve 34

Inter 36

Classifica 2Squadre che hanno meno punti di almeno un’altra squadra

Squadre che hanno più punti di almeno un’altra squadra

Page 90: ALGEBRA RELAZIONALE

Algebra Relazionale 90

Differenza tra la tabella Classifica e Classifica 2

(dopo opportuna ridenominazione)

Squadra Punti

Siena 40

Classifica

Squadra Punti

Inter 36Juve 34

Siena 40Squadra1 Punti1

Juve 34

Inter 36

Classifica 2

Page 91: ALGEBRA RELAZIONALE

Algebra Relazionale 91

Chiusura transitiva

Supervisione(Impiegato, Capo)

Per ogni impiegato, trovare tutti i superiori (cioè il capo, il capo del capo, e cosi' via)

RossiNeri

ImpiegatoRossiNeri

RossiNeriLupi

MoriBruni

CapoMoriBruniLupiBruniBruniBruniFalchi

RossiNeri

ImpiegatoRossiNeri

RossiNeriLupi

MoriBruni

SuperioreMoriBruniLupiBruniBruniBruniFalchi

Rossi Falchi

Lupi

Lupi

Page 92: ALGEBRA RELAZIONALE

Algebra Relazionale 92

Chiusura transitiva, come si fa?

Nell'esempio, basterebbe il join della relazione con se stessa, previa opportuna ridenominazione

Ma:

RossiNeri

ImpiegatoRossiNeri

RossiNeriLupi

MoriBruni

SuperioreMoriBruniLupiBruniBruniBruniFalchi

Rossi Falchi

RossiNeri

ImpiegatoRossiNeri

RossiNeriLupi

MoriBruni

CapoMoriBruniLupiBruniBruniBruniLupi

LupiLeoniFalchi

Falchi Lupi LeoniRossi Leoni

FalchiFalchi

Page 93: ALGEBRA RELAZIONALE

Algebra Relazionale 93

Chiusura transitiva, impossibile!

Per ogni specifico livello è possibile determinare tutti gli impiegati sorvegliati da un impegato a un certo livello, ma non quelli sorvegliati a tutti i livelli

Non esiste in algebra la possibilità di esprimere l'interrogazione che, per ogni relazione binaria, ne calcoli la chiusura transitiva

Per ciascuna istanza relazione, è possibile calcolare la chiusura transitiva, ma con un'espressione ogni volta diversa: dipende dall’istanza e non dallo schema!

Immaginate una istanza di migliaia di tuple: quanti join servono?

Page 94: ALGEBRA RELAZIONALE

Algebra Relazionale 94

Interrogazioni in algebra relazionale

Una interrogazione su una base di dati è una funzione che restituisce una relazione R su un insieme di attributi X.

Page 95: ALGEBRA RELAZIONALE

Esempi

Impiegati Nome Età StipendioMatricola

Bianchi 37 385998Rossi 34 457309

Bruni 43 425698Neri 42 359553

Mori 45 504076Lupi 46 608123

Supervisione Impiegato Capo

59987309

56989553

4076

56985698

40764076

8123

Page 96: ALGEBRA RELAZIONALE

Algebra Relazionale 96

Trovare matricola, nome, età e stipendio degli impiegati che guadagnano più di 40 milioni

Stipendio>40 (Impiegati)

Page 97: ALGEBRA RELAZIONALE

Algebra Relazionale 97

Nome Età StipendioMatricola

Bianchi 37 385998Rossi 34 457309

Bruni 43 425698Neri 42 359553

Mori 45 504076Lupi 46 608123

Stipendio>40(Impiegati)

Bianchi 37 385998Neri 42 359553

Rossi 34 457309

Bruni 43 425698Mori 45 504076Lupi 46 608123

Rossi 34 457309Bruni 43 425698Mori 45 504076Lupi 46 608123

Page 98: ALGEBRA RELAZIONALE

Algebra Relazionale 98

Trovare matricola, nome ed età degli impiegati che guadagnano più di 40 milioni

Matricola, Nome, Età (Stipendio>40(Impiegati))

Nome Età StipendioMatricola

Bianchi 37 385998Rossi 34 457309

Bruni 43 425698Neri 42 359553

Mori 45 504076Lupi 46 608123

Bianchi 37 385998Neri 42 359553

Rossi 34 457309

Bruni 43 425698Mori 45 504076Lupi 46 608123

Rossi 34 457309Bruni 43 425698Mori 45 504076Lupi 46 608123

Page 99: ALGEBRA RELAZIONALE

Algebra Relazionale 99

Trovare le matricole dei capi degli impiegati che guadagnano più di 40 milioni

Capo (Supervisione Impiegato=Matricola ( Stipendio>40(Impiegati)))

Page 100: ALGEBRA RELAZIONALE

Algebra Relazionale 100

Trovare nome e stipendio dei capi degli impiegati che guadagnano più di 40 milioni

Nome,Stipendio

(Impiegati Matricola=Capo Capo(Supervisione Impiegato=Matricola ( Stipendio>40(Impiegati))))

Page 101: ALGEBRA RELAZIONALE

Capo

5698

4076

8123

Capo (Supervisione Impiegato=Matricola(Stipendio>40(Impiegati)))

Bianchi 37 385998Rossi 34 457309

Bruni 43 425698Neri 42 359553

Mori 45 504076Lupi 46 608123

Nome Età StipendioMatricola

Impiegati

Page 102: ALGEBRA RELAZIONALE

Algebra Relazionale 102

Impiegati Matricola=Capo Capo(Supervisione

Impiegato=Matricola ( Stipendio>40(Impiegati))))

Capo Matricola Nome Età Stipendio

5698 5698 Bianchi 37 38

4076 4076 Mori 45 50

8123 8123 Lupi 46 60

Page 103: ALGEBRA RELAZIONALE

Algebra Relazionale 103

Nome,Stipendio (Impiegati Matricola=Capo

Capo(Supervisione Impiegato=Matricola

(Stipendio>40(Impiegati))))

Nome Stipendio

Bianchi 38

Mori 50

Lupi 60

Nome e stipendio dei capi di impiegati che guadagnano più di 40 milioni

Page 104: ALGEBRA RELAZIONALE

Algebra Relazionale 104

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

Matr,Nome,Stip,MatrC,NomeC,StipC ( Stipendio>StipC( MatrC,NomeC,StipC,EtàC Matr,Nome,Stip,Età(Impiegati)

MatrC=Capo

(Supervisione Impiegato=Matricola Impiegati)))

Page 105: ALGEBRA RELAZIONALE

Algebra Relazionale 105

Equivalenza di espressioni algebriche

Espressioni E1 e E2 sono equivalenti per lo schema R, E1RE2 se

E1(r) = E2(r)per ogni istanza r di R.

Le due espressioni sono assolutamente equivalenti, E1E2 se

E1 R E2 per ogni schema R.

Page 106: ALGEBRA RELAZIONALE

Algebra Relazionale 106

equivalenza assoluta:

A,B( A>0(R)) A>0 ( A , B(R))

equivalenza: A,B(R1) A ,C(R2) R A ,B,C(R1 R2)

vale solo per gli schemi R per cui l’intersezione tra gli attributi di R1 e R2 è uguale ad A

ESERCIZIO: trovare un controesempio

Page 107: ALGEBRA RELAZIONALE

Algebra Relazionale 107

Trasformazioni di equivalenza

Due espressioni E1 ed E2 equivalenti garantiscono lo stesso risultato, ma questo non significa che la scelta sia indifferente in termini di “risorse” necessarie

Scopi:1. trasformare le espressioni in modo semplice, affinchè sia

ridotto il numero delle operazioni da eseguire2. il costo di una interrogazione viene valutato in termini di

dimensione dei risultati intermedi: in presenza di alternative si sceglie quella col costo minore.

Page 108: ALGEBRA RELAZIONALE

Algebra Relazionale 108

Trasformazioni di equivalenza (2)

Operazioni che sostituiscono una espressione con un’altra ad essa equivalente

1. Atomizzazione delle selezioni

F1F2(E) F1(F2(E)))2. Idempotenza delle proiezioni

X (E) X ( X Y (E))3. Anticipazione della selezione rispetto al join

F (E1 E2) E1 F (E2) se la condizione F fa riferimento solo ad attributi nella

sottoespressione E2

Page 109: ALGEBRA RELAZIONALE

Algebra Relazionale 109

4. Inglobamento di una selezione in un prodotto cartesiano

F (E1 E2) E1 F E2

5. Distributività della selezione rispetto all'unione

F (E1 E2) F (E1) F (E2)

6. Distributività della proiezione rispetto all'unione

X (E1 E2) X(E1) X (E2)

7. Distributività della selezione rispetto alla differenza

F (E1 - E2) F (E1) - F (E2)

Page 110: ALGEBRA RELAZIONALE

Impiegati Nome Età StipendioMatricola

Bianchi 28 385998Rossi 34 457309

Bruni 23 425698Neri 42 359553

Mori 45 504076Lupi 46 608123

Supervisione Impiegato Capo

59987309

56989553

4076

56985698

40764076

8123

Page 111: ALGEBRA RELAZIONALE

Algebra Relazionale 111

Esercizio: Utilizzando le regole di trasformazione dimostrare che le due espressioni sono equivalenti

Capo ( Matr=Imp Età < 30 (IMPIEGATI SUPERVISIONE))

Capo (SUPERVISIONE Matr=Imp ( Età < 30 (IMPIEGATI))

Page 112: ALGEBRA RELAZIONALE

Algebra Relazionale 112

Trovare i numeri di matricola dei capi di impiegati con meno di 30 anni

Capo ( Matr=Imp Età < 30 (IMPIEGATI SUPERVISIONE))

Per calcolare pochi valori effettua un prodotto cartesiano (molto costoso)

Capo ( Età < 30 ( Matr=Imp (IMPIEGATI SUPERVISIONE)))

Capo ( Età<30 (IMPIEGATI Matr=Imp SUPERVISIONE))

REGOLA 1:

REGOLA 4:

Page 113: ALGEBRA RELAZIONALE

Algebra Relazionale 113

Capo ( Età<30 (IMPIEGATI) Matr=Imp SUPERVISIONE)

REGOLA 3

Page 114: ALGEBRA RELAZIONALE

Algebra Relazionale 114

Viste (relazioni derivate)

Spesso è utile mettere a disposizione degli utenti 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 (quelle che costituiscono effettivamente la base di dati)

Page 115: ALGEBRA RELAZIONALE

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

BD

Schema logico

Schemaesterno

Schema interno

Schemaesterno

Schemaesterno

utenteutente

utenteutente utente

Page 116: ALGEBRA RELAZIONALE

Algebra Relazionale 116

Viste virtuali e materializzate

Due tipi di relazioni derivate: viste materializzate relazioni virtuali (o viste)

Page 117: ALGEBRA RELAZIONALE

Algebra Relazionale 117

Viste materializzate

relazioni derivate effettivamente memorizzate nella base di dati

vantaggi: immediatamente disponibili per le interrogazioni

svantaggi: ridondanti appesantiscono gli aggiornamenti (il loro contenuto

deve essere mantenuto allineato con quello delle relazioni da cui derivano)

non sono supportate dai DBMS commerciali

Page 118: ALGEBRA RELAZIONALE

Algebra Relazionale 118

Viste

relazioni virtuali (o viste): non sono memorizzate nella base di dati sono supportate dai DBMS commerciali una interrogazione su una vista viene eseguita

"ricalcolando" la vista (o quasi) vengono definite nei sistemi relazionali per

mezzo di espressioni nel linguaggio di interrogazione

Page 119: ALGEBRA RELAZIONALE

Algebra Relazionale 119

Viste, esempio

Una vista:Supervisione = Impiegato,Capo (Afferenza Direzione)

A MoriB Leoni

Reparto CapoRossi ANeri BVerdi B

Impiegato Reparto

Bianchi B B Bruni

Afferenza Direzione

Page 120: ALGEBRA RELAZIONALE

Algebra Relazionale 120

Interrogazioni sulle viste

Sono eseguite sostituendo alla vista la sua definizione:

Capo='Leoni' (Supervisione)

viene eseguita come

Capo='Leoni'( Impiegato,Capo (Afferenza Direzione))

Page 121: ALGEBRA RELAZIONALE

Algebra Relazionale 121

Viste, motivazioni

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.Invece: L'utilizzo di viste non influisce sull'efficienza delle

interrogazioni

Page 122: ALGEBRA RELAZIONALE

Algebra Relazionale 122

Viste come strumento di programmazione

Trovare gli impiegati che hanno lo stesso capo di Rossi

Senza vista:Impiegato (Afferenza Direzione)

ImpR,RepR Imp,Reparto ( Impiegato='Rossi' (Afferenza Direzione))

Con la vista: Impiegato (Supervisione) ImpR,RepR Imp,Reparto (Impiegato='Rossi' (Supervisione))