Algoritmi di matching tra schemi Algoritmi di matching tra schemi XML per la riscrittura di queryXML per la riscrittura di query

(1)

Algoritmi di matching tra schemi Algoritmi di matching tra schemi

XML per la riscrittura di query XML per la riscrittura di query

Tesi di laurea di:

Milena Cevolani Milena Cevolani UNIVERSITÀ

UNIVERSITÀ DEGLI DEGLI STUDI DI MODENA E REGGIO EMILIA STUDI DI MODENA E REGGIO EMILIA Facoltà di Ingegneria – Sede di Modena

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

Relatore:

Prof. Paolo Tiberio Prof. Paolo Tiberio

Correlatore:

Dott.sa Federica Mandreoli

(2)

Sommario

• Il progetto ECD e le biblioteche Il progetto ECD e le biblioteche digitali XML

digitali XML

• Il problema della riscrittura delle query Il problema della riscrittura delle query

• Il matching fra schemi XML Il matching fra schemi XML

• Prove sperimentali Prove sperimentali

(3)

Biblioteche Digitali XML

• Il progetto ECD si concentra sullo sviluppo di tecnologie e strumenti per offrire contenuti arricchiti

• Uno dei mezzi di distribuzione dei contenuti arricchiti è dato dalle biblioteche digitali

• Una BD è una raccolta gestita di informazioni, con servizi associati, in cui l’informazione è memorizzata in formato digitale e accessibile su una rete

• Nelle BD XML lo standard scelto per la rappresentazione dei documenti è il linguaggio XML

• Nelle BD XML i dati sono semistrutturati

(4)

Biblioteche Digitali XML

DATI SEMISTRUTTURATI

Pregi:

•Flessibilità

•Facilità d’uso

Difetti:

•Grandi quantità di informazioni eterogenee

•Difficoltà a reperire le informazioni nel repository della BD

Necessità di uso di metadati che descrivano la struttura dei documenti XML

Uso del linguaggio XML Schema

Necessità di eseguire

interrogazioni

approssimate

(5)

La riscrittura delle query

• Definire un linguaggio di interrogazione (XQuery)

• Riscrivere ogni query posta dall’utente

• in modo automatico

• per ogni documento della BD utile a soddisfare la richiesta dell’utente

Un possibile approccio Un possibile approccio

Sfruttare le informazioni strutturali fornite dagli schemi XML

Per interrogare i documenti XML nell’archivio

di una BD bisogna:

(6)

La riscrittura delle query

Schema A Schema B

for $x in /cdstore

where $x/cd/singer = ELISA and $x/cd/song/title = gift return $x/name

“i nomi di negozi che vendono cd di ‘Elisa’ e che contengano

canzoni con ‘gift’ nel titolo “ 

? ?

name

cdstore

cdtitle cd

vocalist address

state

city tracklist

passage title street

musicstore

compackDisk storage

stock signboard

country colorsign namesign

songlist

songtitle singer track

albumTitle location

town

(7)

La riscrittura della query

• Uso di ontologie per “annotare” i termini degli schemi XML

• Una ontologia può essere vista come un insieme di concetti in grado di definire in modo univoco una determinata realtà di interesse

• Annotazione: codice in Wordnet del significato espresso dal termine

• Uso di un algoritmo di matching

• Prende in input coppie di schemi XML “annotati”

• Restituisce una mappatura con i punteggi di similarità fra le coppie di termini appartenenti ai due schemi

Riscrittura automatica di una query: Da dove partire?

(8)

Algoritmo per il matching fra schemi XML

• Trasformazione degli schemi annotati in grafi etichettati diretti

G

A

=XMLDOMGraph(schema A) G

_B

=XMLDOMGraph(schema B)

• Creazione della mappatura iniziale

initialMap=StringMatcher(G

_A

,G

_B

)

• Creazione di un multimapping tramite un calcolo di fixpoint

multimapping=match(G

_A

,G

_B

,initialMap)

• Filtraggio del multimapping

result=Filter(multimapping)

(9)

Trasformazione degli schemi XML

Trasformazione degli schemi XML annotati in grafi RDF

SCHEMA B

<schema>

<element name="cdstore@3662068" type="cdstoreType@3662068"/>

<complexType name="cdstoreType@3662068">

<element name="name@5332759" type="string@5863361"/>

<element name="address@6991355" type="addressType@6991355"/>

</complexType>

</complexType>

</complexType>

</complexType>

</complexType>

</schema>

schema

b0

b1

b3 b2 complexType

element cdstore

cdstoreType

string name

tag

tag tag

child

child child

type

name

Gli archi sono identificati da delle triple (s,p,o)

Uso dell’etichetta child per identificare le relazioni parent-child

bi  [tag:name]

(10)

Creazione della mappatura iniziale

Dai grafi G

_A

e G

_B

si ricava il grafo di connettività a coppie (PCG):

