02 Modello, Algebra E Calcolo Relazionale

1

Il modello relazionale 1

Il Modello Relazionale

2

Il modello relazionale

Proposto da E. F. Codd nel 1970 per favorire l’indipendenza dei dati e reso disponibile come modello logico in DBMS reali nel 1981 Oggi e` il modello logico piu` diffuso ed e` adottato dalla larga maggioranza dei DBMS disponibili a livello commerciale

2

3

Il modello relazionaleCaratteristiche:

E` basato su una semplice struttura dati – la relazioneE` caratterizzato da precise basi matematiche (teoria degliinsiemi + logica dei predicati del primo ordine)

VantaggiSemplice rappresentazione dei dati linguaggidichiarativiFacilita` con cui possono essere espresse interrogazionianche complesse

4

Il modello relazionaleDue linguaggi di interrogazione:

algebra relazionale, in cui le interrogazioni sono espresseapplicando operatori specializzati alle relazionicalcolo relazionale, in cui le interrogazioni sono espresseper mezzo di formule logiche che devono essere verificatedalle tuple ottenute come risposta all’interrogazione

I due linguaggi, sotto opportune ipotesi, hanno lo stesso potere espressivoSono la base a partire dalla quale e` statosviluppato il linguaggio standard per l’accesso e la manipolazione di dati relazionali SQL

3

5

Prima di introdurre le relazioni …

DominioProdotto Cartesiano

6

DominioUn dominio è un insieme (anche infinito) di valori

Esempi:l'insieme dei numeri interil'insieme delle stringhe di caratteril'insieme {0,1}

Nel seguito:D insieme di tutti i dominiint: numeri interireal: numeri realistring: stringhedate: date

4

7

Relazione – prodotto cartesiano

D1, D2, …, Dk ∈ D (k insiemi anche non distinti)

il prodotto cartesiano D1×D2×…×Dk è definito come:{(v1, v2, . . . , vk) | v1 ∈ D1, . . . , vk ∈ Dk}

Il prodotto cartesiano D1×D2×…×Dk ha grado kOgni elemento del prodotto cartesiano e` detto tupla

8

RelazioneSiano D1, D2, …, Dk ∈ D domini

Una relazione su D1, D2, …, Dk e` un sottoinsieme finitodel prodotto cartesiano D1×D2×…×Dk

Una relazione, sottoinsieme del prodotto cartesiano dik domini, ha grado kOgni tupla di una relazione di grado k ha k componenti, una per ogni dominio su cui e` definita la relazione cui la tupla appartieneLa cardinalita` di una relazione e` il numero di tupleappartenenti alla relazione

5

9

Notazioni

Sia R una relazione di grado kSia t una tupla di RSia i ∈ {1,...,k}

t[i] denota la i-esima componente di t

10

Esempio D1={0,1,2} D2={d,v}prodotto cartesiano D1 × D2 = {(0,d),(0,v),(1,d),(1,v),(2,d),(2,v)}

una relazione di cardinalita` 3 r1 ⊆ D1 × D2 r1 = {(0,d),(0,v),(1,d)}

una relazione di cardinalita` 2 r2 ⊆ D1 × D2 r2 = {(0,d),(2,d)}

t = (0,d) t[1] = 0 t[2] = d

6

11

Relazione - proprietà

Una relazione è un insieme di tuple, in quanto tali ordinate al loro interno:

(d1, d2, …, dk)

D1 D2 Dk

∈ ∈ ∈

…

12

Relazione - proprieta`

Una relazione è un insieme, quindi: non è definito alcun ordinamento fra le tuplele tuple di una relazione sono distinte l’una dall’altra

E` un insieme finitoCiascun dominio puo` invece essere infinito

7

13

Relazione – notazioneposizionale

La formulazione introdotta permette di riferireogni componente di una tupla per posizione

t = (d1, d2, …, dk )

t[1] t[2] … t[k]

14

Relazioni – notazione per nome

Viene associato un nome, detto nome di attributo, ad ogni componente delle tuple in una relazione

La coppia (nome di attributo, dominio) e` detta attributo

L’uso degli attributi permette didenotare le componenti di ogni tupla per nomepiuttosto che per posizionefornire maggiori informazioni semantiche sulleproprieta` che ogni componente delle tuple in unarelazione modella

Useremo questa notazione

8

15

Relazione - schemaR nome di relazione{A1,A2,. . . , An} un insieme di nomi di attributi

dom : {A1,A2, . . . ,An} → D una funzione totale cheassocia ad ogni nome di attributo in {A1,A2, . . . ,An} ilcorrispondente dominio

La coppia (R(A1,A2, . . . ,An), dom) e` unoschema di relazione

