Università degli Studi di Modena e Reggio Emilia
Facoltà di Ingegneria – Corso di Laurea Specialistica in Ingegneria Informatica
Approssimazione semantica
per routing di interrogazioni
in un PDMS
Simona Sassatelli
Relatore:
Dott. Federica Mandreoli
Correlatore:
Ing. Riccardo Martoglia
Anno Accademico 2004/2005
Ambito di ricerca:
Progetto nazionale WISDOM
(Web Intelligent Search based on DOMain ontologies)
Obiettivo
definizione di tecniche e strumenti per la ricerca, la localizzazione e la
fruizione personalizzata di risorse informative disponibili su Web
Architettura di riferimento
Peer Data Management System (PDMS)
Ambito di indagine della tesi:
Processo di routing delle interrogazioni
Obiettivo
Sviluppo di tecniche che permettono di operare sulla base di
informazioni semantiche
Q’’
Peer Data Management
System
CiteSeer
(PDMS) Stanford
UW
Q’
Q’’
 Rete di peer indipendenti ed autonomi
Q’’
 Architettura decentralizzata e facilmente estensibile
DBLP
(Peer-to-Peer)
 I peer
Q decidono liberamente di condividere i propri dati
 nessuno schema logico mediato globale
Q’’
 relazioni semantiche stabilite localmente tra i singoli peer (mapping)
Paris
Roma
Vienna Q’
 I peer collaborano nel risolvere le interrogazioni poste
dagli utenti
 query poste usando lo schema del peer
 risposte provenienti da tutto il sistema
Problematiche affrontate
nella tesi
 Gestione dell’eterogeneità delle sorgenti
coinvolte
 Indici di Routing Semantici (SRI)
 Gestione dell’ambiente P2P
 Simulazione
Gestione dell’eterogeneità
dei peer
 Peer indipendenti
 eterogenei negli schemi adottati per
rappresentare i dati
 Mapping semantici locali
 approccio basato sul concetto di
approssimazione semantica
 Sistema XML S3MART
 sviluppato presso l’Università di Modena e
Reggio Emilia
 riscrittura di interrogazioni su insiemi di
documenti eterogenei
XML S3MART
Schema A
Schema B
musicstore
B
location
cdstore
storage
address
signboard
name
A
B
cd
state
vocalist cdtitle tracklist
stock
town
country
colorsign namesign
compactDisk
city street
A
D
passage
songlist
albumTitle
title
D
track
C
C
songtitle singer
2.
REWRITING
1. QUERY
SCHEMA
MATCHING
FOR $x IN /musicstore
A
WHERE $x//compactDisk/songlist/track/singer
=
"elisa"
/cdstore/cd
…/stock/compactDisk
AND $x//compactDisk/songlist/track/songtitle = "gift"
B
FOR $x
IN /cdstore
/musicstore/location
/cdstore/address
RETURN $x/signboard/namesign
C
WHERE $x/cd/vocalist = "elisa"
…/track/songtitle
…/passage/title
AND
$x/cd/tracklist/passage/title
= "gift"
D
…/compactDisk/albumTitle
…/cd/cdtitle
RETURN
$x/name
…
Limiti di XML S3MART
 Progettato per un contesto centralizzato (digital library eterogenee)
 per ogni coppia di schemi individua le migliori corrispondenze tra i concetti
 Ambiente distribuito P2P
Q
 routing delle query
E
D
Q
Q
Q
F
Q
Q
G
C
A
H
Q

Non è sempre conveniente
propagare una query verso
altri nodi
 traffico di rete
 dati inutili per l’utente
Q
B
Q
J
I
Q
Modifiche a XML S3MART
 XML S3MART processa gli schemi a coppie
 punteggi di mapping non utilizzabili per eseguire il routing
 Reingegnerizzazione:
 modifica della struttura
concettuale da uno-a-uno
a uno-a-molti
 correzione del calcolo
iterativo di fixpoint
 adattamento
dell’operazione di
normalizzazione
D
Q
?
A
C
Q
 Punteggi comparabili
 Calcolo dei punteggi efficiente
e incrementale
B
Problematiche affrontate
nella tesi
 Gestione dell’eterogeneità delle sorgenti
coinvolte
 Indici di Routing Semantici (SRI)
 Gestione dell’ambiente P2P
 Simulazione
Routing by mapping
 query propagate solo ai peer con un elevato
punteggio per i concetti richiesti
 Necessità di considerare le intere sottoreti che
hanno origine dai peer vicini.
E
D
 Non è possibile che
F
ogni peer calcoli i
mapping con tutti
gli altri
C
A
Q
H
Informazioni
riassuntive
B
I
G
J
Indici di Routing Semantici (SRI)
 Strutture dati locali ad ogni peer
 Informazioni riassuntive di come ogni elemento dello schema di
