Gerarchie Ricorsive



Una gerarchia ricorsiva deriva dalla presenza di una ricorsione o
ciclo (un anello nel caso più semplice) nello schema operazionale.
Esempio di schema operazionale con anello:
Rappresentazione sullo Schema di Fatto di una Gerarchia ricorsiva
–
la costruzione dell’albero degli attributi non può essere realizzata con la
procedura automatica in quanto la ricorsione provoca un loop.
1
Gerarchie Ricorsive: eventi ed aggregazione


Nelle tabelle che seguono viene illustrata intuitivamente la semantica
dell’aggregazione in presenza di gerarchie ricorsive
La tabella 5.30 mostra gli eventi primari per ATTIVITÀ (non si
considera TipoAttività) e un’istanza della gerarchia ricorsiva
indicandone la relazione di subordinazione tra i vari impiegati
–
A livello di istanze di una gerarchia ricorsiva, l’aspetto caratteristico è la
lunghezza variabile delle relazioni padre-figlio tra i vari livelli
2
Gerarchie Ricorsive: eventi ed aggregazione

La tabella 5.31 mostra gli eventi secondari derivanti dall’aggregazione
ricorsiva degli eventi primari: al primo livello di aggregazione per
ciascun impiegato si riportano le ore complessivamente lavorate da
lui e dagli eventuali immediati subordinati
3
Gerarchie Ricorsive: eventi ed aggregazione

Nella tabella 5.32 si riportano gli eventi secondari al
secondo livello di aggregazione:
4
Gerarchie Ricorsive: Progettazione Logica

La soluzione di base del modello a stella comporterebbe
l’introduzione della dimension table :
IMPIEGATO(NOME,NOMECAPO)



A livello d’istanze, la situazione di tabella 5.30, si traduce in:
Con tale soluzione, per effettuare le aggregazioni viste nelle tabelle
5.31 e 5.32, devo saper calcolare tutti i discendenti (a tutti i livelli) di
un dato impiegato : tale calcolo comporta delle interrogazioni ricorsive
che non sono formulabili in SQL-92 (ACCESS, SQL-SERVER 2000,
…) ma in SQL-99 (ORACLE, SQL-SERVER 2005, …).
L’alternativa è quella di usare strumenti ad hoc:
–
–
Tabelle di Navigazione (Interrogazione ricorsive pre-calcolate)
Relazioni padre-figlio di Analysis Services
5
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;
)
SQL-SERVER 2005
e ACCESS
non accettano
interrogazioni
ricorsive
6
Interrogazioni Ricorsive in SQL

In SQL2 non è possibile definire interrogazioni che facciano uso della
ricorsione: una vista non può essere definita a partire dalla vista stessa
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)  Impiegato(Nome,NomeCapo)
Capo(Nome,NomeCapo) Impiegato(Nome,impiegato1),
Capo(impiegato1,NomeCapo)
–
Capo è una vista ricorsiva: nella sua definizione usa se stessa
–
7
SQL-99 - comando WITH

il comando WITH consente di definire delle tabelle temporanee che non
diventano parte dello schema ma rappresentano solo definizioni 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 definite
in precedenza
la ricorsione deve essere lineare
–
nella definizione di una relazione R, R può comparire una sola volta
8
Esempi

Esempio di ricorsione lineare
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
WHERE R1.NOMECAPO = R2.NOME )
SELECT * FROM CAPO;

(
La forma della query deriva dalla semantica, ovvero dal modo con la quale la
vista ricorsiva CAPO viene calcolata
9
SQL-99 - semantica della ricorsione


La semantica delle interrogazioni ricorsive è definita mediante la
nozione di punto fisso
Se R è una relazione Binaria R(A,B) si definisce chiusura transitiva
di R,denotata con R+, la più piccola (rispetto alla inclusione
insiemistica) relazione tale che
1.
2.

Contiene R
Se (x,y) e (y,z) sono in R+ allora anche (x,z) è in R+
R+ è il minimo punto fisso della funzione:
–
F(R) = R0  
R.A,R0.B
(R  R.B=
R0.A
R0 )
e si calcola come segue:
–
–
–


R0 = R
Ri = F(Ri-1)
quando, per un certo i, si ha che Ri = Ri-1 ci si ferma e tale relazione è il
minimo punto fisso della funzione F e costituisce R+
Esempio: CAPO è la chiusura transitiva di IMPIEGATO
Chiusura transitiva e riflessiva R* : contiene anche tutte le coppie
(x,x) con X in R
10
Esempio

Relazione Arco(Da,a)

Arco(Da,a) rappresenta un grafo; definiamo una vista Cammino(Da,a)
per rappresentare i cammini dal punto Da al punto a
La vista Cammino(Da,a) è la chiusura transitiva Relazione Arco(Da,a) e
si calcola in SQL-99 attraverso la seguente interrogazione ricorsiva

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;
11
Esempio di calcolo del punto fisso

R=Arco
R0 = Cammino0
Cammino0 = Arco(Da,a)
 R.da,

R0.a
(R  R.a
= R0.daR0
in A.R.
Cammino1 = Cammino0 
SELECT R.da, R0.a
FROM Arco R, Cammino0 R0
WHERE R. a = R0.da

Cammino2 = Cammino1 
Cammino3 = Cammino2
punto fisso e risultato
12
)
Tabella di Navigazione


Siccome le viste ricorsive sono difficili da esprimere ed non
formulabili in SQL-92 e quindi in molti DBMS commerciali, si precalcola il loro risultato e si inserisce in opportune tabelle
La Tabella di navigazione memorizza la chiusura transitiva e
riflessiva di una relazione binaria; in essa viene inoltre calcolato e
riportato anche il livello e l’indicazione di foglia
13
Uso della Tabella di Navigazione

Le informazioni presenti nella Tabella di Navigazione vengono usate in
fase di visualizzazione (ed interrogazione) del Fatto

Considerando Foglia come dimensione di ATTIVITA’
– Visualizzare tutte le ore lavorate indipendentemente da Foglia
– Visualizzare solo le ore lavorate dagli impiegati “foglia”
– Visualizzare solo le ore lavorate dagli impiegati “non foglia”

Considerando Livello come dimensione di ATTIVITA’
– Visualizzare tutte le ore lavorate indipendentemente da Livello :
per un impiegato ottengo tutte le ore lavorate da tutti i sui figli a
tutti i livelli
– Visualizzare tutte le ore lavorate, per un certo da Livello X: per un
impiegato ottengo tutte le ore lavorate da tutti i sui figli a livello X
– Visualizzare tutte le ore lavorate, fino ad un certo da Livello X: per
un impiegato ottengo tutte le ore lavorate da tutti i sui figli a livello
Y <= X (richiede una espressione MDX)
14
Calcolo della Tabella di Navigazione

Uso di un DBMS con SQL-99: SQL-SERVER 2005, ORACLE, …
–
Uso del nuovo sistema limitato solo per il calcolo di una interrogazione
ricorsiva

In un DBMS con SQL-92 posso “simulare” il calcolo dell’interrogazione
ricorsiva sulla base dell’algoritmo di calcolo del minimo punto fisso
discusso intuitivamente in precedenza

Un esempio di tale simulazione e’ sul sito web

Come gestire il “flusso delle operazioni” (ad esempio, come decidere
quando fermare il calcolo perche’ e’ stato raggiunto il punto fisso) ?
–
–
Stored procedures (vedi insegnamento di BAsi di Dati)
A mano …
15