UR denota l’insieme dei nomi di attributi di R UR = {A1,A2, . . . ,An}

16

Schema di base di dati

Siano S1, S2, . . . , Sn schemi di relazioni, con nomi di relazione distinti

S = {S1, S2, . . . , Sn} e` dettoschema di base di dati

9

17

Tupla e relazioneSia (R(A1,A2, . . . ,An), dom) uno schema di relazione

Una tupla t definita su R e` un insieme di funzioni totali f1, f2, . . . , fn, dove

fi : Ai → dom(Ai), i = 1, ..., n, associa all’attributo dinome Ai un valore del dominio di tale attributo

Una relazione definita su uno schema di relazione e` un insieme finito di tuple definite su tale schema

tale relazione e` anche detta istanza dello schema

18

NotazioneSchema di relazione (R(A1,A2, . . . , An), dom), Una tupla t su tale schema puo` essererappresentata come

[A1 : v1,A2 : v2, . . . ,An : vn]vi, i = 1, . . . , n, e` un valore appartenente a dom(Ai)t[Ai] = vi, i =1,…,nA = {Ai1,…,Aik} ⊆ {A1,…,An}t[A] = (vi1,…,vik)

10

19

Esempio

Schema: Film(titolo,regista,anno,genere,valutaz)dom(titolo) = dom(regista) = dom(genere) = stringdom(anno) = intdom(valutaz) = real

Relazione (= istanza dello schema) ⊆ string × string × int × string × real

Tupla: [titolo:‘ed wood’,regista:‘tim burton’,anno:1994,genere:’drammatico’,valutaz:4.00]

20

Valori nulli

Non sempre sono disponibili informazioni sulle entità del dominio applicativo rappresentato nella base di dati

alcune tuple possono non avere un valore per unqualche attributo

Si introduce un valore speciale (valore nullo) che denota la mancanza di valore

11

21

Valori nulli – quale valore?Usare un valore legale per almeno un dominio non e` una buonasoluzione

Se scegliamo 0, 0 e` un valore legale per i domini numericiil suo uso non permetterebbe di distinguere il caso in cui 0 siaeffettivamente il valore dell’attributo dal caso in cui 0 indichi il valorenullo

Assumiamo di denotare il valore nullo con il simbolo ‘?’Il valore nullo e` un valore ammissibile per ogni dominioI linguaggi come SQL permettono di specificare nella definizionedi una relazione quali attributi non possono mai assumere valorenullNotazione

negli schemi evidenziamo con un circoletto gli attributi che possonoassumere valori nulli

22

Esempio

Noleggio(colloc,dataNol,codCli,dataResto)

dom(codCli) = dom(colloc) = intdom(dataNol)= dom(dataRest)= date

12

23

ChiaviUna chiave di una relazione e` un insieme diattributi che distingue fra loro le tuple dellarelazioneSia R(A1, ...,An) uno schema di relazioneUn insieme X ⊆ UR di attributi di R e` chiave di R se verifica entrambe le seguenti proprieta`:

1. qualsiasi sia lo stato di R, non esistono due tuple distintedi R che abbiano lo stesso valore per tutti gli attributi in X

2. nessun sottoinsieme proprio di X verifica la proprieta` (1)Un insieme di attributi che verifica la proprieta` (1) ma non la proprieta` (2), e` detto super-chiave diR

24

Chiavi candidateUna relazione puo` avere piu` di un insieme S di attributi cheverificano le proprieta` (1) e (2)

chiavi candidate Le chiavi delle relazioni vengono individuate mediante esamedel dominio applicativo e dei relativi vincoliUna relazione ha sicuramente almeno una chiave

UR soddisfa sempre la proprieta` (1)

Chiavi candidate

Chiave primaria

Chiavi alternative

13

25

ChiaviUna tupla e’ identificata dal valore di una qualunquechiave candidataSi preferisce pero’ usare la chiave primaria

Usata dal DBMS per ottimizzare le operazioniCriteri di scelta della chiave primaria

