calcolo relazionale. marina mongiello linguaggi di interrogazione nel modello relazionale per...
TRANSCRIPT
![Page 1: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/1.jpg)
Calcolo Relazionale
![Page 2: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/2.jpg)
Marina Mongiello
Linguaggi di interrogazione
Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione due tipologie di linguaggi:
• Linguaggi dichiarativi Specificano le proprietà del risultato dell’interrogazione
• Linguaggi procedurali Specificano la sequenza di operazioni da seguire per ottenere il risultato dell’interrogazione
![Page 3: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/3.jpg)
Marina Mongiello
Calcolo Relazionale vs Algebra Relazionale
Calcolo• Famiglia di linguaggi di
interrogazione dichiarativi• Basato sul calcolo dei
predicati del primo ordine• Esempi di linguaggi usati
in DBMS commerciali: SQL
Algebra• Linguaggio di
interrogazione procedurali
• Dispone di operatori la cui applicazione consente di giungere al risultato
![Page 4: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/4.jpg)
Marina Mongiello
Algebra vs Calcolo
Una medesima interrogazione può essere effettuata in algebra relazionale ed in calcolo relazionale
(fornendo lo stesso risultato)
CalcoloAlgebra
Uguale Espressività
![Page 5: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/5.jpg)
Marina Mongiello
Varianti del calcolo relazionale
• Calcolo relazionale su tuple• Calcolo relazionale su domini
![Page 6: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/6.jpg)
Marina Mongiello
Proprietà dei linguaggi relazionali
• Un linguaggio relazionale L si definisce completo se è possibile esprimere in L interrogazioni che possono essere espresse mediante il calcolo relazionale
• La proprietà di completezza relazionale consente di confrontare l’espressività di linguaggi di query di alto livello.
![Page 7: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/7.jpg)
Marina Mongiello
Calcolo dei predicati del primo ordine
• Logica dei predicati• Calcolo perché è semidecidibile
esiste una procedura che consente di stabilire se una formula è soddisfatta
![Page 8: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/8.jpg)
Marina Mongiello
Sintassi
• Simboli di costante ( a,b,c)• Simboli di variabile (x,y,z)• Simboli di predicati (p,q)• Un termine è una costante o una variabile• Un atomo è un simbolo di predicato a n posti
seguito da n termini: esempio P(a,x,y)• Una formula è:
– un atomo– se F, F1, F2 sono formule, una formula può
essere: F, F1F2, F1F2, x F(x), x F(x)
![Page 9: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/9.jpg)
Marina Mongiello
Interpretazione di formule
• Alle formule possono essere associati modelli del mondo reale che soddisfino o meno dette formule
• Interpretazione di formule del primo ordine – Dominio di interpretazione: insieme di elementi– Costanti
• Una formula è soddisfacibile se esiste una
interpretazione che la soddisfa
• Una formula è valida se è soddisfatta in qualunque interpretazione
![Page 10: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/10.jpg)
Marina Mongiello
Semantica
L’interpretazione definisce la semantica della logica: Congiunzione Disgiunzione Negazione – Una formula x F(x) è soddisfatta se esiste
un elemento a tale che F(a) sia soddisfatta– Una formula (x) F(x) è soddisfatta se per
tutti gli elementi a,b,c, … F (a), F(b),ecc sono soddisfatte
![Page 11: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/11.jpg)
Marina Mongiello
Calcolo relazionale su tuple
Specifica un insieme variabile di tuple,
Le query sono del tipo{t | condizione(t)}
• t è l’insieme variabile delle tuple • condizione(t) è la condizione che
deve essere soddisfatta
![Page 12: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/12.jpg)
Marina Mongiello
Espressione generale del calcolo relazionale su tuple
L’espressione generale per rappresentare interrogazioni nel calcolo relazionale su tuple è la seguente:
{t1.A1,t2.A2,..tn.An| Condizione(t1, t2,.., tn,tn+1, tn+2,..., tn+m)}
– t1, t2,.., tn,tn+1 sono tuple
– ciascun Ai è un attributo della relazione a cui t appartiene,
– Condizione(t1, t2,.., tn,tn+1, tn+2,..., tn+m) è la formula o condizione del calcolo relazionale su tuple.
Una formula è definita mediante atomi del calcolo dei predicati
![Page 13: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/13.jpg)
Marina Mongiello
Atomi
Un atomo può essere:R(ti) dove R è una relazione e ti una tupla variabile. L’atomo
identifica il range delle tuple variabili ti come la relazione di nome R
ti.A op tj.B dove op è un operatore di confronto appartenente all’insieme {=, ,<,,>,}; ti e tj sono tuple variabili; A è un attributo della relazione in cui varia ti; B è un attributo della relazione in cui varia tj
ti.A op c oppure c op tj.B dove op è un operatore di confronto dell’insieme {=, ,<,,>,}; ti e tj sono tuple variabili; A è un attributo della relazione in cui varia ti; B è un attributo della relazione in cui varia tj
![Page 14: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/14.jpg)
Marina Mongiello
Formule
Una formula è ottenuta combinando più atomi mediante operatori logici ed è definita induttivamente (ricorsivamente) nel modo seguente:
• Ogni atomo è una formula• Se F1 ed F2 sono formule:
– F1 and F2– F1 or F2 – not F1 sono formule. Il valore di verità è dato dalla semantica
definita per la logica del primo ordine
![Page 15: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/15.jpg)
Marina Mongiello
Trasformazioni tra quantificatori
x P(x) (not x) ( not P(x)) x P(x) not x not P(x)x (P(x) and Q(x) (not x) (not P(x)or not Q(x))x (P(x) or Q(x)) (not x) ( not P(x)and not
Q(x)) x (P(x) or Q(x)) not x (not P(x) and not
Q(x))) x (P(x) and Q(x)) not x (not P(x) or not
Q(x)))
![Page 16: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/16.jpg)
Marina Mongiello
Database di esempio
Sia data la seguente base di dati relazionale Impiegati(Codice, Nome, Cognome, Età, Indirizzo,
DNo, Stipendio, CodiceCapo)Dipartimenti(DNumero,DNome, CodiceCapo)Sede(DNumero,DCittà)Progetti( PNumero, PNome, PSede, DNum)Lavora_su(ICodice,PNo,Ore)Dipendenti(ICodice, NomeDip, Sesso, DataN,
Parentela)
![Page 17: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/17.jpg)
Marina Mongiello
Selezionare gli impiegati con stipendio maggiore di 2000 euro
{t | Impiegati(t) and t.Stipendio>40}
Impiegati(t) specifica che il range della tupla t è la relazione Impiegati.
t.Stipendio>2000 specifica le condizione che deve essere soddisfatta dalle tuple recuperate
Le tuple recuperate saranno quelle in cui il campo Stipendio assume valore >2000
Esempio
![Page 18: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/18.jpg)
Marina Mongiello
1. Selezionare la data di nascita e l’indirizzo dell’impiegato Mario RossiQ1: {t.Data, t.Indirizzo| Impiegati(t) and t.Cognome=‘Rossi’
and t.Nome=‘Mario’}
2. Selezionare il nome e l’indirizzo di tutti gli impiegati che lavorano nel dipartimento ricerca e sviluppoQ2:{t.Nome, t.Cognome,t.Indirizzo| Impiegati(t) and ((d)
(Dipartimenti(d) and d.DNome=‘R&D’ and d.DNumero=t.DNo))}
3. Selezionare il nome degli impiegati che non hanno dipendentiQ3:{e.Cognome, e.Nome | Impiegati(e) and (not (d)
Dipendenti(d) and e.Codice=d.ICodice))}Usando il quantificatore universaleQ3a:{e.Cognome, e.Nome | Impiegati(e) and ((d)
(not(Dipendenti(d)) or not (e.Codice=d.ICodice)))}
![Page 19: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/19.jpg)
Marina Mongiello
4. Selezionare i nomi dei manager che hanno almeno un dipendente
Q4:{e.Cognome, e.Nome | Impiegati(e) and ((d) (p) (Dipartimento(d) and Dipendente(p) and e.Codice=d.CodiceCapo and p.ICodice=e.Codice))}
5. Selezionare per ogni progetto con sede a Milano il numero del progetto, il numero del dipartimento che lo gestisce, il cognome del manager del dipartimento, la sua data di nascita ed indirizzo
Q5:{p.Pnumero, p.DNum, m.Cognome, m.Data, m.Indirizzo |
Progetti(p) and Impiegati(m) and p.Sede=‘Milano’ and ((d) (Dipartimenti(d) and p.Dnum=d.DNumero and
d.CodiceCapo=m.Codice}
![Page 20: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/20.jpg)
Marina Mongiello
6. Selezionare i nomi degli impiegati che lavorano su tutti i progetti controllati dal dipartimento numero 5
Q6a:{e.Cognome, e.Nome | Impiegati(e) and F}F= ( not (x) (Progetti(x) and (x.DNum=5) and
F’)F’ = (not (w) (Lavora_su(w) and
w.ICodice=e.Codice and x.PNumero=w.PNo)))
Q6b:{e.Cognome, e.Nome | Impiegati(e) and F1}
F1 =(x) (not (Progetti(x)) or F2)
F2=(not (x.DNum=5) or F3)
F3=(w)(Lavora_su(w) and w.ICodice=e.Codice and x.PNumero=w.PNo)
![Page 21: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/21.jpg)
Marina Mongiello
7. Selezionare il nome ed il cognome di ogni impiegato e del relativo manager
Q7:{e.Cognome, e.Nome, m.Nome, m.Cognome | Impiegati(e) and Impiegati(m) and e.Codicecapo=m.Codice}
8. Selezionare il nome di tutti gli impiegati che lavorano su qualche progetto controllato dal dipartimento numero 5.
Q8:{e.Cognome, e.Nome | Impiegati(e) and (( X) (w) (Progetti(x) and Lavora_su (w) and
x.DNum=5 and w.ICodice=e.Codice and x.PNumero=x.Pno)) }
![Page 22: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/22.jpg)
Marina Mongiello
9. Selezionare una lista di progetti che coinvolgono impiegati il cui cognome sia “Rossi”, sia in qualità di impiegato che di manager del dipartimento
Q9:{p.PNumero | Progetto(p) and ((( e) (w) (Impiegato(e) and Lavora_su(w) andw.PNo=p.Numero and e.Cognome=“Rossi” and
e.Codice=w.ICodice))or((m) (d)(Impiegato(m) and Dipartimento(d) and
p.DNum=d.DNumero and d.CodiceCapo=m.Codice and m.Cognome=“Rossi”}
![Page 23: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/23.jpg)
Marina Mongiello
Calcolo relazionale su domini
• Le espressioni sono del tipo:{A1: x1,…,Ak: xk| f}
– A1,…,Ak sono attributi distinti
– x1,…,xk sono variabili
– f una formula
– A1: x1 ,…,Ak: xk è la target list: definisce la struttura del risultato
![Page 24: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/24.jpg)
Marina Mongiello
Sia data la seguente base di dati relazionale
Impiegati(Matricola, Nome, Età, Stipendio) Supervisione(Capo, Impiegato)
Selezionare gli impiegati con stipendio superiore a 2000 Euro
Q0: {Matricola:m,Nome:n,Età:e,Stipendio:s | Impiegati(Matricola:m,Nome:n,Età:e,Stipendio:s) s>2000}
Equivale alla query in algebra relazionale:stipendio>2000(Impiegati)
![Page 25: Calcolo Relazionale. Marina Mongiello Linguaggi di interrogazione Nel modello relazionale per effettuare le operazioni di interrogazione si hanno disposizione](https://reader036.vdocumenti.com/reader036/viewer/2022062418/5542eb4a497959361e8b5998/html5/thumbnails/25.jpg)
Marina Mongiello
Selezionare i codici dei capi degli impiegati che guadagnano più di 2000 Euro
Q1: {Capo:c | Impiegati(Matricola:m,Nome:n,Età:e,Stipendio:s) Supervisione(Impiegato:m, Capo:c) s>2000}