UNIVERSITÀ DEGLI STUDI
DI MODENA E REGGIO EMILIA
Facoltà di Ingegneria – Sede di Modena
Corso di Laurea in Ingegneria Informatica
Query Processing by Semantic
Reformulation
_________________________
Elaborazione di Interrogazioni
tramite l’uso di
Corrispondenze Semantiche
Relatore
Prof.ssa Sonia Bergamaschi
Correlatore
Ing. Maurizio Vincini
Tesi di Laurea di
Raffaele Capezzera
Anno Accademico 2002 - 2003
Sommario
Query Processing by Semantic Reformulation
 Ambito di ricerca
 SEWASIE Brokering Agent
 DAML-S Broker
 Elaborazione di interrogazioni
 Riformulazione
 Implementazione
 Conclusioni e ricerca futura
2
Intermediazione di servizi
Query Processing by Semantic Reformulation
Interrogazione
Richiesta di servizio
vs
Annuncio delle capacità di servizio
Preferenze richieste
vs
Capacità pubblicizzate
Richiedente 1
Richiedente 2
Fornitore 1
Intermediario
Fornitore 2
Richiedente 3
Fornitore 3
Matchmaker
Broker
 Conosce le capacità dei fornitori ma
 Conosce sia le capacità dei fornitori
non le preferenze dei richiedenti
 Non si interpone nello scambio del
servizio
che le preferenze dei richiedenti
 Si interpone nello scambio del
servizio
3
Query Processing by Semantic Reformulation
Ambito di ricerca
Come può un broker determinare se una interrogazione verrà
soddisfatta da una sorgente di dati che si sia in precedenza esposta?
 Sistemi di integrazione intelligente di informazioni
 Web semantico
 Agenti
 Logiche descrittive
 Rappresentazione di ontologie
SEWASIE Brokering Agent
(BA)
DAML-S Broker
(DSB)
Analisi e sviluppo delle funzionalità comuni
4
SEWASIE Brokering Agent
Query Processing by Semantic Reformulation
SEWASIE (SEmantic Webs and AgentS in Integrated Economies, www.sewasie.org) è un motore di ricerca
avanzato per l’accesso intelligente tramite arricchimento semantico a sorgenti dati eterogeneee sul Web
Query Agent 1
Query Agent 2
Brokering Agent
Query Agent 3
Virtual
Data
Store
Virtual
Data
Store
SINode
SINode
Ontologia di
riferimento
Specifiche
 Ontologia di riferimento comune in ODLI3
 Interrogazioni in OQLI3
Virtual
Data
Store
SINode
Funzionalità richieste
 Protocollo di comunicazione per l’interazione con Query Agent ed SINode
 Accoppiamento semantico dei termini di un interrogazione rispetto
all’ontologia di riferimento per individuare l’SINode più adeguato a rispondere
5
Sistemi di integrazione a mediatore
Query Processing by Semantic Reformulation
Interrogazione
Utente – Applicazione
Utente - Applicazione
Mediatore
Mediatore
Mediatore
Wrapper
Riscrittura di
interrogazioni in
base alle
Decisione sulla
capacità delle esprimibilità
sorgenti
rispetto alle
sorgenti dati
Descrizione delle
capacità di
interrogazione e
delle capacità di
contenuto di una
sorgente dati
Wrapper 1
Wrapper 2
Sorgente dati 1
Sistemi di
integrazione
a mediatore
Sorgente dati 2
Ontologia
Wrapper 3
Wrapper 4
Sorgente dati 3
Infrastruttura
MAS
Sorgente dati 4
GAV
LAV
Capacità di
interrogazione
esplicite
Capacità di
contenuto
esplicite
MOMIS

-

-
-

TSIMMIS

-
-
-


Information
Manifold
-

-
-


SIMS



-
-

Carnot



-
-

InfoSleuth




-

