Approssimazione semantica Approssimazione semantica per routing di interrogazioni per routing di interrogazioni in un PDMSin un PDMS

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

in un PDMS in un PDMS

Università degli Studi di Modena e Reggio Emilia Università degli Studi di Modena e Reggio Emilia

Facoltà di Ingegneria – Corso di Laurea Specialistica in Ingegneria Informatica Facoltà di Ingegneria – Corso di Laurea Specialistica in Ingegneria Informatica

Anno Accademico 2004/2005 Anno Accademico 2004/2005 Relatore:

Relatore:

Dott. Federica Mandreoli Dott. Federica Mandreoli

Correlatore Correlatore:

Ing. Riccardo Martoglia Ing. Riccardo Martoglia

Simona Sassatelli

Simona 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 Web fruizione personalizzata di risorse informative disponibili su Web

Obiettivo Obiettivo

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

Architettura di riferimento Architettura di riferimento

Ambito di indagine della tesi:

Ambito di indagine della tesi:

Sviluppo di tecniche che permettono di operare sulla base di Sviluppo di tecniche che permettono di operare sulla base di

informazioni semantiche informazioni semantiche

Processo di routing delle interrogazioni Processo di routing delle interrogazioni

Obiettivo Obiettivo

Peer Data Management System Peer Data Management System

(PDMS) (PDMS)

 Rete di Rete di peer peer 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 dati I 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 utenti

dagli 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 tesi nella tesi

 Gestione dell’eterogeneità delle sorgenti Gestione dell’eterogeneità delle sorgenti coinvolte

coinvolte

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

 Gestione dell’ambiente P2P Gestione dell’ambiente P2P

 Simulazione Simulazione

Gestione dell’eterogeneità Gestione dell’eterogeneità

dei peer dei peer

 Mapping semantici locali Mapping semantici locali

  approccio basato sul concetto di approccio basato sul concetto di

approssimazione semantica approssimazione semantica

 Peer indipendenti Peer indipendenti

  eterogenei negli schemi adottati per eterogenei negli schemi adottati per rappresentare i dati

rappresentare i dati

 Sistema Sistema XML S XML S

³³

MART MART

 sviluppato presso l’Università di Modena e sviluppato presso l’Università di Modena e Reggio Emilia

Reggio Emilia

 riscrittura di interrogazioni su insiemi di riscrittura di interrogazioni su insiemi di documenti eterogenei

documenti eterogenei

Schema A

Schema A Schema B Schema B

cdstore

cdtitle cd

vocalist address

state

city tracklist

passage

title street

musicstore

compactDisk

storage

stock signboard

country colorsign namesign

songlist

songtitle singer track

albumTitle location

town

name

XML S

XML S

³³

MART MART

BB

BB

CC

CC AA

AA

DD

DD

… … /stock/compactDisk /stock/compactDisk

^AA

/cdstore/cd /cdstore/cd /musicstore/location

/musicstore/location

^BB

/cdstore/address /cdstore/address

… … /track/songtitle /track/songtitle

^CC

… … /passage/title /passage/title

… … /compactDisk/albumTitle /compactDisk/albumTitle

^DD

… … /cd/cdtitle /cd/cdtitle

… …

1. SCHEMA MATCHING 1. SCHEMA MATCHING

2. QUERY REWRITING 2. QUERY REWRITING FOR $x IN /musicstore

FOR $x IN /musicstore WHERE

WHERE

$x//compactDisk/songlist/track/singer =

$x//compactDisk/songlist/track/singer =

"elisa"

"elisa"

AND AND

$x//compactDisk/songlist/track/songtitl

$x//compactDisk/songlist/track/songtitl e = "gift"

e = "gift"

RETURN $x/signboard/namesign RETURN $x/signboard/namesign

FOR $x IN /cdstore FOR $x IN /cdstore

WHERE $x/cd/vocalist = WHERE $x/cd/vocalist =

"elisa"

"elisa"

AND AND

$x/cd/tracklist/passage/title

