Calcolo Relazionale

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

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

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à

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, F1F2, F1F2, 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

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

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)))}

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) 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”}

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}