Approssimazione semantica Approssimazione semantica per routing di interrogazioni per routing di interrogazioni

in un PDMSin un PDMS

Università degli Studi di Modena e Reggio EmiliaUniversità degli Studi di Modena e Reggio EmiliaFacoltà di Ingegneria – Corso di Laurea Specialistica in Ingegneria InformaticaFacoltà di Ingegneria – Corso di Laurea Specialistica in Ingegneria Informatica

Anno Accademico 2004/2005Anno Accademico 2004/2005

Relatore: Relatore:

Dott. Federica MandreoliDott. Federica Mandreoli

CorrelatoreCorrelatore:

Ing. Riccardo MartogliaIng. Riccardo Martoglia

Simona SassatelliSimona Sassatelli

Ambito di ricerca:Ambito di ricerca:Progetto nazionale WISDOM Progetto nazionale WISDOM

(Web Intelligent Search based on DOMain ontologies)(Web Intelligent Search based on DOMain ontologies)

definizione di tecniche e strumenti per la ricerca, la localizzazione e la definizione di tecniche e strumenti per la ricerca, la localizzazione e la fruizione personalizzata di risorse informative disponibili su Webfruizione personalizzata di risorse informative disponibili su Web

ObiettivoObiettivo

Peer Data Management System (PDMS)Peer Data Management System (PDMS)

Architettura di riferimentoArchitettura di riferimento

Ambito di indagine della tesi:Ambito di indagine della tesi:

Sviluppo di tecniche che permettono di operare sulla base diSviluppo di tecniche che permettono di operare sulla base di informazioni semanticheinformazioni semantiche

Processo di routing delle interrogazioniProcesso di routing delle interrogazioni

ObiettivoObiettivo

Peer Data Management System Peer Data Management System (PDMS)(PDMS)

Rete di Rete di peerpeer indipendenti ed autonomi indipendenti ed autonomi

Architettura decentralizzata e facilmente estensibile Architettura decentralizzata e facilmente estensibile (Peer-to-Peer)(Peer-to-Peer)

I peer decidono liberamente di condividere i propri datiI peer decidono liberamente di condividere i propri dati nessuno schema logico mediato globalenessuno schema logico mediato globale relazioni semantiche stabilite localmente tra i singoli peer (mapping)relazioni semantiche stabilite localmente tra i singoli peer (mapping)

I peer collaborano nel risolvere le interrogazioni poste I peer collaborano nel risolvere le interrogazioni poste dagli utentidagli utenti

query poste usando lo schema del peerquery poste usando lo schema del peer risposte provenienti da tutto il sistemarisposte provenienti da tutto il sistema

UW Stanford

DBLP

Roma Paris

CiteSeer

Vienna

Q

Q’

Q’Q’’

Q’’

Q’’

Q’’

Problematiche affrontate Problematiche affrontate nella tesinella tesi

Gestione dell’eterogeneità delle sorgenti Gestione dell’eterogeneità delle sorgenti coinvoltecoinvolte

Indici di Routing Semantici (SRI)Indici di Routing Semantici (SRI)

Gestione dell’ambiente P2PGestione dell’ambiente P2P

SimulazioneSimulazione

Gestione dell’eterogeneità Gestione dell’eterogeneità dei peerdei peer

Mapping semantici localiMapping semantici locali approccio basato sul concetto di approccio basato sul concetto di approssimazione semantica approssimazione semantica

Peer indipendentiPeer indipendenti eterogenei negli schemi adottati per eterogenei negli schemi adottati per

rappresentare i dati rappresentare i dati

Sistema Sistema XML SXML S33MARTMART sviluppato presso l’Università di Modena e sviluppato presso l’Università di Modena e

Reggio EmiliaReggio Emilia riscrittura di interrogazioni su insiemi di riscrittura di interrogazioni su insiemi di

documenti eterogeneidocumenti eterogenei

Schema ASchema A Schema BSchema Bcdstore

cdtitle

cd

vocalist

address

statecity tracklist

passage

title

street

musicstore

compactDisk

storage

stock

signboard

country namesigncolorsign

songlist

songtitle singer