G _A G _B Grafo di connettività a coppie (a2, child ,a9)  G

_A

e (b0, child, b1)  G

_B

 ((a2,b0), child, (a9,b1))  PCG

schema

b0

b1

b3 b2 complexType

element cdstore

cdstoreType

string name

tag

tag tag

child

child child

type

name

storageType, string

element,element

storage,name a9,b3

storage,cdstoreType

a9,b2 a2,b0 a9,b1

element,complexType

storage,cdstore

storageType,cdstoreType

a2,b1 complexType,element

musicstoreType,cdstore tag

tag name

name

name name

name

type type

type

child child

schema

element complexType

a2 a1

a0

a9

musicstore

storage storageType

musicstoreType tag

tag

tag tag child

child

child name

name

name type

type

(11)

Creazione della mappatura iniziale

Per ogni coppia di mappe (a,b)  PCG, si calcola il valore iniziale di similarità σ

⁰

come segue:

•Coppie (risorsa,risorsa) e (risorsa,letterale): σ

⁰

= minSim

•Coppie (letterale,letterale):

Uso del modello Vector Space Generalizzato

Uso delle gerarchie di ipernimi di WordNet

livello 8 =>singer, vocalist, vocalizer, vocaliser livello 7 =>musician, instrumentalist, player livello 6 =>performer, performing artist livello 5 =>entertainer

livello 4 =>person, individual, someone, somebody, mortal, human, soul

livello 3 =>organism, being

livello 2 =>living thing, animate thing livello 1 =>object, physical object livello 0 =>entity, physical thing

livello 3 =>causal agent, cause, causal agency livello 2 =>entity, physical thing

livello 8 =>singer,vocalist, vocalizer, vocaliser livello 7 =>musician, instrumentalist, player livello 6 =>performer, performing artist livello 5 =>entertainer

livello 4 =>person, individual, someone, somebody, mortal, human, soul

livello 3 =>organism, being

livello 2 =>living thing, animate thing livello 1 =>object, physical object livello 0 =>entity, physical thing

livello 3 =>causal agent, cause, causal agency livello 2 =>entity, physical thing

0 . 8 1 8 2 8 )

vocalist (

depth )

ger (sin

depth depth ( LCA (sin ger , vocalist )) ) 2

vocalist ,