Chiave candidata contenente il minor numero di attributiChiave candidata piu` frequentemente utilizzata nelleinterrogazioni

Le chiavi primarie non possono assumere valorinulliLe chiavi alternative possono assumere valori nulli

26

EsempioCliente(codCli,nome,cognome,telefono,dataN,residenza)

Film(titolo,regista,anno,genere,valutaz◦)

Video(colloc,titolo,regista,tipo)

Noleggio(colloc,dataNol,codCli,dataRest◦)

14

27

Chiavi esternePermettono di modellare le associazioniSiano

R ed R′ due relazioniY ⊆ UR’ una chiave per R′ X ⊆ UR un insieme di attributi di R tale che Y e X contengano lo stesso numero di attributi e di dominio compatibile

X e` una chiave esterna di R su R′ se, qualsiasi siano gli stati di R ed R′, per ogni tupla t di R esiste una tupla t′ di R′ tale che

t[X] = t′[Y ]

R viene detta relazione referenteR′ viene detta relazione riferita

28

Chiavi esterne - schema

R(A,B,C,D,E)

R’(F,G,H,I)

Y

X

(D,E) e (F,G) domini compatibili(D,E) puo` essere definita comechiave esterna di R su R’

15

29

Chiavi esterne - istanza

A B C D E

a1 b1 c1 d1 e1a2 b1 c2 d2 e1a3 b2 c3 d1 e1a4 b2 c3 d2 e3

F G H I

d1 e1 h1 i1d1 e2 h2 i2d2 e1 h1 i3d2 e4 h3 i4d2 e2 h1 i1d2 e3 h2 i1

R R’

30

Chiavi esterneLe chiavi esterne permettono di collegare tra lorotuple di relazioni diverse

meccanismo per realizzare le associazioniper valore

16

31

Integrita` referenziale

Qualsiasi siano gli stati di R ed R′, per ogni tupla t di R esiste una tupla t′ di R′ tale che t[X] = t′[Y ]

Vincolo di integrita’ referenziale

32

EsempioCliente(codCli,nome,cognome,telefono,dataN,residenza)

Film(titolo,regista,anno,genere,valutaz◦)

Video(colloc,titoloFilm,registaFilm,tipo)

Noleggio(collocVideo,dataNol,codCliCliente,dataRest◦)

17

33

Esempio

Vincolo diintegrita` referenzialesoddisfatto

34

EsempioVincolo diintegrita` referenzialesoddisfatto

18

35

Esempio

1126 22-Mar-2006 6655 ?

Vincolo diintegrita` referenzialeNON soddisfatto

36

Violazioni integrita` referenziale

L’integrita` referenziale puo` essere violata dainserimenti e modifiche (del valore della chiave esterna) nella relazione referenteda cancellazioni e modifiche (del valore della chiave) nellarelazione riferita

I linguaggi per basi di dati quali SQL permettonoall’utente, nella definizione di chiavi esterne, dispecificare quali azioni eseguire nel caso in cui operazioni di modifica violino l’integrita` referenziale

19

37

Violazioni

1126 22-Mar-2006 6655 ?

Vincolo diintegrita` referenzialeviolato da inserimentoin tabella referente

38

Violazioni

Vincolo diintegrita` referenzialeviolato da modificain tabella referente 6610

6660

6660 non appare

20

39

Violazioni

Vincolo diintegrita` referenzialeviolato da cancellazionein tabella riferita

40

Violazioni

Vincolo diintegrita` referenzialeviolato da modificain tabella riferita

6630

21

41

Osservazione 1I nomi degli attributi nella chiave e nella chiave esterna non devononecessariamente essere gli stessi

Se lo sono, semplificano alcune operazioni (join naturale)Esempio

Cliente(codCli,nome,cognome,telefono,dataN,residenza)Noleggio(collocVideo,dataNol,clienteCliente,dataResto)

Gli attributi avranno sicuramente nomi diversi tutte le volte che la relazione referente e la relazione riferita coincidono, cioe` la chiaveesterna contiene un riferimento alla relazione stessaEsempio

Film(titolo,regista,anno,genere,valutazo,titoloPreoFilm,registaPreo

Film)(titoloPre,registaPre) contengono titolo e regista del film di cui il film e` eventualmente il seguito

42

Osservazione 2Una relazione puo` contenere piu` chiavi esterne, eventualmente anche sulla stessa relazioneLe chiavi esterne, come del resto le chiavi, devonoessere esplicitamente specificate in uno schema direlazione

Il fatto di avere attributi con lo stesso nome e dominicompatibili in relazioni diverse non offre alcuna garanziarelativamente al mantenimento dell’integrita` referenziale