un peer viene approssimato semanticamente nelle sottoreti che
hanno origine dai vicini

B
Esempio:
A
SRIA
a1
a2
…
a5
A
0.8
0.9
…
0.7
B
0.6
0.0
…
0.5
C
0.4
0.5
…
0.6
I
C
J
Costruzione delle informazioni riassuntive
Calcolate a partire dai punteggi di mapping determinati con XML S3MART:
1. AGGREGAZIONE:
informazione riassuntiva per punteggi di mapping che hanno lo stesso schema source
SRIA
a1
a2
…
an
A
0.8
0.9
…
0.7
B
0.6
0.6
…
0.5
C
0.4
0.5
…
0.6
D
0.7
0.7
…
0.3
…
…
…
…
…
B
C
A
D
2. COMPOSIZIONE:
informazione riassuntiva per due punteggi di mapping in cui lo schema target del primo
corrisponde allo schema source del secondo.
A
C
SRIB
b1
b2
…
bm
B
0.8
0.9
…
0.7
C
0.6
0.6
…
0.5
0.5
A
0.4
0.7
…
…
…
…
SRIA
a1
a2
…
an
A
0.8
0.9
…
0.7
B
0.6
0.6
…
…
…
…
…
B
0.3
…
…
Costruzione delle informazioni riassuntive
 Modello matematico ispirato alla logica fuzzy
 mapping  relazione fuzzy
 punteggio  grado di membership
M(SA,SB)  SA SB
μM: SA SB → [0,1]
 AGGREGAZIONE  unione tra fuzzy set
 COMPOSIZIONE  composizione tra relazioni fuzzy rappresentate dai
corrispondenti fuzzy set
Funzioni matematiche da impiegare:
AGGREGAZIONE
Proprietà:
Esempi:
Funzioni matematiche da impiegare:
COMPOSIZIONE
Proprietà:
Esempi:
Problematiche affrontate
nella tesi
 Gestione dell’eterogeneità delle sorgenti
coinvolte
 Indici di Routing Semantici (SRI)
 Gestione dell’ambiente P2P
 Simulazione
Gestione dell’ambiente P2P

Ambiente P2P: entità autonome e indipendenti
 libera scelta degli istanti di connessione
 libera scelta dei vicini

Nuovo modulo che gestisce l’ambiente P2P
 Strutture dati
 Protocollo di interazione tra i peer
 Algoritmi per la connessione di nuovi nodi e
l’aggiornamento degli indici
Esempio di connessione e
aggiornamento
SRIA
a1
a2
…
aann
A
B
B
SRIB
b2
…
bm
B
C
A
D
4.3 RISPOSTA
AGGIORNAMENTO
4.1
RISPOSTA
3.
RICHIESTA
1. 2.
RICHIESTA
RISPOSTA
AGGIORNAMENTO
AGGIORNAMENTO
CONNESSIONE
CONNESSIONE
4.2
RISPOSTA
AGGIORNAMENTO
d1
d2
…
SRIC
C
A
SRID
b1
dj
c1
c2
…
e1
e2
…
cr
C
A
SRIE
D
E
ek
E
D
D
E
F
A
SRIF
F
F
D
f1
f2
…
fi
Problematiche affrontate
nella tesi
 Gestione dell’eterogeneità delle sorgenti
coinvolte
 Indici di Routing Semantici (SRI)
 Gestione dell’ambiente P2P
 Simulazione
Prove sperimentali
 Carenza di PDMS liberamente impiegabili e
modificabili a scopo di test
 simulazione
 Ambiente di simulazione a eventi discreti
 definizione di un modello per il sistema
 utilizzo di SimJava 2.0
 Scenario per la simulazione
 rete di peer
 schemi di argomento diverso
 due tipi di test:
1. Confrontabilità tra i punteggi di mapping
2. Efficacia degli indici di routing semantici
Risultati: Confrontabilità dei mapping
1
Risultati:
Efficacia degli indici di routing semantici
(b) Situazione finale
(a) Situazione iniziale
Efficacia degli indici di routing semantici
Conclusioni
 Studio delle problematiche dei PDMS
 Gestione dell’eterogeneità dei peer
 Mapping semantici locali
 Modifiche a XML S3MART
 Indici di routing semantici
 Routing by mapping
 Creazione delle informazioni riassuntive
 Modello matematico fuzzy
 Gestione dell’ambiente P2P
 Nuovo modulo
 Strutture dati e protocollo
 Simulazione
 Ambiente di esecuzione P2P
 Prove sperimentali
Sviluppi futuri
 Informazioni quantitative
 dati  indici di routing quantitativi
 valori  content summary
 Simulazione con reti più complesse e query reali
 Introdurre metriche di valutazione proprie dei sistemi di
information retrieval