Calcolo relazionale

Calcolo Relazionale
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
Marina Mongiello
Calcolo Relazionale vs Algebra
Relazionale
Algebra
• Linguaggio di
interrogazione
procedurali
• Dispone di operatori la
cui applicazione
consente di giungere al
risultato
Marina Mongiello
Calcolo
• Famiglia di linguaggi di
interrogazione dichiarativi
• Basato sul calcolo dei predicati
del primo ordine
• Esempi di linguaggi usati in
DBMS commerciali: SQL
Algebra vs Calcolo
Algebra
Calcolo
Uguale Espressività
Una medesima interrogazione può essere
effettuata in algebra relazionale ed in
calcolo relazionale
(fornendo lo stesso risultato)
Marina Mongiello
Varianti del calcolo relazionale
• Calcolo relazionale su tuple
• Calcolo relazionale su domini
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.
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
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, F1F2, F1F2, x F(x),  x F(x)
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
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
–
–
–
–
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
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
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
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
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)))
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)
Marina Mongiello
Esempio
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
Marina Mongiello
1. Selezionare la data di nascita e l’indirizzo dell’impiegato Mario
Rossi
Q1: {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 sviluppo
Q2:{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 dipendenti
Q3:{e.Cognome, e.Nome | Impiegati(e) and (not (d) Dipendenti(d)
and e.Codice=d.ICodice))}
Usando il quantificatore universale
Q3a:{e.Cognome, e.Nome | Impiegati(e) and ((d)
(not(Dipendenti(d)) or not (e.Codice=d.ICodice)))}
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}
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)
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)) }
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) and
w.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”}
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
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)
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}
Marina Mongiello