Seminario di Ingegneria del Software
“Studio di RacePro per fare delle
interrogazioni in OWL-QL. In particolare
dovrei cercare di esprimere delle
conjunctive-queries interessanti”.
Alessio De Gaetanis
OBIETTIVI
• Analisi delle funzionalità del sistema
RacerPro e dell’applicazione client
RacerPorter.
• Definizione di una base di conoscenza in
RacerPro
• Studio del linguaggio nRQL, che ci
permetterà di esprimere delle conjunctivequeries su alcune basi di conoscenza.
Funzioni di RacerPro
Sistema di Ragionamento Web Semantico: data
un’ontologia OWL (OWL-Lite o OWL-DL), ne controlla
la consistenza, trova relazioni di sottoclasse, i
sinonimi e recupera le risorse.
Sistema di logica descrittiva: sistema di
rappresentazione della conoscenza che implementa il
calcolo basato su tableau altamente ottimizzato per
una logica descrittiva molto espressiva. Il sistema
implementa la logica descrittiva ALCQHIR+. Data una:
TBox  determina la (in)consistenza, la sussunzioni,
e le relazioni padre-figlio tra concetti.
ABox  controlla la sua consistenza, testa e recupera
gli individui che soddisfano certe condizioni,…
RacerPorter
Shell: display:
permette
di
una
query,
ilfocalizzando
cui risultato
Network:
Individuals:
Queries
Taxonomy:
(Rules):
visualizza
una
una volta
volta
si effettuare
può
la selezionato
strutture
selezionato
selezionare
dell
un
ununa
ABox
concetto,
elemento
query
(rule)
si
puoi
possono
ottenere
dalla
l’attenzione
listalae
State
poi
usare
i pulsanti
per
un
comandosemplicemente
alla query (rule)
sull’elemento
lista
dimostrato
tutti
iletipi
selezionato
adistanze.
essoapplicare
associati
premendo
il
recuperare
sue
sarà
nell’area
RacerPro
Log.
indica
lo
stato
corrente
del
sistema,
selezionata.
Pulsante Direct Types o All Types
che indica l’oggetto corrente che si
sta interrogando.
KB in RacerPro – I Concetti
Bisogna definire i termini di concetto complessi utilizzando:
• i termini booleani
• le qualified restriction (il riempitivo
di ruolo deve essere di un certo concetto).
• le number restriction
• top e bottom
• i concetti di dominio concreto
(restrizioni di predicato per i riempitivi
degli attributi)
Attributi interi  min, max,equal
Attributi reali  >,>=,<,<=,=,<>
Predicato esistenziale: a o an
Predicato di negazione: no
KB – Assiomi di Concetto e TBox
• General concept inclusion: (implies C1
• Concept equation: (equivalent C1 C2)
• Concept disjointness axioms:
C2)
(disjoint C1 … Cn)
• Primitive concept axioms:
(define-primitive-concept CN C)
•Primitive concept axioms:
(define-concept CN C)
 Possono essere ciclici
 Una TBox può contenere anche diversi assiomi per un
