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

Tesi di laurea di:Tesi di laurea di:

Milena CevolaniMilena Cevolani

UNIVERSITÀUNIVERSITÀ DEGLIDEGLI STUDI DI MODENA E REGGIO EMILIASTUDI 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:Relatore:

Prof. Paolo TiberioProf. Paolo Tiberio

Correlatore:Correlatore:

Dott.sa Federica MandreoliDott.sa Federica Mandreoli

Sommario

• Il progetto ECD e le biblioteche Il progetto ECD e le biblioteche

digitali XMLdigitali XML

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

• Il matching fra schemi XML Il matching fra schemi XML

• Prove sperimentaliProve sperimentali

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

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 metadatiche descrivano la strutturadei documenti XML

Uso del linguaggioXML Schema

Necessità di eseguireinterrogazioni approssimate

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 approccioUn possibile approccio

Sfruttare le informazioni strutturali fornite dagli schemi XML

Per interrogare i documenti XML nell’archivio di una BD bisogna:

La riscrittura delle query

Schema A Schema B

for $x in /cdstorewhere $x/cd/singer = ELISAand $x/cd/song/title = giftreturn $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

statecity tracklist

passage

title

street

musicstore

compackDisk

storage

stock

signboard

country namesigncolorsign

songlist

songtitle singer

track

albumTitle

location

town

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?

Algoritmo per il matching fra schemi XML

• Trasformazione degli schemi annotati in grafi etichettati diretti

GA=XMLDOMGraph(schema A)

GB=XMLDOMGraph(schema B)

• Creazione della mappatura inizialeinitialMap=StringMatcher(GA,GB)

• Creazione di un multimapping tramite un calcolo di fixpoint

multimapping=match(GA,GB,initialMap)

• Filtraggio del multimapping

result=Filter(multimapping)

Trasformazione degli schemi XMLTrasformazione 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"/>

<element name="cd@2679407" type="cdType@2679407"/>

</complexType>

<complexType name="addressType@6991355">

<element name="city@7017487" type="string@5863361"/>

<element name="street@3777764" type="string@5863361"/>

<element name="state@6772345" type="string@5863361"/>

</complexType>

<complexType name="cdType@2679407">

<element name="vocalist@8680915" type="string@5863361"/>

<element name="cdtitle@5337484" type="string@5863361"/>

<element name="tracklist@5429385" type="tracklistType@5429385"/>

</complexType>

<complexType name="tracklistType@5429385">

<element name="passage@5886415" type="passageType@5886415"/>

</complexType>

<complexType name="passageType@5886415">

<element name="title@5337484" type="string@5863361"/>

</complexType>

</schema>

schema

b0

b1

b3

b2

complexType

element

cdstore

cdstoreType

string name

tag

tag

tag

tag

child

childchild

type

type

name

name

name

Gli archi sono identificati da delle triple (s,p,o)Uso dell’etichetta child per identificare le relazioni parent-child

bi [tag:name]

Creazione della mappatura inizialeDai grafi GA e GB si ricava il grafo di connettività a coppie (PCG):

GA GBGrafo di connettività a coppie

(a2, child ,a9) GA e (b0, child, b1) GB ((a2,b0), child, (a9,b1)) PCG

schema

b0

b1

b3

b2

complexType

element

cdstore

cdstoreType

string name

tag

tag

tag

tag

child

childchild

type

type

name

name

storageType, string

element,elementstorage,name a9,b3

storage,cdstoreType

a9,b2 a9,b1a2,b0

element,complexType

storage,cdstore

storageType,cdstoreType

a2,b1

complexType,element

musicstoreType,cdstoretag

tag

name

name

name

name

name

type

type

type

childchild

schema

element

complexType

a2a1

a0

a9

musicstore

storage storageType

musicstoreType

tag

tag

tag

tagchild

child

child

name

name

nametype

type

Creazione della mappatura inizialePer ogni coppia di mappe (a,b) PCG, si calcola il valore iniziale di similarità σ0 come segue:•Coppie (risorsa,risorsa) e (risorsa,letterale): σ0 = minSim•Coppie (letterale,letterale):