Se non esplicitamente impedito mediante la specifica di un apposito vincolo, le chiavi esternepossono assumere valore nullo

22

43

Vincoli di integrita`Abbiamo visto

Vincoli di dominioVincoli di obbligatorieta`Vincolo di chiave (primaria, alternativa)Vincolo di integrita` referenziale (chiave esterna)

Questi vincoli non sono sufficienti a garantire che ilcontenuto della base di dati rispecchi in modo fedelele informazioni del dominio applicativo darappresentare

Come faccio a garantire che la valutazione di un film sia un numero decimale compreso tra 0 e 5?

Discuteremo nel seguito altre categorie di vincoli


Algebra Relazionale

23

45

Operazioni nel Modello Relazionale

Le operazioni sulle relazioni possono essere espresse in due formalismi di base:

Algebra relazionale: le interrogazioni (query) sono espresse applicando operatori specializzati alle relazioni Calcolo relazionale: le interrogazioni (query) sono espresse per mezzo di formule logiche che devono essere verificate dalle tuple ottenute come risposta all'interrogazione

I due formalismi (sotto opportune ipotesi) sono equivalenti

46

Algebra Relazionale

Esistono cinque operazioni di base:Proiezione SelezioneProdotto cartesianoUnioneDifferenza

Queste operazioni definiscono completamente l’algebra relazionale

24

47

Algebra RelazionaleOgni operazione restituisce come risultato una relazione

è pertanto possibile applicare una operazione al risultato di un'altra operazione (proprietà di chiusura)

Esistono operazioni addizionali, che possono essere espresse in termini delle cinque operazioni di base

Non aumentano il potere espressivo dell’agebra ma sono comode a fini praticiOperazione fondamentale: join

48

Algebra RelazionaleLa definizione delle varie operazioni e` leggermente diversa a seconda che si consideri la definizione del modello relazionale per posizione o la definizione per nomeConsidereremo la definizione per nomeOperazione addizionale

RidenominazionePermette di modificare il nome degli attributi

25

49

RidenominazioneLa ridenominazione di una relazione R rispetto ad una lista

di coppie di nomi di attributi (A1,B1),…, (Am,Bm) tale che Ai è un nome di attributo di R, denotata con

ridenomina l’attributo di nome Ai con il nome Bi

La ridenominazione è corretta se il nuovo schema della relazione R ha attributi con nomi tutti distintiLa relazione ottenuta ha lo stesso grado della relazione R ed ha lo stesso contenutoGli attributi della relazione risultato sono UR \ {A1,A2, . . . ,Am} ∪ {B1,B2, . . . ,Bm}

( )Rmm BBAA ,,, 11 KK ←ρ

50

Ridenominazione - esempio

La ridenominazione:

cambia lo schema di Noleggio daNoleggio(colloc,dataNol,codCli,dataRest)

aNoleggio(video,dataIn,cliente,dataFine)

( )NoleggiodataFinecliente,dataIn, video,dataRest codCli,dataNol,colloc, ←ρ

26

51

ProiezioneLa proiezione di una relazione R su un insieme di attributi A={A1,…Am},

A ⊆ UR, indicata con

è una relazione di grado m le cui tuple hanno come attributi solo quelli specificati in A

La proiezione genera un insieme T di tuple con m attributi (grado m)Se t=[A1:v1,…Am:vm] è in T allora esiste una tupla t’ in R tale che per ogni Ai in A, t[Ai]=t’[Ai]Nella relazione risultato gli attributi hanno l’ordine specificato in ALa cardinalita` di T puo` essere diversa dalla cardinalita` di R

Eliminazione duplicati

)(,,1 RAmA KΠ

52

Proiezione - esempio

dbcfadcbaCBA

R ( )RCA,Π ( )RAB,Π

dcfdcaCA

cbdaabAB

abB

( )RBΠ

27

53

Proiezione - esempio

54

SelezioneLa selezione su una relazione R, dato un predicato F

su R, indicata con σF (R)

genera una relazione che contiene tutte le tuple di R che verificano F

Il grado della relazione risultato è uguale al grado della relazione operandoI nomi degli attributi della relazione risultato sono gli stessi della relazione operandoLa cardinalita` del risultato e` minore o uguale alla cardinalita` della relazione di partenza

28

55

Selezione - predicati

