Tecniche di ranking per l’interrogazione approssimata di dati XML

(1)

Cristian Colli

Università degli Studi di Modena e Reggio Emilia Università degli Studi di Modena e Reggio Emilia

Facoltà di Ingegneria – Corso di Laurea in Ingegneria Informatica Facoltà di Ingegneria – Corso di Laurea in Ingegneria Informatica

Anno Accademico 2001/2002 Anno Accademico 2001/2002

Relatore:

Prof. Paolo Tiberio Prof. Paolo Tiberio Correlatore:

Correlatore:

Dott. Federica Mandreoli Dott. Federica Mandreoli Ing. Riccardo Martoglia Ing. Riccardo Martoglia

Controrelatore Controrelatore:

Prof. Sonia BergamaschiProf. Sonia Bergamaschi

Tecniche di ranking per l’interrogazione

approssimata di dati XML

(2)

Interrogazione approssimata XML

<?xml version="1.0" encoding="UTF-8"?>

<?xml-stylesheet type="text/xsl" href="XMLTree.xsl"?>

<dblp>

D. Shasha

</corresponding author>

<title>

Approximate tree matching in the presence of…

</title>

<journal>Journal of algorithms</journal>

<date>

</date>

</article>

</dblp>

Documento XML

D. Shasha </author>

K. Zhang </author>

</article>

Interrogazione XML

year author author article

1994 D.shasha K. Zhang

 Necessità di criteri per la selezione delle risposte approssimate

 Non sempre esistono soluzioni che rispondono a pieno all’interrogazione

 Interrogando l’albero XML accediamo a dati di cui non conosciamo lo schema

author author date article

1994 K.

Zang D.

Shasha

year journal

J.T.L.

Wang Corr.

author

key title

dblp

Journal of algorithms

(3)

Obiettivi della tesi

Metrica di similarità tra alberi Metrica di similarità tra alberi

Flessibile (fornendo all’utente la possibilità di esprimere le proprieFlessibile (fornendo all’utente la possibilità di esprimere le proprie

preferenze attraverso appositi parametri)preferenze attraverso appositi parametri)

Rigorosa (Rigorosa (quantificando il valore di dissimilianza tra alberi attraversoquantificando il valore di dissimilianza tra alberi attraverso

il calcolo della tree edit distance unorderedil calcolo della tree edit distance unordered))

Efficace (Efficace (garantendo di produrre risultati utili e di qualità)garantendo di produrre risultati utili e di qualità)

Algoritmi per la risoluzione di interrogazioni Algoritmi per la risoluzione di interrogazioni

Completi (fornendo all’utente tutti e solo i risultati effettivamente utiliCompleti (fornendo all’utente tutti e solo i risultati effettivamente utili))

Efficienti (Efficienti (garantendo prestazioni soddisfacenti attraverso l’utilizzogarantendo prestazioni soddisfacenti attraverso l’utilizzo

di filtri costruiti di filtri costruiti ad hoc)ad hoc)

(4)

Parametri

1994 K. Zhang D. Shasha

L’utente deve poter decidere come penalizzare le soluzioni approssimate trovate

1

0 1

1

1 -

 Costo locale per ogni rilassamento sui vincoli di parentela padre figlio nell’albero dati

2

4

2 2

2 2 2

 Costo locale per ogni nodo query non trovato nell’albero dati

Penalizzazioni:

Albero query

Occorre specificare un limite alle soluzioni approssimate attraverso l’introduzione di un valore di soglia di dissimilarità che permetta di selezionare le soluzioni.

Soglia = 3

Parentela: Distanza massima che può esistere nell’albero dati tra due nodi legati nell’albero query, da una relazione padre-figlio

Parentela = 2

 Per ogni inconsistenza sul contenuto la metrica di dissimilarità e espressa dalla edit distance

(5)

Tree Edit Distance Unordered

Edit operation:

Inserimento

Cancellazione

Sostituzione

