Comments
Description
Transcript
Presentazione di PowerPoint - ISGroup
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)) 28 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 pq 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