Uso del modello Vector Space GeneralizzatoUso 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.18882

)vocalist(depth)ger(sindepth))vocalist,ger(sinLCA(depth2)vocalist,ger(sin0

Creazione della mappatura iniziale

Nodi in Schema A Nodi in Schema B 0

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

Creazione del multimapping

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

Creazione del grafo di propagazione della similarità :

Aggiunta di un arco, con direzione opposta

storageType,string

element, elementstorage,name a9,b3

a9,b1a2,b0a9,b2

storageType,cdstoreType

storage, cdstore

element, complexType

storage, cdstoreType

a2,b1 musicstoreType, cdstorecomplexType, element

1.0

1.0 1.0

1.01.0

1.0 1.0

1.0

1.0

1.0

0.005 0.005

0.143

1.0 0.005

1.01.0

0.013

1.0

0.01 1.0

1.01.0

0.005

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

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

card1

Creazione del multimapping

storageType,string

element, elementstorage,name a9,b3

a9,b1a2,b0a9,b2

storageType,cdstoreType

storage, cdstore

element, complexType

storage, cdstoreType

a2,b1 musicstoreType, cdstorecomplexType, element

1.0

1.0 1.0

1.01.0

1.0 1.0

1.0

1.0

1.0

0.005 0.005

0.143

1.0 0.005

1.01.0

0.013

1.0

0.01 1.0

1.01.0

0.005

Formula di fixpoint: σn + 1 = normalize (σ0 + σn + φ(σ0 + σn))

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

001.0)element,ecomplexTyp(n)element,ecomplexTyp(0

a2,b1 musicstoreType, cdstorecomplexType, element1.0 1.0

0.01 1.0

0.1)cdstore,Typemusicstore(n)cdstore,Typemusicstore(0

0.1)element,ecomplexTyp(n)element,ecomplexTyp(0

0.1)cdstore,Typemusicstore(n)cdstore,Typemusicstore(0

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 (n,n+1) <

• Il calcolo converge se il grafo di propagazione è

strettamente connesso

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

con σ0(a,b) > 0

Filtraggio dei risultati

FiltroVincoli 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 delmatrimonio stabile

Valore di soglia0.4

iMy,x

y,x

Prove sperimentaliSchema BSchema A

musicstore

compackDisk

storage

stock

signboard

country namesigncolorsign

songlist

songtitle singer

track

albumTitle

location

town

cdstore

cdtitle

cd

vocalist

address

statecity tracklist

passage

title

streetNodi in A Nodi in B 0

[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

Prove sperimentali

Schema A

musicstore

compackDisk

storage

stock

signboard

country namesigncolorsign

songlist

songtitle singer

track

albumTitle

location

town

cdstore

cdtitle

cd

vocalist

address

statecity tracklist

passage

title

street

Schema BSchema B1

cdstore

cdtitle

cd

vocalist

address

statecity tracklist

passage

title

street

Prove sperimentali

Schema A

cdstore

cdtitle

cd

vocalist

address

statecity tracklist

passage

title

street

musicstore

compackDisk

storage

stock

signboard

country namesigncolorsign

songlist

songtitle singer

track

albumTitle

location

town

Schema BSchema B2

cdstore

cdtitle

cd

vocalist

address

statecity tracklist

passage

title

street

tradecenter

middletown

Prove sperimentali

Schema A

musicstore

compackDisk

storage

stock

signboard

country namesigncolorsign

songlist

songtitle singer

track

albumTitle

location

town

cdstore

cdtitle

cd

vocalist

address

statecity tracklist

passage

title

street

catalog

categorycode

music

cdtitle

cd

vocalist

tracklist

passage

title

Schema B1Schema B3

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{

card1

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

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

card2

)B,q(}r,l{

card)A,p(}r,l{

card1

)B,q(}r,l{

card)A,p(}r,l{

card2

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

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

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

card)A,p(}r,l{

card(4

Parametri di modulazione

SIGLA FORMULE DI FIXPOINT

FTF σn + 1 = normalize (φ(σ0 + σn))

TFF σn + 1 = normalize (σ0 + φ(σn))

FFT σn + 1 = normalize (σn + φ(σn))

TTF σn + 1 = normalize (σ0 + φ(σ0 + σn))

FTT σn + 1 = normalize (σn + φ(σ0 + σn))

TFT σn + 1 = normalize (σ0 + σn + φ(σn))

TTT σn + 1 = normalize (σ0 + σn + φ(σ0 + σn))

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

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

songsinger

cdname

title

town

location

musicstore

compackDisk

storage

stock

signboard

country namesigncolorsign

songlist

songtitle singer

track

albumTitle