Necessità di misurare una distanza tra alberi (unordered) che sia una metrica e che permetta in seguito di selezionare solo le soluzioni per le quali la distanza è inferiore alla soglia

T1 R

E A

B C

D

T2 R

A B

C E

F

Tree edit distance = 2

Costo di cancellazione del nodo D

Inserimento del nodo F in T1(Costo di cancellazione nodo F in T2) Supponendo per ciascuna edit operation un costo unitario:

(6)

Algoritmo tree edit distance unordered

T

D

C F

A B

K(T)

D

C F

A

Costruiamo tutti i possibili sottoalberi

RK(T)

D

A_C F

Riduciamo l’albero affinchè contenga solo nodi Head

RK(T) 1 nodo RK(T) 3 nodi

RK(T) 5 nodi

RK(T)

Memorizziamo gli RK(T) secondo Il numero di Head che contengono Consideriamo un albero alla volta e per entrambi determiniamo tutti i possibili sotto alberi

(7)

Algoritmo per tree edit distance tra alberi unordered

C

A B

C

B A

RK 3 nodi

RK(T1) RK(T2)

D

C F

A B

RK 5 nodi

D

C H E G

Teorema:

Ogni confronto tra RK(T1) e RK(T2) nel quale Head(RK(T1))  Head(RK(T2)) ha distanza infinita.

Tabella HASH

 Nella tabella Hash il confronto a costo minore rappresenta la tree edit distance Dist = 0

Dist = 

(8)

Unordered Tree Edit Distance per Interrogazioni Approssimate

T1

D

C F

A B

T2

D

F C

B A

H E G

Tree Edit Distance: ottima metrica per esprimere la distanza tra alberi ma non adatta alla risoluzione di query

Occorre adattare la metrica al contesto delle interrogazioni:

Necessità di valutare la distanza tra l’albero query e le sotto parti dell’albero dati

per tutti nodi dell’albero dati: Costo_del = 0

Resta problema della complessità: NP-completo

Per un albero di m=18 nodi il numero di sottoalberi è limitato da 2^m–1=262143 La complessità è esponenziale al crescere del numero dei nodi degli alberi

(9)

Filtro per la ricerca delle parti

 Necessità di un filtro che limiti la complessità della funzione per il calcolo della Tree Edit Distance

T1

D

C F

A B

T2

D

F C

B A

H E G

 La complessità rimane esponenziale solo per quanto riguarda le dimensioni dell’albero query

Identificando i gruppi di nodi dell’albero dati che possono risolvere la query otteniamo degli alberi che contengono al più lo stesso numero di nodi dell’albero query.

(10)

Algoritmo Filtro

Nodo query BB: 7; 6; 7,2; 7,5; 7,6;

6,5; 2; 5; 6;

Nodo query CC: 7,2,4; 7,5,4; 7,6,4; 6,5,4;

7,5; 6,5; 7,4 Gruppi generati:

Nodo query AA: 7; 6

3, AA

1, BB 2, CC

2, GB

6, AB 3, GG

7, AA

1, GF 4, CC 5, BB

Albero

query Albero

dati Filtro basato sul contenuto:

per ogni nodo query si cercano i nodi dati simili

per ogni nodo query processato si generano tutti i gruppi di nodi che sono possibili soluzioni

7,2,4; 7,5,4; 7,6,4; 6,5,4;

Risultati del filtro:

Assunzioni per Tutti i nodi query:

Costo_del = 2 Ril_par = 1

Soglia = 3 Parentela = 2

(11)

Risultati del filtro

3, AA

1, BB 2, CC

2, GB

6, AB 3, GG

7, AA

1, GF 4, CC 5, BB

Il filtro individua i gruppi di nodi che possono rispondere alla interrogazione

Per i gruppi candidati che soddisfano la query, la distanza coincide con quella calcolata dal filtro

7,2,4 con distanza filtro 3 (reale 3) Risultati del filtro:

7,5,4 con distanza filtro 2 (reale 2)

6,5,4 con distanza filtro 1 (reale 1)

7,6,4 con distanza filtro 1 (reale infinito) Albero

query Albero

dati

(12)

Interrogazione approssimata XML

1994 D.shasha K. Zhang

author author date article

1994 K.

Zang D.

Shasha

year journal

J.T.L.

Wang Corr.

author

key title

dblp

Journal of algorithms

Riconsideriamo l’interrogazione iniziale per la quale l’utente ha specificato I seguenti parametri:

In dblp esiste una soluzione approssimata.

 Il filtro propone il gruppo di nodi evidenziati come candidato (distanza 3)

L’algoritmo calcola il relativo valore di dissimilianza con l’albero query mediante la funzione di tree edit distance:

2

2 2

4 2

2

1 -

1 1

1

1 0

Soglia = 3 Parentela = 2

Il candidato è soluzione con valore di dissimilianza = 3

(13)

Selettività filtro

Efficacia del filtro realizzato al variare del valore di soglia per una interrogazione contenente 6 nodi su di un albero composto da 22.

 la dimensione dell’insieme candidato prodotto dal filtro è vicina a quella delle soluzioni alla query

 Il filtro si adatta al valore dei parametri imposti dall’utente

I parametri della interrogazione sono:

Costo_del = 2 Ril_par = 2 Parentela = 2

La complessità dell’algoritmo, complessivamente viene ridotta nel caso peggiore da 2²²=4194304 a 65 x ( 2⁶ ) = 4160 con un fattore di riduzione pari a 1000.

0 1 3 4

12

29

0 1

5

11

32

65

0 10 20 30 40 50 60 70

0 1 2 3 4 5 6

Valore della soglia

Soluzioni trovate

sol effettive sol filtro

(14)

Scalabilità (1)

Prestazioni dell’algoritmo nel suo complesso al variare del numero di nodi presenti nella query.

Valore dei parametri:

Soglia = 3 Parentela = 2 Costo_del = 2 Ril_par = 1

 Il

tempo necessario per convertire il documento XML nella struttura ad albero

rappresenta il tempo maggiore e indica la scarsa efficienza di tale funzione.

 Il tempo richiesto per l’esecuzio dell’interrogazione rimane

limitato poiché aumentando il numero di nodi della query aumentano i criteri di selettività del filtro.

Albero dati 440 nodi

9 9 9 9 9

15

17

14

15

14

0 2 4 6 8 10 12 14 16 18

0 2 4 6 8 10 12

Nodi query

Tempo di esecuzione (sec)

t imm t tot

(15)

Scalabilità (2)

Occupazione memoria

39 39 39

40

41

38,5 39 39,5 40 40,5 41 41,5

0 2 4 6 8 10 12

Nodi query

Occupazione memoria (Mbyte)

 L’occupazione di memoria

presenta un andamento

di tipo esponenziale al crescere del numero di nodi della query

Valore dei parametri:

Soglia = 3 Parentela = 2 Costo_del = 2 Ril_par = 1

Prestazioni dell’algoritmo nel suo complesso al variare del numero di nodi presenti nella query.

(16)

Conclusioni

Obiettivi conseguiti:

Sviluppi futuri:

E’ stata definita una metrica di similarità tra alberi efficace basata sul concetto di Unordered Tree Edit Distance

Utilizzando questa metrica è stato definito e affrontato il problema di risoluzione di una query.

E’ stato definito un filtro in grado di ricercare le parti di un albero dati di grandi dimensioni simili all’albero query

E’ stato realizzato in Java un ambiente comune che riunisce queste funzionalità

Ricercare criteri per la costruzione dei soli sottoalberi utili

Potenziare gli algoritmi proposti per la realizzazione del filtro

Migliorare le prestazioni della funzione che converte il documento XML nella struttura ad albero utilizzata dall’algoritmo