UNIVERSITÀ DEGLI STUDI DI MODENA E REGGIO EMILIA
Facoltà di Ingegneria – Sede di Modena
Corso di Laurea in Ingegneria Informatica
Algoritmi di matching tra schemi
XML per la riscrittura di query
Relatore:
Prof. Paolo Tiberio
Correlatore:
Dott.sa Federica Mandreoli
Tesi di laurea di:
Milena Cevolani
Sommario
• Il progetto ECD e le biblioteche
digitali XML
• Il problema della riscrittura delle query
• Il matching fra schemi XML
• Prove 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
Difetti:
Pregi:
•Flessibilità
•Facilità d’uso
•Grandi quantità di informazioni
eterogenee
•Difficoltà a reperire le informazioni
nel repository della BD
Necessità di eseguire
interrogazioni
approssimate
Uso del linguaggio
XML Schema
Necessità di uso di metadati
che descrivano la struttura
dei documenti XML
La riscrittura delle query
Per interrogare i documenti XML nell’archivio
di una BD bisogna:
• 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
Sfruttare le informazioni strutturali fornite dagli
schemi XML
La riscrittura delle query
“i nomi di negozi che vendono
cd di ‘Elisa’ e che contengano
canzoni con ‘gift’ nel titolo “
for $x in /cdstore
where $x/cd/singer = ELISA
and $x/cd/song/title = gift
return $x/name
Schema A
Schema B
musicstore
location
signboard
town
colorsign
country

cdstore
storage
namesign
stock
name
address
city
street
cd
state
compackDisk
songlist
cdtitle
tracklist
passage
albumTitle
title
track
songtitle
vocalist
singer
?
?
La riscrittura della query
Riscrittura automatica di una query: Da dove partire?
• 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
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 iniziale
initialMap=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 XML
Trasformazione degli schemi XML annotati in grafi RDF
Gli archi sono identificati da delle triple (s,p,o)
Uso dell’etichetta child per identificare le relazioni parent-child
SCHEMA B
<schema>
bi  [tag:name]
schema
cdstore
<element name="cdstore@3662068" type="cdstoreType@3662068"/>
<complexType name="cdstoreType@3662068">
tag
<element name="name@5332759" type="string@5863361"/>
<element name="address@6991355" type="addressType@6991355"/>
<element name="cd@2679407" type="cdType@2679407"/>
complexType
</complexType>
child
<complexType name="addressType@6991355">
<element name="city@7017487" type="string@5863361"/>
b0
name
child
tag
<element name="street@3777764" type="string@5863361"/>
b1
<element name="state@6772345" type="string@5863361"/>
</complexType>
b2
<complexType name="cdType@2679407">
name
<element name="vocalist@8680915" type="string@5863361"/>
<element name="cdtitle@5337484" type="string@5863361"/>
child
<element name="tracklist@5429385" type="tracklistType@5429385"/>
type
cdstoreType
tag
</complexType>
b3
<complexType name="tracklistType@5429385">
<element name="passage@5886415" type="passageType@5886415"/>
</complexType>
<complexType name="passageType@5886415">
type
<element name="title@5337484" type="string@5863361"/>
tag
name
</complexType>
</schema>
string
name
element
Creazione della mappatura iniziale
Dai grafi GA e GB si ricava il grafo di connettività a coppie (PCG):
(a2, child ,a9)  GAe (b0, child, b1)  GB  ((a2,b0), child, (a9,b1))  PCG
GA
GB
schema
schema
Grafo di connettività a coppie
storageType, string
tag
complexType
tag
musicstore
type
cdstore
complexType
name
storage,name
a9,b3
tag
element,element
b0
name
a0
tag
tag
child
child
name
child
child
a9,b2
child
b2
b1
name
type
a1
child
tag
child
musicstoreType
tag
type
type
name
a9,b1
name
name
a2
child
a2,b0
storage,cdstore
storage,cdstoreType
type
cdstoreType
element,complexType
tag
a9
name
storage
tag
b3
element
type
complexType,element
type
name
storageType
string
storageType,cdstoreType
element
musicstoreType,cdstore
tag
name
name
a2,b1
Creazione della mappatura iniziale
Per 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 Generalizzato
Uso delle gerarchie di ipernimi di WordNet
livello 8 =>singer, vocalist, vocalizer, vocaliser
livello 8 =>singer,vocalist, vocalizer, vocaliser
livello 7 =>musician, instrumentalist, player
livello 7 =>musician, instrumentalist, player
livello 6 =>performer, performing artist
livello 6 =>performer, performing artist
livello 5
livello 5
=>entertainer
=>entertainer
livello 4
=>person, individual, someone, somebody,
mortal, human, soul
livello 4 =>person, individual, someone, somebody, mortal,
human, soul
livello 3
=>organism, being
livello 3
=>organism, being
livello 2
=>living thing, animate thing
livello 2
=>living thing, animate thing
livello 1
=>object, physical object
livello 1
=>object, physical object
livello 0
=>entity, physical thing
livello 0
=>entity, physical thing
livello 3
=>causal agent, cause, causal agency
livello 3
=>causal agent, cause, causal agency
livello 2
=>entity, physical thing
livello 2
=>entity, physical thing
0(sin ger, vocalist)  2 depth (LCA (sin ger, vocalist))  28 1.0
depth (sin ger)  depth (vocalist) 8  8
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
Creazione del grafo di propagazione della similarità :
Aggiunta di un arco, con direzione opposta
Aggiunta dei coefficienti di propagazione w sugli archi con la
1
formula inverse product:
card (x, p, A)  card (y, q, B)
{l,r}
{l,r}
storageType,string
0.143
1.0
1.0
storage,name
1.0
0.005
a9,b3
1.0
1.0
a9,b2
1.0
0.005
1.0
storage, cdstoreType
element, element
1.0
0.005
1.0
a2,b0
0.005
a9,b1
1.0
1.0
1.0
storage, cdstore
0.013
1.0
1.0
storageType,cdstoreType
element, complexType
1.0
complexType, element
0.01
1.0
a2,b1
1.0
musicstoreType, cdstore
Creazione del multimapping
Formula di fixpoint: σn + 1 = normalize (σ0 + σn + φ(σ0 + σn))
1.0
complexType, element
0.01
1.0
storageType,string
a2,b1
1.0
musicstoreType, cdstore
0.143
1.0
1.0
0.005
n

