1

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.

2

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

3

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

4

Gerarchie Ricorsive: eventi ed aggregazione Nella tabella 5.32 si riportano gli eventi secondari al

secondo livello di aggregazione:

5

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

6

Principale limitazione di AR e SQL-92: interrogazioni ricorsive

IMPIEGATO

NOME NOMECAPORossi Verdi

Neri Verdi

Verdi DeSio

Tucci DeSio

DeLuca DeSio

DeSio Lazio

Lazio

selezionare tutti i capi di “Rossi”

Query

NOMECAPOVerdi

DeSio

Lazio

Questa interrogazione è riconducibile ad un caso di chiusura transitiva di una relazione binaria

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;

In SQL-3 (SQL-1999) si possono esprimere interrogazioni ricorsive

In DB2

SQL-SERVER 2005e ACCESSnon accettano interrogazioniricorsive

7

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

8

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

9

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

10

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– 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

11

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;

12

Esempio di calcolo del punto fisso Cammino0 = Arco(Da,a)

Cammino1 = Cammino0

Cammino2 = Cammino1

Cammino3 = Cammino2 punto fisso e risultato

SELECT R.da, R0.a

FROM Arco R, Cammino0 R0

WHERE R. a = R0.da

R=ArcoR0 = Cammino0

R.da, R0.a (R R.a = R0.daR0 )

in A.R.

13

Tabella di Navigazione Siccome le viste ricorsive sono difficili da esprimere ed non formulabili in SQL-92 e quindi

in molti DBMS commerciali, si pre-calcola 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

14

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)

15

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 …