Un predicato F su una relazione R ha una delle seguenti forme:

predicato semplicecombinazione booleana di predicati semplici, ottenuta con i connettivi ∧ (AND), ∨ (OR), ¬(NOT)

56

Selezione - predicati

Un predicato semplice ha una delle seguenti forme:

A op vA op A’

dove:A e A’ sono attributi di Rop è un operatore relazionale di confronto >,<,>=,<=,=, ≠v è una costante compatibile con il dominio di A

29

57

Selezione – esempi di predicati

codCli=6635 predicato semplicedataNol=dataRest predicato semplice

codCli=6635 ∧ dataNol=dataRestcombinazione booleana

58

SelezioneSia t=[A1:v1,…Ak:vk] una tupla in T = σF (R) t è tale che:

F(A1/t[A1],…,Ak/t[Ak]) è veraLa notazione Ai/t[Ai] indica la sostituzione in F del nome di attributo Ai (se tale nome compare in F) con il valore t[Ai] dell’attributo di nome Ai in tSe nessuna tupla di R verifica il predicato F, allora il risultato è una relazione vuota

30

59

Selezione - esempio

dbcfadcbaCBA

R dbccbaCBA

fadCBA

dbccbaCBA

( )RbB=σ ( )RbNOTB=σ

( )RCAbB == ORσ ( )RCAbB == ANDσ

CBA

60

Selezione - esempio

31

61

Prodotto cartesianoIl prodotto cartesiano di due relazioni R ed S, di grado

k1, k2, indicato con:R X S

è una relazione di grado k1+k2 le cui tuple sono tutte le tuple che hanno:

come prime k1 componenti le tuple di Rcome seconde k2 componenti le tuple di S

62

Prodotto cartesianoSi applica solo se R e S hanno schemi disgiuntiSe le due relazioni hanno attributi con lo stesso nome, è necessario ridenominare gli attributi in una delle due relazioniNella relazione risultato:

i primi k1 attributi sono gli attributi della relazione Rgli ultimi k2 attributi sono gli attributi della relazione S

La cardinalita` del risultato e` il prodotto delle cardinalita` degli argomenti

32

63

Prodotto cartesiano - esempio

dbcfadcbaCBA

fadagbFED

R

S

faddbcagbdbcfadfadagbfadfadcbaagbcbaFEDCBA

R X S

64

Prodotto cartesiano – esempio

33

65

UnioneL’unione di due relazioni R, S, indicata con

R∪S è l’insieme delle tuple in R, S o in entrambe

L’unione di due relazione può essere fatta solo se hanno lo stesso schemaLa relazione risultato ha lo stesso schema delle relazioni argomentoLe tuple duplicate vengono eliminate Il grado della relazione risultato è uguale al grado delle relazioni operandi

66

Unione - esempio

dbcfadcbaCBA

fadagbCBA

agbdbcfadcbaCBA

R

S

R∪S

34

67

Unione - esempio

68

DifferenzaLa differenza di due relazioni R ed S, indicata con

R-S è l’insieme delle tuple che sono in R ma non in S

La differenza (come l’unione) può essere eseguita solo se le relazioni hanno lo stesso schemaLa relazione risultato ha lo stesso schema delle relazioni argomentoIl grado della relazione risultato è uguale al grado delle relazioni operandi

35

69

Differenza - esempio

dbcfadcbaCBA

fadagbCBA

dbccbaCBAR

S

R-S

70

Differenza - esempio

36

71

Operazioni derivate -intersezione

L’intersezione di due relazioni R, S, indicata con R∩S

è l’insieme delle tuple contenute in R e in S

L’intersezione di due relazione può essere fatta solo se hanno lo stesso schemaLa relazione risultato ha lo stesso schema delle relazioni argomentoIl grado della relazione risultato è uguale al grado delle relazioni operandi

72

Operazioni derivate -intersezione

L’intersezione è un’operazione derivataPuò infatti essere definita come segue

R∩S = R - (R - S)

37

73

Operazioni derivate –intersezione - esempio

dbcfadcbaCBA

fadagbCBA

fadCBA

R S R ∩ S

dbccbaCBA

fadCBA

R - SR - (R-S)

74


38

75


76

Operazioni derivate - joinIl join (detto anche theta-join) di due relazioni R ed S

sugli attributi A di R ed A’ di S, indicato con

è definito come

Il join è quindi un prodotto cartesiano seguito da una selezioneIl predicato AθA’ è detto predicato di join

SR AA 'θ><

( )SRAA ×'θσ

39

77

Operazioni derivate - join

Come per il prodotto cartesiano, gli schemi delle due relazioni argomento devono essere disgiunti e lo schema della relazione risultato e` dato dalla loro unioneIl grado della relazione risultato è uguale alla somma dei gradi delle relazioni operandi