track

albumTitle

location

town

name

XML SXML S33MARTMART

BBBB

CC

CC

AA

AA

DD

DD

……/stock/compactDisk/stock/compactDisk /cdstore/cd/cdstore/cdAA

/musicstore/location/musicstore/location /cdstore/address/cdstore/addressBB

……/track/songtitle/track/songtitle ……/passage/title/passage/titleCC

……/compactDisk/albumTitle/compactDisk/albumTitle ……/cd/cdtitle/cd/cdtitleDD

……

1. SCHEMA MATCHING1. SCHEMA MATCHING2. QUERY REWRITING2. QUERY REWRITINGFOR $x IN /musicstoreFOR $x IN /musicstoreWHERE $x//compactDisk/songlist/track/singer = "elisa"WHERE $x//compactDisk/songlist/track/singer = "elisa"AND $x//compactDisk/songlist/track/songtitle = "gift"AND $x//compactDisk/songlist/track/songtitle = "gift"RETURN $x/signboard/namesignRETURN $x/signboard/namesign

FOR $x IN /cdstoreFOR $x IN /cdstoreWHERE $x/cd/vocalist = "elisa"WHERE $x/cd/vocalist = "elisa"AND $x/cd/tracklist/passage/title = "gift"AND $x/cd/tracklist/passage/title = "gift"RETURN $x/nameRETURN $x/name

Limiti di XML SLimiti di XML S33MARTMART Progettato per un contesto centralizzato (digital library eterogenee)Progettato per un contesto centralizzato (digital library eterogenee)

per ogni coppia di schemi individua le migliori corrispondenze tra i per ogni coppia di schemi individua le migliori corrispondenze tra i concetti concetti

Ambiente distribuito P2PAmbiente distribuito P2P routing delle queryrouting delle query

A

D

C

B

E

F

G

H

IJ

Q Q

Q

Q

Q

Q

Q

Q

Q

Q

Non è sempre conveniente Non è sempre conveniente propagare una query verso propagare una query verso altri nodialtri nodi traffico di rete traffico di rete dati inutili per l’utentedati inutili per l’utente

Modifiche a XML SModifiche a XML S33MARTMART XML SXML S33MART processa gli schemi a coppieMART processa gli schemi a coppie

punteggi di mapping non utilizzabili per eseguire il routingpunteggi di mapping non utilizzabili per eseguire il routing

A

D

C

B

Q

??

Q

Reingegnerizzazione:Reingegnerizzazione: modifica della struttura modifica della struttura

concettuale da uno-a-uno concettuale da uno-a-uno a uno-a-moltia uno-a-molti

correzione del calcolo correzione del calcolo iterativo di fixpoint iterativo di fixpoint

adattamento adattamento dell’operazione di dell’operazione di normalizzazionenormalizzazione

Punteggi comparabiliPunteggi comparabili Calcolo dei punteggi efficiente Calcolo dei punteggi efficiente

e incrementalee incrementale

Problematiche affrontate Problematiche affrontate nella tesinella tesi

Gestione dell’eterogeneità delle sorgenti Gestione dell’eterogeneità delle sorgenti coinvoltecoinvolte

Indici di Routing Semantici (SRI)Indici di Routing Semantici (SRI)

Gestione dell’ambiente P2PGestione dell’ambiente P2P

SimulazioneSimulazione

Routing by mappingRouting by mapping

Necessità di considerare le Necessità di considerare le intere sottoretiintere sottoreti che hanno origine dai peer vicini. che hanno origine dai peer vicini.

InformazioniInformazioni

riassuntiveriassuntive

A

D

C

B

E

F

G

H

IJ

Non è possibile che Non è possibile che ogni peer calcoli i ogni peer calcoli i mapping con tutti gli mapping con tutti gli altri altri

query propagate solo ai peer con un elevato punteggio per i concetti richiesti

Q

Indici di Routing Semantici (SRI)Indici di Routing Semantici (SRI) Strutture dati locali ad ogni peerStrutture dati locali ad ogni peer