$x/cd/tracklist/passage/title

= "gift"

= "gift"

RETURN $x/name RETURN $x/name

Limiti di XML S

Limiti di XML S

³³

MART MART

 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 concetti per ogni coppia di schemi individua le migliori corrispondenze tra i concetti

 Ambiente distribuito P2P Ambiente distribuito P2P

  routing delle queryrouting delle query

A

D

C

B

E

F

G H

I J

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 nodi

altri nodi

 traffico di rete traffico di rete

 dati inutili per l’utentedati inutili per l’utente

Modifiche a XML S

Modifiche a XML S

³³

MART MART

 XML S XML S

³³

MART processa gli schemi a coppie MART processa gli schemi a coppie

  punteggi di mapping non utilizzabili per eseguire il routing punteggi 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-molti

a uno-a-molti

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

 adattamento adattamento

dell’operazione di dell’operazione di normalizzazione normalizzazione

 Punteggi comparabili Punteggi comparabili

 Calcolo dei punteggi efficiente Calcolo dei punteggi efficiente e incrementale

e incrementale

Problematiche affrontate Problematiche affrontate

nella tesi nella tesi

 Gestione dell’eterogeneità delle sorgenti Gestione dell’eterogeneità delle sorgenti coinvolte

coinvolte

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

 Gestione dell’ambiente P2P Gestione dell’ambiente P2P

 Simulazione Simulazione

Routing by mapping Routing by mapping

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

Informazioni Informazioni riassuntive riassuntive

A

D

C

B

E

F

G H

I J

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

con tutti gli 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 peer Strutture dati locali ad ogni peer



Informazioni riassuntive

Informazioni 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

C I

SRISRI_AA aa₁₁ aa₂₂ …… aa₅₅ 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 riassuntive Costruzione delle informazioni riassuntive

Calcolate a partire dai punteggi di mapping determinati con XML S

Calcolate a partire dai punteggi di mapping determinati con XML S³³MART:MART:

1. AGGREGAZIONE:

1. AGGREGAZIONE:

informazione riassuntiva per punteggi di mapping che hanno lo stesso schema source informazione 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

SRISRI_AA aa₁₁ aa₂₂ …… aa_nn

AA 0.80.8 0.90.9 …… 0.70.7 B

B 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

…

… …… …… …… ……

SRISRI_AA aa₁₁ aa₂₂ …… aa_nn AA 0.80.8 0.90.9 …… 0.70.7 BB 0.60.6 0.60.6 …… 0.50.5

…… …… …… …… ……

SRISRI_BB bb₁₁ bb₂₂ …… bb_mm B

B 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 fuzzy Modello matematico ispirato alla logica fuzzy

 mapping mapping  relazione fuzzy relazione fuzzy

 punteggio punteggio  grado di membership grado di membership

M(SM(S_AA,S,S_BB) )  S S_AA S S_BB

Costruzione delle informazioni riassuntive Costruzione 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: S_AA S S_BB → [0,1] → [0,1]

Funzioni matematiche da impiegare:

Funzioni matematiche da impiegare:

AGGREGAZIONE AGGREGAZIONE

Proprietà:

Proprietà:

Esempi:

Esempi:

Funzioni matematiche da impiegare:

Funzioni matematiche da impiegare:

COMPOSIZIONE COMPOSIZIONE

Proprietà:

Proprietà:

Esempi:

Esempi:

Problematiche affrontate Problematiche affrontate

nella tesi nella tesi

 Gestione dell’eterogeneità delle sorgenti Gestione dell’eterogeneità delle sorgenti coinvolte

coinvolte

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

 Gestione dell’ambiente P2P Gestione dell’ambiente P2P

 Simulazione Simulazione

Gestione dell’ambiente P2P Gestione dell’ambiente P2P

 Ambiente P2P: entità autonome e indipendenti Ambiente P2P: entità autonome e indipendenti

  libera scelta degli istanti di connessione libera scelta degli istanti di connessione

  libera scelta dei vicini libera scelta dei vicini

 Nuovo modulo che gestisce l’ambiente P2P Nuovo modulo che gestisce l’ambiente P2P

 Strutture dati Strutture 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