78

Operazioni derivate – join -esempio

987

654

321

CBA

2613ED

13321EDCBA

2632113321

26654

EDCBA

R

S

SR DB<><

SR EA=><

40

79


80

Operazioi derivate - join

Il join e` un’operazione estremamente importante in quanto permette di collegare tuple di relazioni diverse e di attraversare le associazioni rappresentate nelle relazioni della base di dati mediante il meccanismo delle chiavi esterneIl join prende il nome di equi-join quando l’operatore usato nel predicato di join e` l’operatore di uguaglianza (=)

41

81


Determinare il titolo ed il regista dei film noleggiatiil 15 Marzo 2006 dal cliente di codice 6635

82

Operazioni derivate – joinnaturale

L’operazione di join naturale è una ‘semplificazione’ del joinHa senso solo nella notazione con nome del modello relazionaleE’ un tipo di join molto frequenteL’operazione di join naturale indica un tipo di join basato sull’eguaglianza degli attributi comuni a due relazioni

42

83


Il join naturale di due relazioni R ed S e` indicatocon

Sia{A1,…,Ak} = UR∩US

{I1,…,Im} = UR∪US

{B1,…,Bk} nomi di attributi che non compaiono ne’ in R ne’ in S

l’espressione che definisce il join naturale è

( )( )( )( )SRc BkB1,...,AkA1,...,Im,...,1I ←×Π ρσ

SR ><

84


Nella formula precedente c indica la formula

Pertanto il join naturale esegue un join eguagliando gli attributi con lo stesso nome delle due relazioni argomento dell’operazione e poi elimina gli attributi duplicati dalla relazione risultatoAffinche’ l’operazione di join sia ben definita, gli attributi con nomi uguali nelle relazioni argomento dell’operazione devono avere domini compatibili

A1=B1 AND A2 = B2 AND … AND Ak = Bk

43

85


UR = US

Join naturale = intersezione

UR ∩ US = ∅Join naturale = prodotto cartesiano

Il join naturale permette di navigare in modo molto piu` agevole, rispetto al join, le associazioni rappresentate tramite il meccanismo delle chiavi esterne, nel caso in cui per chiave e chiave esterna sia stato utilizzato lo stesso nome

86

Operazioni derivate – joinnaturale - esempio

dacfbbcbdcbaCBA

bdaecbdcbDCB

bdac

ecbd

dcbd

ecba

dcba

DCBA

RS

SR ><

44

87

Operazioni derivate – joinnaturale - esempio

Supponiamo di voler abbinare codice e nome del clienteal titolo e all’anno dei film di Quentin Tarantino solo se ilcliente ha noleggiato almeno un video di quel film

88

Operazioni derivate - divisione

Date due relazioni R ed S con insiemi di attributi URed US, rispettivamente, e tali che UR ⊃ US, l'operazione di divisione di R per S è denotata da

R ÷ Spermette di determinare le tuple t di schema D = UR – US tali che in R appaiono tutte le tuple che si ottengono combinando t con ogni tupla di S

45

89

Operazioni derivate - divisioneUna tupla t viene cioe` restituita se, per ogni tupla s in S, in R e` presente una tupla r tale che

r[D] = t[D] e r[US] = s[US]Formulazione alternativa, che giustifica il suo nomecome operazione “inversa” del prodotto:

t ∈ R÷S se e solo se {t}×S ⊆ R l’operazione di divisione determina le tuple per cui in una relazione c’e` una corrispondenza con tutte le tuple di un’altra relazione

90

Operazioni derivate – divisione- esempio

daadbbdbacbaCBA

dadbcbCB

RS

aA

R ÷ S

46

91


daadbbdbacbaCBA

dadbcbCB

RS

aA

R ÷ S

92


Determinare i codici dei clienti che hanno noleggiato tutti i film di Tim Burton

1. Film di Tim Burton

47

93


2. Film noleggiati dai clienti

94


NC ÷ TB

48

95

Operazioni derivate – divisione

La divisione si puo` esprimere nel modo seguente:

ΠD (R) - Π D((ΠD (R) x S) - R)

dove D = (UR - US)

96


49

97


98


663566426610

50

99

Algebra relazionale - esempioSelezionare i codici dei clienti che hanno noleggiato sia film drammatici che film horror

1. Codici clienti che hanno noleggiato almeno un film drammatico

R =

2. Codici clienti che hanno noleggiato almeno un film horror

S =

3. Risultato: R ∩ S

100

Algebra relazionale - esempio

Selezionare i codici dei clienti che non hanno mainoleggiato film horror

1. Codici clienti R =

2. Codici clienti che hanno noleggiato almeno un film horror

S =

3. Risultato: R - S

51

101

Algebra relazionale - esempioSelezionare i codici dei clienti che hanno noleggiato film dialmeno due generi diversi

1. Coppie cliente/genere film noleggiatiR =

2. Associazione binaria tra coppie cliente/genere film noleggiatoS = R X

3. Risultato: Selezione delle associazioni relative allo stessocliente, ma generi diversi e proiezione sul codiceT =

Si poteva anche risolvere con un join naturale, cosa sarebbecambiato?

102

Algebra relazionale - esempioSelezionare titolo e regista del film con la valutazione piu` alta

1. Titolo e regista di tutti i film

R =

2. Titolo e regista dei film con valutazione non massima (film per cui esiste un altro film con valutazione maggiore della loro)

S =

3. Risultato: R - S

52

103

Algebra relazionale – sintesi


Calcolo Relazionale

53

105

Algebra vs. calcoloL’algebra relazionale è un linguaggio procedurale

dobbiamo indicare le operazioni da eseguire per ottenere il risultato di una data interrogazione

Il calcolo relazionale e` un linguaggio dichiarativo

viene data una descrizione formale del risultato, senza specificare come ottenerlo

106

Calcolo relazionale - VariantiDue varianti del calcolo relazionale:

Tuple relational calculus (TRC)le variabili rappresentano tuple

Domain relational calculus (DRC)le variabili rappresentano valori di dominiogni espressione richiede un numero molto elevato di variabiliusate in interfaccie grafiche

54

107

Calcolo relazionale - atomis∈R (R è un nome di relazione ed s è una variabile)

la tupla s appartiene alla relazione R

s[A] θ u[A’] (s ed u sono variabili, θ è un operatore relazionale di confronto, A ed A’ sono nomi di attributi)

il valore di A nella tupla s è in relazione θ con il valore di A’nella tupla u

s[A] θ a (s è una variabile, θ è un operatore relazionale di confronto, A è un nome di attributo, a è una costante)

il valore di A nella tupla s è in relazione θ con il valore a

108

Calcolo relazionale - formuleVariabili libere e legate

data una formula F ed una variabile x, x è liberain F se e solo se x non compare

in un quantificatore ∀x (quantificazione universale) In un quantificatore ∃x (quantificazione esistenziale)

55

109

Calcolo relazionale - formuleogni atomo è una formula

tutte le occorrenze delle variabili dell’atomo sono libere

se φ1 e φ2 sono formule, allora φ1∧φ2, φ1∨φ2, ¬φ1 sono formule

le occorrenze delle variabili sono libere o legate a seconda di come sono in φ1 e φ2

se φ è una formula allora ∃s(φ), ∀s(φ) sono formuletutte le occorrenze di s in φ sono legate al quantificatore ∃(oppure ∀)

se φ è una formula allora (φ) è una formulale occorrenze delle variabili sono libere o legate a seconda di come sono in φ

110

Calcolo relazionale – verita` delle formule

Presentiamo una formulazione intuitivadati

una formula f(x1, x2,…, xn), con x1, x2,…, xnvariabili libereuna tupla di valori (a1, a2,…, an )

f(x1, x2,…, xn) e` vera su (a1, a2,…, an ) se sostituendo xi con ai si ottiene il valore True

56

111

Calcolo relazionale – formule -esempio

cc formula legaletutte le occorrenze sono legatela formula e` vera se esiste una tupla appartenente alla relazioneFilm avente il valore dell’attributo valutaz maggiore di 3.50

formula legatetutte le occorrenze di x sono legatetutte le occorrenze di y sono liberela formula e` vera sulla tupla (‘big fish’) con schema (Titolo) se esiste una tupla appartenente alla relazione Film avente il valoredell’attributo valutaz maggiore di 3.5 e titolo uguale a ‘big fish’