singolo concetto.
KB – Dichiarazione di ruoli
L’insieme dei ruoli (R) è costituito da due insiemi
disgiunti:
• Features (F): ruoli funzionali.
• Ruoli transitivi (R+): ruoli transitivamente
chiusi
Sono permesse gerarchie di ruolo
Per ogni ruolo bisogna definire :domain e
il :range
Si usa :inverse o (inv R) per riferirsi al
ruolo inverso
Possono essere definiti o nella signature o tramite:
(define-primitive-role RN :domain C)
(define-primitive-role RN :range D)
KB – Dominio Concreto
A ogni individuo può essere associato un
oggetto (nome per il valore del dominio
concreto) tramite i nomi d’attributo.
L‘insieme A di tutti gli attributi deve
essere disgiunto dall’insieme dei ruoli.
Gli attributi sono considerati come “typed”
(possono assumere valori di tipo cardinal,
integer, real, complex o string).
KB - Esempio
...
(signature
:atomic-concepts (... teenager)
:roles (...)
:attributes ((integer age)
(real temperature-celsius)
(real temperature-fahrenheit))
:individuals (eve doris)
:objects (temp-eve temp-doris)
...
(equivalent teenager (and human (min age 16)))
(equivalent old-teenager (and human (min age 18)))
(equivalent human-with-fever
(and human (>= temperature-celsius 38.5))
(equivalent seriously-ill-human
(and human (>= temperature-celsius 42.0)))
(constrained doris temp-doris temperature-celsius)
(constraints (= temp-doris 39.5))
TBOX
...
ABOX
Modellazione di logiche descrittive
Racer
Inf. indefinita
≠
Database
Inf. definita
Open World Assumption: ciò che non
può essere provato esser vero, non vuol
dire che sia falso.
Racer permette di utilizzare anche la LocalClosed World Assumption (uso di NAF)
RacerPro è in grado di leggere file RDF,
RDFS e OWL.
nRQL-new Racer Query Language
• Linguaggio di query di ABox per DL espressive
ALCQHIR+(D-)
• Linguaggio di query RDF e OWL
Permette di esprimere conjunctive query
Le espressioni di base sono detti atomi unari (un
oggetto) o binari (con due). Un oggetto può essere
o un individuo o una variabile iniettiva o ordinaria.
Semantica del dominio attivo: le variabili possono
essere associate soltanto a individui modellati
esplicitamente nella corrente ABox (senza un
preciso ordinamento sulla loro consegna).
nRQL – Concept Query Atoms
Atomi unari utili per recuperare tutti gli
individui di un concetto o di una classe OWL.
Esempio: Query head Query body
(retrieve (?x) (?x woman))
> (((?X EVE)) ((?X DORIS)) ((?X ALICE)) ((?X BETTY))).
Espressione di
concetto
Esempio: da un determinato documento OWL. complessa
(retrieve (?x) (?x (or
|http://www.owl-ontologies.com/unnamed.owl#person|
|http://www.owl-ontologies.com/unnamed.owl#book|)))
> (((?X |http://www.owl-ontologies.com/unnamed.owl#michael|))
((?X |http://www.owl-ontologies.com/unnamed.owl#michael|)))
nRQL è più potente di qualsiasi altro
linguaggio di query di documenti RDF
nRQL- Role Query Atoms
Atomi binari necessari per recuperare coppie dei
riempitivi di ruolo contenuti in una ABox o coppie di
individui OWL legati da un object properties.
Esempio.
(retrieve (?mother ?child) (?mother ?child has-child))
> (((?MOTHER BETTY) (?CHILD DORIS))
((?MOTHER BETTY) (?CHILD EVE))
((?MOTHER ALICE) (?CHILD BETTY))
((?MOTHER ALICE) (?CHILD CHARLES))).
Ruolo invertito: costruttore INV
(retrieve (?mother ?child) (?child ?mother (inv has-child)))
Ruolo negato: costruttore not (non è supportato
da altre DL ALCQHIR+(D-))
(retrieve (?x) (?x (not mother)))
> (((?X CHARLES)))
nRQL–Constraint Query Atoms
Atomi binari utili per recuperare quelle coppie di
individui della ABox (o OWL) il cui valore di certi
attributi di dominio concreto soddisfa un vincolo.
Esempio: dopo aver aggiunto l’età per ogni individuo.
(retrieve (?x) (?x (>= age 75)))
> (((?X ALICE))).
I singoli attributi, possono essere sostituiti da
catena di ruoli di lunghezza arbitraria (terminanti
con attributi)
Esempio.
(retrieve (?x) (?x ?x (constraint (has-father age)
(has-mother age) >))).
nRQL – Auxiliary Query Atoms
Atomi HAS-KNOWN-SUCCESSOR che permettono di
recuperare gli individui che hanno un certo
successore di ruolo modellato esplicitamente
nell’ABox, ma non siamo interessati attualmente al
recupero di questo successore.
Esempio.
(retrieve (?x) (?x (has-known-successor has-child)))
> (((?X CHARLES)) ((?X BETTY)) ((?X ALICE))).
nRQL – Operatori
Query Head Projection
Recuperano:
• Oggetti del dominio concreto di individui dell’ABox e i loro valori
• Le datatype properties e le annotation properties di un individuo in
un file OWL
Assicura che alice può essere limitato
Solo all’individuo Alice dell’ABox
Esempio
(retrieve (alice (age alice))(bind-individual alice))
> ((($?ALICE ALICE) ((AGE $?ALICE) (ALICE-AGE)))).
(retrieve (alice (age alice) (told-value (age alice)))
(bind-individual alice))
> ((($?ALICE ALICE)
((AGE $?ALICE) (HUHU ALICE-AGE)
((:TOLD-VALUE (AGE $?ALICE)) (:NO-TOLD-VALUE 80))))
nRQL – Query Complesse (1/3)
Possiamo costruire un body query più complesso con
i seguenti operatori:
• AND: costruttore n-ario usato per formulare query
congiuntive
congiunti
Esempio
(retrieve (?x ?y) (and (?x mother) (?y man) (?x ?y has-child)))
> (((?X ALICE) (?Y CHARLES))).
Esempio: tutte le persone che hanno una mamma in comune
(retrieve (?mother ?child1 ?child2)
(and (?child1 human)
(?child2 human)
(?mother ?child1 has-child)
(?mother ?child2 has-child))).
nRQL – Query Complesse (2/3)
• UNION: calcola l’unione dei singoli insiemi
di risposta (con stessa arità) dei corpi dei
query argomento.
Esempio: la prima query deve essere trasformata nella seconda.
(retrieve (?x ?y) (union (?x ?y has-child) (?x man)))
(retrieve (?x ?y) (union (?x ?y has-child)
(and (?x man) (?y top)))).
• NEG: implementa la negazione come
semantica di fallimento (NAF). Si può
utilizzare anche per atomi di ruolo
Esempio: complementare di (?x grandmother).
(retrieve (?x) (neg (?x grandmother)))
nRQL – Query Complesse (3/3)
• INV: costruttore di ruoli inversi.
• PROJECT-TO: operatore di proiezione per
body di query.
Esempio: Data l’ABox
(instance a c)
(instance b d)
(instance c top)
(related a b r)
Vogliamo recuperare quelle istanze C che non hanno successori noti
R che sono istanze di D. In questo caso la risposta dovrebbe essere
(((?X B)) ((?X C))).
(retrieve (?x) (neg (project-to (?x)
(and (?x c) (?x ?y r) (?y d)))))
 La proiezione deve essere effettuata prima della negazione
Modi di processamento
Set at a time: computa la risposta in unico insieme
(retrieve)
Lazy mode: evita computazioni che non riguardano la
query  minimizza il tempo di computazione
Eager mode: prima di rispondere alla query, classifica la
TBox  minimizza globalmente il tempo di processamento.
Tuple at a time: le tuple vengono restituite una alla volta su
richiesta del client.  multi-processamento delle query:
ognuna si contraddistingue dall’identificativo (id)
Lazy mode: le prossime tuple non sono compuate fino alla
richiesta del client  il thread è in fase di waiting
Eager mode: il thread continua a calcolare anche le tuple
successive che vengono messe in coda per eventuali
richieste.
Grado di completezza
Modo completo
Se il test di consistenza iniziale di una ABox è
impossibile il ragionamento e i servizi di recupero
sono indisponibili per l’alta complessità
Es. Non è possibile caricare un’intera università dal
LUBM (solo 5 dipartimenti anziché 14)
 Utilizziamo un modo incompleto per recuperare
individui dall’ABox  potrebbe risultare completo per
alcune ABox strutturate in maniera semplice
Casi di Studio – Prima KB (1/4)
(in-knowledge-base grafo grafo-node-egde)
(signature :atomic-concepts (node redN blueN)
:roles ((edge :inverse inverse-edge
:domain node
:range node))
:individuals (a b c d))
(implies *top* (and (all edge node)
(all inverse-edge node)))
(implies redN node)
(implies blueN node)
(implies redN (not blueN))
(implies node (or redN blueN))
a
c
b
d
(related
(related
(related
(related
a
b
c
c
b
c
a
d
edge)
edge)
edge)
edge)
Casi di Studio – Prima KB (2/4)
x
Prima query:
y
z
x
q(x) :- ∃y, z, w. edge(x,y) ∧ edge(y,z) ∧ edge(z,w)
In nRQL:
(RETRIEVE (?X) (AND (?X ?Y EDGE) (?Y ?Z EDGE)
(?Z ?W EDGE)))
> (((?X D)) ((?X A)) ((?X C)) ((?X B))
 In ogni modello, esiste una catena di questo tipo a partire da ogni nodo
a
a
a
a
c
c
b
d
c
b
d
(1)
c
b
d
(2)
b
d
(3)
(4)
Casi di Studio – Prima KB (3/4)
Seconda query:
x
y
q(x,y,z) :- edge(x,y) ∧ edge(y,z) ∧ edge(z,x)
In nRQL:
(RETRIEVE (?X ?Y ?Z) (AND (?X ?Y EDGE) (?Y ?Z EDGE)
(?Z ?X EDGE)))
> (((?X A) (?Y B) (?Z C))
(1)
((?X C) (?Y A) (?Z B))
(2)
((?X B) (?Y C) (?Z A)))
(3)
z
a
 Il sistema fornisce tre liste di nodi
differenti che soddisfano la query, che
in realtà però individuano sempre lo
stesso ciclo di nodi
b
c
d
Terza query:
q(x) :- edge(x,y) ∧ edge(y,z) ∧ edge(z,x)
In nRQL:
(RETRIEVE (?X) (AND (?X ?Y EDGE) (?Y ?Z EDGE)
(?Z ?X EDGE)))
> (((?X A)) ((?X C)) ((?X B)))
x
y
z
Casi di Studio – Prima KB (4/4)
Quarta query:
q(x) :- ∃y,z. edge(x,y) ∧ RedN(y) edge(y,z) ∧ BlueN(z) ∧ edge(z,x)
In nRQL:
x
(RETRIEVE (?X) (AND (?X ?Y EDGE) (?Y REDN)
(?Y ?Z EDGE) (?Z BLUEN) (?Z ?X EDGE)))
> NIL
y
z
In questo caso il sistema RacerPro non è in grado di dimostrare l’esistenza di
tale cammino. Infatti assegnando un colore ai nodi (in particolare al nodo c) a cui
non è stato ancora associato, in tutte le possibili combinazione, possiamo
osservare l’esistenza di tale cammino in ognuna di esse (in ogni modello).
a
a
c
c
b
d
b
d
Casi di Studio – Seconda KB (1/2)
(in-knowledge-base grafoII grafoII-node-egde)
(signature :atomic-concepts (node nodeRB)
:roles ((edgeR :inverse inverse-edgeR
:domain node
:range node)
(edgeB :inverse inverse-edgeB
:domain node
:range node))
:individuals (a))
a
(implies
(implies
(implies
(implies
(implies
(implies
(some inverse-edgeR node) node)
(some edgeR node) node)
(some inverse-edgeB node) node)
(some edgeB node) node)
nodeRB (some edgeB node))
nodeRB (some edgeR node))
(related a a edgeB)
(instance a nodeRB)
Casi di Studio – Seconda KB(2/2)
Prima query
q(x):-∃y, z. edgeB(x,y) ∧ edgeR(x,z) ∧ edgeR(y,z)
In nRQL:
(RETRIEVE (?X) (AND (?X ?Y EDGEB) (?X ?Z EDGER)
(?Y ?Z EDGER)))
> NIL
 Neanche in questo caso il sistema è in grado di dimostrare che il
nodo a soddisfa la query in ogni modello. Infatti il nodo a (a cui
associamo la variabile x), essendo un nodeRB, deve avere un edgeB
(lo ha già verso se stesso) e un edgeR verso un altro nodo (oppure
anche verso se stesso). Quindi poiché anche y coincide con il nodo a,
l’edgeR condiviso da x e z, sarà condiviso anche da y e z, come è
evidente in figura.
a
x
y
z
Casi di Studio
Compito A del 19/12/2005
Casi di Studio
Compito A del 19/12/2005 (1/3)
Prima query
Per ogni schema concettuale che ha richiesto più di 30 giorni per lo
sviluppo, si vogliono conoscere i dati relativi al progetto, al numero, e alla
versione.
(RETRIEVE
> (((?X
(?X |http://www.owl-ontologies.com/unnamed.owl#Conceptual_12|)
((:TOLD-VALUE
(TOLD-VALUE (|http://www.owl-ontologies.com/unnamed.owl#schemeNumber| ?X))
(|http://www.owl-ontologies.com/unnamed.owl#schemeNumber|?X))(234))
(TOLD-VALUE
(|http://www.owl-ontologies.com/unnamed.owl#version| ?X))
((:TOLD-VALUE
?Y
(|http://www.owl-ontologies.com/unnamed.owl#version|
?X) ("uml"))
(TOLD-VALUE (|http://www.owl-ontologies.com/unnamed.owl#identifyNumber|
?Y))
(?Y
|http://www.owl-ontologies.com/unnamed.owl#Project_9|)
(TOLD-VALUE
(|http://www.owl-ontologies.com/unnamed.owl#cost| ?Y))
((:TOLD-VALUE
(TOLD-VALUE (|http://www.owl-ontologies.com/unnamed.owl#duration| ?Y)))
(|http://www.owl-ontologies.com/unnamed.owl#identifyNumber|?Y))(456))
(AND (?X |http://www.owl-ontologies.com/unnamed.owl#Conceptual|)
((:TOLD-VALUE
(?X
(min |http://www.owl-ontologies.com/unnamed.owl#developmentPeriod| 30))
?Y)) (30000.0))
(?X(|http://www.owl-ontologies.com/unnamed.owl#cost|
?Y |http://www.owl-ontologies.com/unnamed.owl#related|)))
((:TOLD-VALU
(|http://www.owl-ontologies.com/unnamed.owl#duration|?Y))(“16:27:26"))))
Casi di Studio
Compito A del 19/12/2005 (2/3)
Seconda query
Per ogni schema logico di dimensione maggiore di 100, si vogliono
conoscere il tempo di sviluppo, ed il costo del relativo progetto.
RETRIEVE
(?X
(TOLD-VALUE (|http://www.owl-ontologies.com/unnamed.owl#developmentPeriod|?X))
?Y
(TOLD-VALUE (|http://www.owl-ontologies.com/unnamed.owl#cost| ?Y))))
(AND (?X |http://www.owl-ontologies.com/unnamed.owl#Logical|)
(?X (MIN |http://www.owl-ontologies.com/unnamed.owl#size| 100))
(?X ?Y |http://www.owl-ontologies.com/unnamed.owl#related|)))
> (((?X |http://www.owl-ontologies.com/unnamed.owl#Logical_10|)
((:TOLD-VALUE(|http://www.owl-ontologies.com/unnamed.owl#developmentPeriod| ?X))
(24))
(?Y |http://www.owl-ontologies.com/unnamed.owl#Project_3|)
((:TOLD-VALUE (|http://www.owl-ontologies.com/unnamed.owl#cost| ?Y))(15000.0))))
Casi di Studio
Compito A del 19/12/2005 (3/3)
Terza query
Fornire la lista dei progetti per i quali è stato prodotto almeno uno schema
logico implementato in un DBMS per il quale almeno un committente del
relativo progetto non ha la licenza.
(RETRIEVE
(?X)
(AND (?X |http://www.owl-ontologies.com/unnamed.owl#Logical|)
(?X ?Y |http://www.owl-ontologies.com/unnamed.owl#layout|)
(?X ?Z |http://www.owl-ontologies.com/unnamed.owl#related|)
(?W ?Z |http://www.owl-ontologies.com/unnamed.owl#order|)
(NEG (?W ?Y
|http://www.owl-ontologies.com/unnamed.owl#permission|))))
> (((?X |http://www.owl-ontologies.com/unnamed.owl#Logical_13|)))
Quarta query
Produrre la lista di tutti i progetti il cui costo è inferiore al compenso totale
che hanno determinato per l'azienda, dove il compenso totale che un
progetto determina per l'azienda è semplicemente la somma dei compensi
erogati dai relativi committenti per quel progetto.
Non è possibile calcolare il compenso totale di un determinato progetto.
Conclusioni
RacerPro
• processa documenti OWL-DL (completezza computazionale e
decidibilità)
• implementa la DL ALCQHIR+
nRQL
• permette di esprimere le conjunctive query e query complesse
a partire da semplici atomi.
• supporta due tipi di negazione: classica negazione del vero e
NAF (non supportata da nessun linguaggio di query OWL).
• supporta ricerche complesse sui valori degli attributi di un
individuo (dominio concreto).
• supporta un’operatore di proiezione proiect-to.
• è un potente linguaggio di query OWL e RDF.
Conclusioni (2/2)
Grande potere espressivo
Limitato potere computazionale:
nei casi di studio abbiamo osservato che il
sistema non è in grado di dimostrare dei
fatti che sono veri in ogni modello della KB.
Il test di consistenza iniziale dell’ABox
limita il sistema, che non è in grado di
utilizzare delle KB molto grandi (non più di
10.000 individui).