Informazioni riassuntiveInformazioni riassuntive di come ogni elemento dello schema di di come ogni elemento dello schema di un peer viene approssimato semanticamente nelle sottoreti che un peer viene approssimato semanticamente nelle sottoreti che hanno origine dai vicini hanno origine dai vicini

J

A

B

CISRISRIAA aa11 aa22 …… aa55

AA 0.80.8 0.90.9 …… 0.70.7

BB 0.60.6 0.00.0 …… 0.50.5

CC 0.40.4 0.50.5 …… 0.60.6

Esempio:Esempio:

Costruzione delle informazioni riassuntiveCostruzione delle informazioni riassuntiveCalcolate a partire dai punteggi di mapping determinati con XML SCalcolate a partire dai punteggi di mapping determinati con XML S33MART:MART:

1. AGGREGAZIONE:1. AGGREGAZIONE:informazione riassuntiva per punteggi di mapping che hanno lo stesso schema sourceinformazione riassuntiva per punteggi di mapping che hanno lo stesso schema source

2. COMPOSIZIONE:2. COMPOSIZIONE:informazione riassuntiva per due punteggi di mapping in cui lo schema target del primo informazione riassuntiva per due punteggi di mapping in cui lo schema target del primo corrisponde allo schema source del secondo.corrisponde allo schema source del secondo.

A

B

C

D

A

B

C

SRISRIAA aa11 aa22 …… aann

AA 0.80.8 0.90.9 …… 0.70.7

BB 0.60.6 0.60.6 …… 0.50.5

CC 0.40.4 0.50.5 …… 0.60.6

DD 0.70.7 0.70.7 …… 0.30.3

…… …… …… …… ……

SRISRIAA aa11 aa22 …… aann

AA 0.80.8 0.90.9 …… 0.70.7

BB 0.60.6 0.60.6 …… 0.50.5

…… …… …… …… ……

SRISRIBB bb11 bb22 …… bbmm

BB 0.80.8 0.90.9 …… 0.70.7

CC 0.60.6 0.60.6 …… 0.50.5

AA 0.40.4 0.70.7 0.30.3

…… …… …… …… ……

Modello matematico ispirato alla logica fuzzyModello matematico ispirato alla logica fuzzy mapping mapping relazione fuzzy relazione fuzzy punteggio punteggio grado di membership grado di membership

M(SM(SAA,S,SBB) ) S SAA S SBB

Costruzione delle informazioni riassuntiveCostruzione delle informazioni riassuntive

AGGREGAZIONEAGGREGAZIONE unione tra fuzzy set unione tra fuzzy set

COMPOSIZIONECOMPOSIZIONE composizione tra relazioni fuzzy rappresentate dai composizione tra relazioni fuzzy rappresentate dai corrispondenti fuzzy set corrispondenti fuzzy set

μμMM: S: SAA S SBB → [0,1] → [0,1]

Funzioni matematiche da impiegare:Funzioni matematiche da impiegare:AGGREGAZIONEAGGREGAZIONE

Proprietà:Proprietà:

Esempi:Esempi:

Funzioni matematiche da impiegare:Funzioni matematiche da impiegare:COMPOSIZIONECOMPOSIZIONE

Proprietà:Proprietà:

Esempi:Esempi:

Problematiche affrontate Problematiche affrontate nella tesinella tesi

Gestione dell’eterogeneità delle sorgenti Gestione dell’eterogeneità delle sorgenti coinvoltecoinvolte

Indici di Routing Semantici (SRI)Indici di Routing Semantici (SRI)

Gestione dell’ambiente P2PGestione dell’ambiente P2P

SimulazioneSimulazione

Gestione dell’ambiente P2PGestione dell’ambiente P2P

Ambiente P2P: entità autonome e indipendentiAmbiente P2P: entità autonome e indipendenti libera scelta degli istanti di connessionelibera scelta degli istanti di connessione libera scelta dei vicini libera scelta dei vicini

Nuovo moduloNuovo modulo che gestisce l’ambiente P2P che gestisce l’ambiente P2P Strutture datiStrutture dati Protocollo di interazione tra i peer Protocollo di interazione tra i peer Algoritmi per la connessione di nuovi nodi e Algoritmi per la connessione di nuovi nodi e