1
0
n
storage,name
element, element
 (a2, b1)   (a2, b1)   (a2, b1) 1.0
a9,b3
1.0
1.0
0.005
 0
n 1.0
)   0.001
1.0
  (complexType, element)   (complexType, element


a9,b2
0.005
a2,b0
0.005


1.0
a9,b1

1.0
1.0
 0
1.0 , cdstore)  n (musicstore Type, cdstore)  1.0 
1.0
  (musicstore Type
 1.0 1.0

storage, cdstore 
storage, cdstoreType
0.013
 0

storageType,cdstoreType
n (complexTyp
  (complexType, element) 
element,
complexType e, element)  1.0 



1.0
1.0
 0

  (musicstore Type
, cdstore
)  n (musicstoreType
1.0 
complexType,
element
a2,b1 , cdstore) musicstoreType,
cdstore


0.01
1.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
Problema del
matrimonio stabile
Multimapping
Problema di assegnamento
x, y 
•Similarità cumulativa x, y
M
•[0,1]-[0,1]
Vincoli di typing
•[element:name]
•[complexType:name]
Filtro
Valore di soglia
0.4
mappatura finale
(similarità assoluta)
i
Vincoli di cardinalità
•[0.n]-[0,n]
Prove sperimentali
Schema A
Schema B
cdstore
musicstore
location
signboard
address
storage
Nodi in A
town
country
colorsign
namesign
cd
0
Nodi in B
city
stock
street
state
vocalist
tracklist
[element:musicstore]
[complexType:cdstoreType]
compackDisk
[complexType:compackDiskType]
[element:cd]
0.001
[element:tracklist]
0.001
title
1.0
track
[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
songlist
albumTitle
[complexType:songlistType]
songtitle
singer
0.001

cdtitle
1.0
passage
1.0
Prove sperimentali
Schema A
Schema B1
B
musicstore
location
signboard
town
colorsign
country
cdstore
storage
namesign
stock
address
city
street
cd
state
vocalist
cdtitle
compackDisk
songlist
albumTitle
track
songtitle
singer
tracklist
passage
vocalist
title
Prove sperimentali
Schema A
Schema B
B2
musicstore
location
signboard
town
colorsign
country
middletown
cdstore
storage
namesign
stock
address
tradecenter
city
albumTitle
track
songtitle
street
cdstore state
address
compackDisk
songlist
cd
city
street
vocalist
cdtitle
cd
state
vocalist
tracklist
passage
cdtitle
title
tracklist
passage
singer
title
Prove sperimentali
Schema A
B1
Schema B3
musicstore
location
catalog
cdstore
signboard
storage
address
code
town
country
colorsign
namesign
stock
city
cd
category
street
state
music
cdtitle
compackDisk
tracklist
passage
cd
songlist
albumTitle
track
vocalist
cdtitle tracklist
passage
songtitle
singer
vocalist
title
title
Parametri di modulazione
Approccio
p=q
Combined inverse
average
1
card (x, p, A)  card (y, q, B)
{l,r}
{l,r}
2
card
(x, p, A)  card
(y, q, B)
{l,r}
{l,r}
1
card
(p, A)  card (q, B)
{l,r}
{l,r}
2
card
(p, A)  card
(q, B)
{l,r}
{l,r}
4
(card (p, A)  card (q, B)) (card (x, p, A)  card (y, q, B))
{l,r}
{l,r}
{l,r}
{l,r}
Equal
1.0
Inverse product
Inverse average
Inverse total
product
Inverse total
average
pq
0
0
0
0
0
0
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
cdstore
name
Schema
musicstore
location
cd
town
country
signboard
colorsign
storage
namesign
stock
compackDisk
singer
song
songlist
title
albumTitle
track
songtitle
singer