6
DAML-S (Web service semantici)
Annotazione semantica dei contenuti del
Web (RDF, DAML, OIL, OWL, ...)
Interazioni tra agenti per lo scambio di servizi
sul Web (SOAP, WSDL, UDDI, ...)
Query Processing by Semantic Reformulation
Web semantico
Web service
DAML-S
Ontologia e linguaggio annotato per la
descrizione semantica di Web service
ServiceModel
presents
supports
ServiceGrounding
Linguaggio di descrizione
delle capacità offerte e
delle capacità richieste
describedBy
Service
ServiceProfile
input
output
precondition
effect
Indicazione dei più adeguati fornitori di servizio
per una data richiesta tramite accoppiamento
semantico delle capacità espresse dai rispettivi
ServiceProfile
7
Query Processing by Semantic Reformulation
DAML-S Broker
Algoritmo di accoppiamento
semantico dei ServiceProfile
 Gli output promessi dal
fornitore devono includere gli
output voluti dal richiedente
Funzionalità richieste
 Linguaggio di interrogazione
 Conversione di interrogazioni
in richieste ossia ServiceProfile
 Corrispondenze semantiche
tra gli input forniti dal
richiedente e gli input richiesti
dal fornitore
 Scelta del più appropriato
fornitore tra quelli indicati
dall’algoritmo di accoppiamento
semantico
8
Interazione tra QA, BA ed SINode
3. Conversione da interrogazione a richiesta
in forma di ServiceProfile
Query Processing by Semantic Reformulation
6. Riscrittura interrogazione
2. Interrogazione
Query Agent
Brokering Agent
5. Indicazione del SINode
4. Accoppiamento semantico
1. Annuncio capacità in forma di ServiceProfile
6. Interrogazione
8. Risposta
Virtual
Data
Store
SINode
7. Elaborazione risposta
Soluzioni Proposte
 Protocollo di comunicazione per il SEWASIE Brokering Agent
ibrido tra broker e matchmaker
 Accoppiamento semantico tra i ServiceProfile che
rappresentano richiesta ed annuncio di servizio per il soddisfacimento
di una interrogazione
9
Elaborazione di interrogazioni
 Interrogazioni poste al DAML-S Broker in DAML Query Language (DQL)
 Ontologia di riferimento comune tra richiedente, broker e fornitore
 Algoritmo di accoppiamento semantico delle capacità espresse dai ServiceProfile
 Capacità rappresentate da concetti
 Sviluppo
1. Astrazione
Da istanze e variabili dell’interrogazione
iniziale in concetti per operare l’algoritmo
di accoppiamento semantico
2. Accoppiamento semantico
3. Riscrittura
Da concetti dell’interrogazione astratta ed
istanze dell’interrogazione iniziale in
concetti ed istanze richiesti dal fornitore
indicato dall’algoritmo di accoppiamento
semantico
Riformulazione
Query Processing by Semantic Reformulation
 Premesse
10
Ontologia di riferimento
 Rappresentata nel linguaggio OWL DL (inferenze decidibili e complete)
Query Processing by Semantic Reformulation
Elemento di OWL DL
Descrizione di ODLI3
Rappresentazione in logica descrittiva
Significato
owl:Thing
-
T
concetto universo
owl:Nothing
-

concetto vuoto
interface, view
C
concetto astratto
B
D
intervallo concreto
owl:ObjectProperty
attribute
R
ruolo astratto
owl:DatatypeProperty
attribute
U
ruolo concreto
owl:inverseOf
-
R-
ruolo inverso
owl:SymmetricProperty
-
-R
ruolo simmetrico
owl:TransitiveProperty
-
R+
ruolo transitivo
and
C1 ∏ C2
congiunzione
union
C1  C2
disgiunzione
C
negazione
{o1, o2, …, ol}, {v1, v2, …, vm}
enumerazione
owl:Class
owl:DataRange
owl:intersectionOf
owl:unionOf
owl:complementOf
owl:one of
range, enum
rule
R.C, U.D
exists
R.C, U.D
quantificazione esistenziale
attribute set, forall
R.C, U.D
quantificazione universale
owl:hasValue
-
R : o2 , U : v
quantificazione su individui
owl:Cardinality
-
= n R, = n U
restrizione numerica
owl:maxCardinality
-
 n R,  n U
restrizione minorativa
owl:minCardinality
-
 n R,  n U
restrizione maggiorativa
owl:Restriction… owl:onProperty
owl:someValuesFrom
owl:allValuesFrom
restrizione
 Sostanziale equivalenza col linguaggio ODLI3
11
Query Processing by Semantic Reformulation
Riformulazione (1)