aggiornamento aggiornamento

A

SRI

SRI_DD dd₁₁ dd₂₂ …… dd_jj DD

EE FF

SRISRI_BB bb₁₁ bb₂₂ …… bb_mm B

B AA

SRISRI_CC cc₁₁ cc₂₂ …… cc_rr CC

AA

SRISRI_EE ee₁₁ ee₂₂ …… ee_kk EE

D D

SRISRI_FF ff₁₁ ff₂₂ …… ff_ii FF

DD

F E C

B

D

1. RICHIESTA 1. RICHIESTA

CONNESSIONE CONNESSIONE 2. RISPOSTA CONNESSIONE

SRISRI_AA aa₁₁ aa₂₂ …… aa_nn AA

BB CC DD

SRISRI_AA aa₁₁ aa₂₂ …… aa_nn AA

BB CC

SRISRI_DD dd₁₁ dd₂₂ …… dd_jj DD

EE FF AA

3. RICHIESTA

AGGIORNAMENTO 4.1 RISPOSTA

AGGIORNAMENTO 4.2 RISPOSTA

AGGIORNAMENTO 4.3 RISPOSTA

AGGIORNAMENTO

SRISRI_AA aa₁₁ aa₂₂ …… aa_nn AA

BB CC D D

SRI

SRI_DD dd₁₁ dd₂₂ …… dd_jj DD

EE FF AA

Problematiche affrontate Problematiche affrontate

nella tesi nella tesi

 Gestione dell’eterogeneità delle sorgenti Gestione dell’eterogeneità delle sorgenti coinvolte

coinvolte

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

 Gestione dell’ambiente P2P Gestione dell’ambiente P2P

 Simulazione Simulazione

Prove sperimentali Prove sperimentali

 Carenza di PDMS liberamente impiegabili e Carenza di PDMS liberamente impiegabili e modificabili a scopo di test

modificabili a scopo di test

  simulazione simulazione

 Ambiente di simulazione a eventi discreti Ambiente di simulazione a eventi discreti

 definizione di un modello per il sistema definizione di un modello per il sistema

 utilizzo di SimJava 2.0 utilizzo di SimJava 2.0

 Scenario per la simulazione Scenario per la simulazione

 rete di peer rete di peer

 schemi di argomento diverso schemi di argomento diverso

 due tipi di test: due tipi di test:

1. 1.

Confrontabilità tra i punteggi di mappingConfrontabilità tra i punteggi di mapping

2. 2.

Efficacia degli indici di routing semanticiEfficacia degli indici di routing semantici

Risultati: Confrontabilità dei mapping Risultati: Confrontabilità dei mapping

1

Risultati:

Risultati:

Efficacia degli indici di routing semantici Efficacia degli indici di routing semantici

(a) Situazione iniziale

(b) Situazione finale

Efficacia degli indici di routing semantici

Efficacia degli indici di routing semantici

Conclusioni Conclusioni

 Studio delle problematiche dei PDMS Studio delle problematiche dei PDMS

 Gestione dell’eterogeneità dei peer Gestione dell’eterogeneità dei peer

 Mapping semantici localiMapping semantici locali

 Modifiche a XML SModifiche a XML S³³MARTMART

 Indici di routing semantici Indici di routing semantici

 Routing by mappingRouting by mapping

 Creazione delle informazioni riassuntiveCreazione delle informazioni riassuntive

 Modello matematico fuzzyModello matematico fuzzy

 Gestione dell’ambiente P2P Gestione dell’ambiente P2P

 Nuovo moduloNuovo modulo

 Strutture dati e protocolloStrutture dati e protocollo

 Simulazione Simulazione

 Ambiente di esecuzione P2PAmbiente di esecuzione P2P

 Prove sperimentaliProve sperimentali

Sviluppi futuri Sviluppi 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