112

Calcolo relazionale -espressioni

In TRC un’espressione o interrogazione ha la forma {x:U|f(x)}

doveU e` un insieme di attributif e` una formula legale del calcolox e` la sola variabile libera in f

un’espressione è quindi definita come l’insieme di tutte le tuple x su un insieme di attributi U tali che il la formula f è vera per x

57

113

cc

espressione correttaritrova i registi di cui almeno un film ha valutazionesuperiore a 3.50

espressione errata poiche’ x non e` libera

Calcolo relazionale –espressioni - esempio

114

Calcolo relazionale - esempiRitrovare titolo ed anno di uscita dei film presenti nellavideoteca

Ritrovare i noleggi effettuati dal cliente con codice 6635

Ritrovare l’anno ed il genere dei film il cui regista e` Tim Burton o Gabriele Salvatores

58

115

Calcolo relazionale - esempiRitrovare per i noleggi di film di Quentin Tarantino il codice ed il nome del cliente che ha effettuato il noleggio insieme al titolo ed all’anno del film noleggiato

116

Calcolo relazionale - esempiRitrovare i codici dei clienti che hanno noleggiato sia film drammatici sia film horror

59

117

Calcolo relazionale –esprimere l’algebra con il TRC

Proiezione: ΠA1,…Ak (R){t:{A1,…,Ak}|∃x(x∈R∧x[A1]=t[A1]∧…∧x[Ak]=t[Ak]}

Selezione: σF(R) {t:UR|t ∈R ∧F’}

dove F’ è la formula F con ogni attributo A sostituito da t[A]

118

Calcolo relazionale –esprimere l’algebra con il TRC

Prodotto cartesiano: RxS siano UR ={A1,…,An} e US ={A’1,…,A’m} gli insiemi degli attributi di R ed S

{t: UR ∪ US |∃x(∃y(x∈R∧y∈S∧x[A1]=t[A1]∧…∧x[An]=t[An] ∧y[A’1]=t[A’1]∧…∧ y[A’m]=t[A’m]))}

Unione: R∪S {t : UR | t ∈ R ∨ t∈S}Differenza: R-S {t : UR | t ∈ R ∧ ¬t∈S}

60

119

Calcolo relazionale – potere espressivo

L’algebra relazionale e il calcolo relazionale hanno lo stesso potere espressivo?Cioè

tutte le operazioni esprimibili mediante espressioni dell’algebra relazionale possono essere espresse mediante espressioni del calcolo relazionale e viceversa?

120


La semantica di un’interrogazione (in algebra o in calcolo) è una funzione che trasforma una base di dati relazionale (insieme di relazioni) in una nuova base di dati relazionalealgebra e calcolo hanno lo stesso potere espressivo se per ogni interrogazione Q1 in uno dei due formalismi esiste un’interrogazione Q2 nell’altro la cui semantica è la stessa funzione

61

121


Non tutte le espressioni del calcolo possono essere tradotte in equivalenti espressioni dell’algebraEsempio:

l’espressione{t:UFilm| ¬t∈Film}

è sintatticamente correttapoiche’ alcuni attributi di Film hanno dominio infinito (ad esempio Titolo, con dominio string) questa espressione è soddisfatta da un numero infinito di tuple

il risultato non sarebbe una relazione!

122


Si introduce quindi una condizione sintattica (safety) sufficiente ad evitare situazioni come quella precedenteL’espressione

{t:UFilm| ¬t∈Film}non è safeil calcolo relazionale safe e l’algebra relazionale hanno lo stesso potere espressivola traduzione da un formalismo all’altro può essere effettuata in tempo polinomiale nella dimensione dell’espressione

62

123

Perché due linguaggi?Algebra relazionale

linguaggio proceduraleutile per il sistema

Calcolo relazionale (safe)linguaggio dichiarativoutile per l’utente

i linguaggi di interrogazione nei sistemi reali si basano sul calcolol’algebra relazionale viene utilizzata come linguaggio interno

l’interrogazione utente viene compilata in un’espressione dell’algebra relazionaleil sistema utilizza le proprietà dell’algebra per stabilire quale espressione permette di risolvere l’interrogazione iniziale nel modo più efficiente

Date post:	26-May-2015
Category:	Business
Upload:	guestbe916c
View:	1,607 times
Download:	0 times

02 Modello, Algebra E Calcolo Relazionale

Business