Interrogazioni formulate come triple (predicati binari)
Termini variabili intesi come output
Termini non variabili intesi come input
Similarità semantica (strutturale e lessicale) come euristica
Utilizzo di relazioni intra-ontolologiche
Astrazione
has+father(John, y)
has+father(John, man)
Di variabili
Interrogazione: P(x, B)
Se  Ai  {A1, A2, …, An} t.c.  C: P├ P(Ai, C)  KB ╞ P(Ai, C)
allora Abstract(x) = Ai.
Quindi, interrogazione astratta: P(Ai, B)
Interrogazione: P(A, y)
Se  Bi  {B1, B2, …, Bm} t.c.  C: P├ P(Bi, C)  KB ╞ P(Bi, C)
allora Abstract(y) = Bi.
Quindi, interrogazione astratta: P(A, Bi)
has+father(person, y)
Di istanze
Interrogazione: P(a, B)
Se  A t.c. a ├ A(a)  KB ╞ A(a)
allora Abstract(a) = A.
Quindi, interrogazione astratta: P(A, B)
12
Riformulazione (2)
Query Processing by Semantic Reformulation
Riscrittura
Trasformazione di concetti
Concetto origine: A = A0, concetto obiettivo: B = An.
A può essere trasformato in B sse
 P1 t.c. (P1 ├ P1(A0, A1)  KB ╞ P1(A0, A1))  (P1 ├ P1(A1, A0)  KB ╞ P1(A1, A0)),
 P2 t.c. (P2 ├ P2(A1, A2)  KB ╞ P2(A1, A2))  (P2 ├ P2(A2, A1)  KB ╞ P2(A2, A1)),
…
 Pn t.c. (Pn ├ Pn(An-1, An)  KB ╞ Pn(An-1, An))  (Pn ├ Pn(An, An-1)  KB ╞ Pn(An, An-1)),
Quindi, Percorso(A0, An) = Percorso(A0.A1.A2. … .An-1.An)
Riscrittura di istanze
Istanza origine: a = a0,
Concetto origine: A = A0 s.t. a0 ├ A0(a0)  KB ╞ A0(a0),
Concetto obiettivo: B = An,
PercorsoTriple(A0, An) = {(A0, P1, A1), (A1, P1, A2), ..., (An-1, Pn, An)}.
a0 può essere riscritta in un’istanza an t.c. an ├ An(an)  KB ╞ An(an) sse
 a1 t.c. (P1 ├ P1(a0, a1)  KB ╞ P1(a0, a1))  (P1 ├ P1(a1, a0)  KB ╞ P1(a1, a0)),
 a2 t.c. (P2 ├ P2(a1, a2)  KB ╞ P2(a1, a2))  (P2 ├ P2(a2, a1)  KB ╞ P2(a2, a1)),
…
 an t.c. (Pn ├ Pn(an-1, an)  KB ╞ Pn(an-1, an))  (Pn ├ Pn(an, an-1)  KB ╞ Pn(an, an-1))
13
Trasformazione di concetti - Esempio
Query Processing by Semantic Reformulation
person
isSubsuming
pet+ow ner
isSubsuming
cat+ow ner
isSubsuming
old+lady
isSubsumedBy
grow nup
isSubsuming
man
person
isSubsuming
driver
person
person
has+f ather
isSubsuming
AND(man, person)
grow nup
isSubsuming
isSubsuming
van+driver
man
isSubsuming
w hite+van+man
Caratteristiche dell’algoritmo
 Decidibile
 Completo
 Ordinamento dei percorsi
trovati
 Strategia breadth first con
euristica
Relazioni utilizzabili per
la trasformazione di
concetti
 equivalentClass
 subClassOf
 intersectionOf
 unionOf
 ObjectProperty
 DatatypeProperty
14
Query Processing by Semantic Reformulation
Implementazione e ragionatori
 Componente
software modulare
e flessibile scritto in
Java
 Ausilio
dell’ontologia
lessicale WordNet
 Ausilio di RACER
quale ragionatore
Ragionatori
Ragionamento
a
posteriori
Ragionamento
a
posteriori
Logica
descrittiva
implementata
Linguaggio
di
rappresentazione
Linguaggio
di
interrogazione
Mondo
aperto
Mondo
chiuso
Java
API
ODB-Tools
-
-
OCDL, OLCD
ODL, ODLI3
OQL, OQLI3