l’aggiornamento degli indici l’aggiornamento degli indici

Esempio di connessione e Esempio di connessione e aggiornamentoaggiornamento

A

SRISRIDD dd11 dd22 …… ddjj

DD

EE

FF

SRISRIBB bb11 bb22 …… bbmm

BB

AA

SRISRICC cc11 cc22 …… ccrr

CC

AA

SRISRIEE ee11 ee22 …… eekk

EE

DD

SRISRIFF ff11 ff22 …… ffii

FF

DDF

E

C

B

D

1. RICHIESTA 1. RICHIESTA CONNESSIONECONNESSIONE

2. RISPOSTA CONNESSIONE

SRISRIAA aa11 aa22 …… aann

AA

BB

CC

DD

SRISRIAA aa11 aa22 …… aann

AA

BB

CC

SRISRIDD dd11 dd22 …… ddjj

DD

EE

FF

AA

3. RICHIESTA AGGIORNAMENTO

4.1 RISPOSTA AGGIORNAMENTO

4.2 RISPOSTA AGGIORNAMENTO

4.3 RISPOSTA AGGIORNAMENTO

SRISRIAA aa11 aa22 …… aann

AA

BB

CC

DD

SRISRIDD dd11 dd22 …… ddjj

DD

EE

FF

AA

Problematiche affrontate Problematiche affrontate nella tesinella tesi

Gestione dell’eterogeneità delle sorgenti Gestione dell’eterogeneità delle sorgenti coinvoltecoinvolte

Indici di Routing Semantici (SRI)Indici di Routing Semantici (SRI)

Gestione dell’ambiente P2PGestione dell’ambiente P2P

SimulazioneSimulazione

Prove sperimentaliProve sperimentali

Carenza di PDMS liberamente impiegabili e Carenza di PDMS liberamente impiegabili e modificabili a scopo di testmodificabili a scopo di test simulazione simulazione

Ambiente di simulazione a eventi discretiAmbiente di simulazione a eventi discreti definizione di un modello per il sistemadefinizione di un modello per il sistema utilizzo di SimJava 2.0 utilizzo di SimJava 2.0

Scenario per la simulazioneScenario per la simulazione rete di peer rete di peer schemi di argomento diversoschemi di argomento diverso due tipi di test:due tipi di test:

1.1. Confrontabilità tra i punteggi di mappingConfrontabilità tra i punteggi di mapping2.2. Efficacia degli indici di routing semanticiEfficacia degli indici di routing semantici

Risultati: Confrontabilità dei mappingRisultati: Confrontabilità dei mapping

1

Risultati: Risultati: Efficacia degli indici di routing semanticiEfficacia degli indici di routing semantici

(a) Situazione iniziale

(b) Situazione finale

Efficacia degli indici di routing semanticiEfficacia degli indici di routing semantici

ConclusioniConclusioni Studio delle problematiche dei PDMSStudio delle problematiche dei PDMS Gestione dell’eterogeneità dei peerGestione dell’eterogeneità dei peer

Mapping semantici localiMapping semantici locali Modifiche a XML SModifiche a XML S33MARTMART

Indici di routing semanticiIndici di routing semantici Routing by mappingRouting by mapping Creazione delle informazioni riassuntiveCreazione delle informazioni riassuntive Modello matematico fuzzyModello matematico fuzzy

Gestione dell’ambiente P2PGestione dell’ambiente P2P Nuovo moduloNuovo modulo Strutture dati e protocolloStrutture dati e protocollo

SimulazioneSimulazione Ambiente di esecuzione P2PAmbiente di esecuzione P2P Prove sperimentaliProve sperimentali

Sviluppi futuriSviluppi futuri Informazioni quantitativeInformazioni quantitative

dati dati indici di routing quantitativi indici di routing quantitativi valori valori content summary content summary

Simulazione con reti più complesse e query realiSimulazione con reti più complesse e query reali Introdurre metriche di valutazione proprie dei sistemi di information retrievalIntrodurre metriche di valutazione proprie dei sistemi di information retrieval