Principale limitazione di AR e SQL-92: interrogazioni ricorsive
IMPIEGATO
NOME
NOMECAPO
Rossi
Verdi
Neri
Verdi
Verdi
DeSio
Tucci
DeSio
DeLuca
DeSio
DeSio
Lazio
Lazio
Query
selezionare tutti i capi
di “Rossi”
NOMECAPO
Verdi
DeSio
Lazio
Questa interrogazione è riconducibile ad un caso
di chiusura transitiva di una relazione binaria
In SQL-3 (SQL-1999) si possono esprimere interrogazioni ricorsive
In DB2
WITH CAPO (NOME, NOMECAPO) AS
(
SELECT NOME, NOMECAPO
FROM IMPIEGATO
UNION
SELECT CAPO.NOME, IMPIEGATO.NOMECAPO
FROM CAPO, IMPIEGATO
WHERE CAPO.NOMECAPO = IMPIEGATO.NOME
SELECT NOMECAPO
FROM CAPO WHERE NOME = 'Rossi'
AND NOMECAPO IS NOT NULL;
)
Access non accetta
interrogazioni
ricorsive
Interrogazioni Ricorsive in SQL

In SQL2 non è possibile definire interrogazioni che facciano uso della
ricorsione
Esempio
– Impiegato(Nome,NomeCapo)
– non è possibile esprimere l’interrogazione che ritrova “tutti i capi di un
impiegato”, con un numero arbitrario di livelli intermedi
per risolvere queste interrogazioni con SQL2, è necessario utilizzare SQL da
programma (o stored procedure)
in SQL-99 c’è la possibilità di esprimere interrogazioni ricorsive

base teorica: basi di dati deduttive



–
Capo(Nome,NomeCapo)  Capo(Nome,NomeCapo)
Capo(Nome,NomeCapo) Impiegato(Nome,impiegato1),
Capo(impiegato1,NomeCapo)
–
Capo è una vista ricorsiva: nella sua definizione usa se stessa
–
SQL-99 - comando WITH

il comando WITH consente di definire delle tabelle temporanee che non
diventano parte dello schema ma rappresentano solo dichiarazioni di relazioni
da utilizzare nel contesto dell’interrogazione associata a WITH
WITH
R1 AS <definizione di R1>,
...
Rn AS <definizione di Rn>,
<interrogazione che coinvolge R1, …, Rn>





ogni definizione può essere ricorsiva e mutuamente ricorsiva
ogni relazione coinvolta in una ricorsione deve essere preceduta dalla parola
chiave RECURSIVE
la definizione per la relazione Ri consiste in
– parola chiave opzionale RECURSIVE
– il nome della relazione che si sta definendo (seguita da AS)
– interrogazione che definisce Ri e può fare riferimento a R1 ,…, Ri-1
l’interrogazione finale che può far riferimento a tutte le relazioni definire
in precedenza
la ricorsione deve essere lineare
–
nella definizione di una relazione R, R può comparire una sola volta
Esempi

Esempio di ricorsione lineare (nota RECURSIVE rispetto a DB2)
WITH RECURSIVE CAPO (NOME, NOMECAPO) AS
(
SELECT NOME, NOMECAPO
FROM IMPIEGATO
UNION
SELECT CAPO.NOME, IMPIEGATO.NOMECAPO
FROM CAPO, IMPIEGATO
WHERE CAPO.NOMECAPO = IMPIEGATO.NOME )
SELECT * FROM CAPO;

Esempio di ricorsione non lineare : non accettata dallo standard
WITH RECURSIVE CAPO (NOME, NOMECAPO) AS
(
SELECT NOME, NOMECAPO
FROM IMPIEGATO
UNION
SELECT R1.NOME, R2.NOMECAPO
FROM CAPO R1, CAPO R2 R1.NOMECAPO = R2.NOME )
SELECT * FROM CAPO;

La forma della query deriva dalla semantica, ovvero dal modo con la quale
CAPO viene calcolata
SQL-99 - semantica della ricorsione


La semantica delle interrogazioni ricorsive è definita mediante la
nozione di punto fisso (più precisamente minimo punto fisso)
Se R è Binaria (es. R(A,B)) si parla anche di chiusura transitiva R+ :
è la più piccola (rispetto alla inclusione) relazione tale che
1.
2.

si costruisce una sequenza Ri di relazioni tali che:
–
–
–

Contiene R+
Se (x,y) e (y,z) sono in R+ allora anche (x,z) è in R+
R0 è la relazione vuota
Ri, 1  i, viene ottenuta applicando la definizione della relazione a Ri-1
quando, per un certo i, si ha che Ri = Ri-1 ci si ferma e tale relazione è il
minimo punto fisso e costituisce il risultato dell'interrogazione ricorsiva
Esempio: CAPO è la chiusura transitiva di IMPIEGATO
SQL-99 - semantica della ricorsione


La semantica delle interrogazioni ricorsive è definita mediante la
nozione di punto fisso (più precisamente minimo punto fisso)
si costruisce una sequenza Ri di relazioni tali che:
–
–
–

Se R è Binaria si parla anche di chiusura transitiva R+ : è la più
piccola (rispetto alla inclusione) relazione tale che
1.
2.

R0 è la relazione vuota
Ri, 1  i, viene ottenuta applicando la definizione della relazione a Ri-1
quando, per un certo i, si ha che Ri = Ri-1 ci si ferma e tale relazione è il
minimo punto fisso e costituisce il risultato dell'interrogazione ricorsiva
Contiene R+
Se (x,y) e (y,z) sono in R+ allora anche (x,z) è R+
Esempio: CAPO è la chiusura transitiva di IMPIEGATO
Esempio
Determinare i cammini di un grafo dati gli archi
WITH
RECURSIVE Cammino(da,a) AS
(SELECT da,a FROM Arco)
UNION
(SELECT R1.da, R2.a
FROM Arco AS R1, Cammino AS R2
WHERE R1.a = R2.da);
SELECT * FROM Cammino;

Esempio (continua)



Arco
Cammino0 = ;
Cammino1 =
Esempio - semantica

Cammino2 = Cammino1 

Cammino3 = Cammino2 

Cammino4 = Cammino3 punto fisso e risultato