-
-
JTP

-
-
KIF 3.0
KIF 3.0

-

DAMLJessKB
-

-
JESS
JESS
-


FaCT
-
-
SHIQ, SHF
KRSS
KRSS

-

RACER
-
-
SHIQ
KRSS
KRSS

-

15
Query Processing by Semantic Reformulation
Conclusioni
 Nei sistemi di integrazione di dati a mediatore la descrizione delle capacità di
interrogazione permette di risolvere il CBR ed QED
 DAML-S come linguaggio di descrizione delle capacità di un Web service permette al
DAML-S Broker la scoperta dei fornitori di servizio più adatti per un certo richiedente
 Inquadrare il SEWASIE Brokering Agent come ibrido tra broker e matchmaker ed
inscriverlo entro il paradigma DAML-S gli giova le richieste funzionalità di accoppiamento
semantico
 L’elaborazione di interrogazioni comprende sottoprocessi quali riformulazione ed
accoppiamento semantico. La riformulazione di interrogazioni è costituita da astrazione e
riscrittura.
 Nella astrazione da variabili a concetti e nella trasformazione di concetti per la riscrittura
di interrogazioni si utilizza una euristica basata su similarità semantica (coadiuvata da
WordNet)
 Pur essendo stata proposta per dotare il DAML-S Broker delle funzionalità richieste, la
riformulazione di interrogazioni è applicabile ogni qualvolta sia necessario astrarre e
riscrivere termini rispetto a determinati concetti di riferimento
 L’intero processo sfrutta relazioni intra-ontologiche di una ontologia in OWL DL. Una
ontologia in ODLI3 è parimenti utilizzabile.
16
Ricerca futura
Query Processing by Semantic Reformulation
 Interrogazioni formulate come congiunzioni di predicati binari
 Interpretazione di predicati binari
 Accoppiamento semantico di predicati binari
 Riformulazione dei termini di una interrogazione per ottenere tutti i
parametri di un DAML-S ServiceProfile, non solo input ed output.
 Specifica analisi di interrogazioni in DQL ed OQLI3
 Utilizzo di ODB-Tools come ragionatore
 Interfaccia per permettere al DAML-S Broker di processare
interrogazioni DQL
 Ottimizzazione degli algoritmi implementati per la riformulazione di
interrogazioni con ulteriori euristiche
17
Query Processing by Semantic Reformulation
Bibliografia essenziale
 Jose Luis Ambite, Craig A. Knoblock, Ion Muslea and Andrew Philpot. Compiling Source
Descriptions for Efficient and Flexible Information Integration. Journal of Intelligent
Information Systems, vol. 16, no. 2, pp. 149-187. 2001.
 V. Vassalos and Y. Papakonstantinou. Expressive Capabilities Description Languages
and Query Rewriting Algorithms. Journal of Logic Programming, vol. 43, no. 1, pp. 75122. 2000.
 Sonia Bergamaschi, Silvana Castano, Domenico Beneventano, and Maurizio Vincini.
Semantic Integration of Heterogeneous Information Sources. Special Issue on Intelligent
Information Integration, Data & Knowledge Engineering, vol. 36, No. 1, Pages 215-249.
Elsevier Science B.V. 2001.
 Massimo Paolucci, Takahiro Kawamura, Terry R. Payne, and Katia Sycara. Semantic
Matching of Web Services Capabilities. Proceedings of the first International Semantic
Web Conference (ISWC), LNCS 2342, pp. 333-347. Springer Verlag. 2002.
 Franz Baader, Ralf Küsters, and Ralf Molitor. Rewriting Concepts Using Terminologies.
Proceedings of the Seventh International Conference on Knowledge Representation and
Reasoning (KR2000). 2000.
 Ian Horrocks, Peter F. Patel-Schneider, and Frank van Harmelen. From SHIQ and RDF
to OWL: The Making of a Web Ontology Language. Journal of Web Semantics, vol. 1, no.
1. 2003.
 Volker Haarslev and Ralf Möller. RACER User’s Guide and Reference Manual Version
1.7.7. November 7, 2003.
18
Query Processing by Semantic Reformulation
Elaborazione di interrogazioni tramite l’uso di
corrispondenze semantiche
Grazie per l’attenzione
Raffaele Capezzera