ger 0 (sin

    

 



(12)

Creazione della mappatura iniziale

Nodi in Schema A Nodi in Schema B 

⁰

musicstore cdstore 1.0

songlist tracklist 1.0

namesign name 1.0

track passage 0.5

songtitle title 1.0

compackDisk cd 1.0

singer vocalist 1.0

(13)

Creazione del multimapping

Aggiunta dei coefficienti di propagazione w w sugli archi con la formula inverse product:

Creazione del grafo di propagazione della similarità :

Aggiunta di un arco, con direzione opposta

storageType,string

element, element

a9,b1 a2,b0

a9,b2

storageType,cdstoreType storage, cdstore

element, complexType storage, cdstoreType

a2,b1 musicstoreType, cdstore complexType, element

1.0

1.0 1.0

1.0

0.005 0.005

0.143

1.0 0.005

1.0 1.0

0.013 1.0

0.01 1.0

1.0 1.0

0.005

) B , q , y } ( r ,l card { )

A , p , x } ( r ,l

card { 1



(14)

Creazione del multimapping

storageType,string

element, element

a9,b1 a2,b0

a9,b2

storageType,cdstoreType storage, cdstore

element, complexType storage, cdstoreType

1.0

1.0 1.0

1.0

0.005 0.005

0.143

1.0 0.005

1.0 1.0

0.013 1.0

0.01 1.0

1.0 1.0

0.005

Formula di fixpoint: σ

^{n + 1}

= normalize (σ

⁰

+ σ

ⁿ

+ φ(σ

⁰

+ σ

ⁿ

))









 

 n 1 ( a 2 , b 1 ) 0 ( a 2 , b 1 ) n ( a 2 , b 1 )















 



 





0 ( complexTyp e , element ) n ( complexTyp e , element ) 0 . 001

1.0 1.0

0.01 1.0

 ^









_



 





0 ( musicstore Type , cdstore ) n ( musicstore Type , cdstore ) 1 . 0





 



 





 0 ( complexTyp e , element )   n ( complexTyp e , element )  1 . 0 

 ^









_



 





0 ( musicstore Type , cdstore ) n ( musicstore Type , cdstore ) 1 . 0

(15)

Convergenza del calcolo di fixpoint

• La formula di fixpoint corrisponde al ^calcolo

dei cammini casuali sulle catene di Markov

• L’iterazione continua fino a che ( ⁿ , ⁿ⁺¹ ) < 

• Il calcolo converge se il grafo di propagazione è strettamente connesso

• Uso del dampening: si aggiunge σ ⁰ al calcolo di φ

con σ ⁰ (a,b) > 0

(16)

Filtraggio dei risultati

Filtro

Vincoli di typing

•[element:name]

•[complexType:name]

Vincoli di cardinalità

•[0.n]-[0,n]

Multimapping

mappatura finale

(similarità assoluta)

Problema di assegnamento

•Similarità cumulativa

•[0,1]-[0,1]

Problema del matrimonio stabile

Valore di soglia

0.4

  

 

Mi y ,

x x,y

(17)

Prove sperimentali

Schema B Schema A

musicstore

compackDisk storage

stock signboard

songlist

albumTitle location

town

cdstore

cdtitle cd

vocalist address

state

city tracklist

Nodi in A Nodi in B 

⁰



[element:musicstore] [complexType:cdstoreType] 0.001 1.0 [complexType:compackDiskType] [element:cd] 0.001 1.0 [complexType:songlistType] [element:tracklist] 0.001 1.0 [element:compackDisk] [complexType:cdType] 0.001 0.779

[element:compackDisk] [element:cd] 0.001 0.755

[complexType:musicstoreType] [element:cdstore] 0.001 0.755

[element:namesign] [element:name] 0.001 0.755

[element:musicstore] [element:cdstore] 0.001 0.637

[element:songlist] [element:tracklist] 0.001 0.506

[element:songlist] [complexType:tracklistType] 0.001 0.506

[element:track] [complexType:passageType] 0.001 0.504

[element:track] [element:passage] 0.001 0.504

(18)

Prove sperimentali

Schema A

musicstore

compackDisk storage

stock signboard

songlist

albumTitle location

town

cdstore

cdtitle cd

vocalist address

state

city tracklist

Schema B Schema B1

cdstore

cdtitle cd

vocalist address

state

city tracklist

(19)

Prove sperimentali

Schema A

cdstore

cdtitle cd

vocalist address

state

city tracklist

musicstore

compackDisk storage

stock signboard

songlist

albumTitle location

town

Schema B Schema B2

cdstore

cdtitle cd

vocalist address

state

city tracklist

tradecenter middletown

(20)

Prove sperimentali

Schema A

musicstore

compackDisk storage

stock signboard

songlist

albumTitle location

town

cdstore

cdtitle cd

vocalist address

state

city tracklist

catalog

category code

music

cdtitle cd

vocalist

tracklist passage

title

Schema B1

Schema B3

(21)

Parametri di modulazione

Approccio p = q p  q

Inverse product 0

Inverse average 0

Inverse total

product 0

Inverse total

average 0

Combined inverse

average 0

Equal 1.0 0

) B , q , y } ( r ,l card { )

A , p , x } ( r ,l

card { 1



) B , q , y } ( r ,l card { )

A , p , x } ( r ,l

card { 2



) B , q } ( r ,l card { )

A , p } ( r ,l

card { 1



) B , q } ( r ,l card { )

A , p } ( r ,l

card { 2



)) B , q , y } ( r, l card { )

A , p , x } ( r, l card { ( )) B , q } ( r, l card { )

A , p } ( r, l card {

( 4







(22)

Parametri di modulazione

SIGLA FORMULE DI FIXPOINT

FTF σ

^{n + 1}

= normalize (φ(σ

⁰

+ σ

ⁿ

)) TFF σ

^{n + 1}

= normalize (σ

⁰

+ φ(σ

ⁿ

)) FFT σ

^{n + 1}

= normalize (σ

ⁿ

+ φ(σ

ⁿ

))

TTF σ

^{n + 1}

= normalize (σ

⁰

+ φ(σ

⁰

+ σ

ⁿ

)) FTT σ

^{n + 1}

= normalize (σ

ⁿ

+ φ(σ

⁰

+ σ

ⁿ

)) TFT σ

^{n + 1}

= normalize (σ

⁰

+ σ

ⁿ

+ φ(σ

ⁿ

))

TTT σ

^{n + 1}

= normalize (σ

⁰

+ σ

ⁿ

+ φ(σ

⁰

+ σ

ⁿ

))

(23)

Conclusioni

• E’ stato implementato un metodo per effettuare in modo automatico il matching fra schemi XML

• Il metodo proposto si basa sull’utilizzo di

ontologie e di informazioni strutturali fornite dagli schemi XML

• Il valore iniziale di similarità trovato è stato

“affinato” tramite un calcolo iterativo di fixpoint

• Per limitare le mappature trovate, si sono usati dei

filtri

(24)

Sviluppi Futuri

• Il software progettato potrà, in futuro, essere sfruttato in un modulo di gestione delle query

• Un criterio per la riscrittura delle query potrebbe fare uso dei valori σ trovati e combinare insieme :

• Il problema del matrimonio stabile: implica la determinazione di un matching stabile

• La similarità relativa: rendere significativo il verso di “attraversamento”

degli schemi

Query Schema

cdstore

song singer

cd name

title



town location

musicstore

compackDisk storage

stock signboard

songlist

albumTitle