Leopold Franzens
Universität Innsbruck
Technical Fair
Reasoning
Barry Bishop
DERI Innsbruck – University of Innsbruck
Technical Fair
 Copyright 2007
DERI Innsbruck
www.deri.at
11th December 2007
Introduction
•
•
•
•
2
The reasoning group
Achievements over the last year (or so)
Recent progress
Future plans
Technical Fair
11th December 2007
The Reasoning Group
Barry Bishop
Uwe Keller
Chair/Software
Engineer
PhD Researcher
Nathalie
Steinmetz
Graduate
Researcher
Stijn Heymans
Graham Hench
Holger Lausen
Post-doc
Researcher
Software
Engineer
PhD Student
Florian Fischer
Richard Pöttler
Undergraduate
Software
Engineer
The Reasoning Group meet every 2 weeks to co-ordinate project tasks and push
forward the development of DERI software components
3
Technical Fair
11th December 2007
Established components
• Integrated Rule Inference System (IRIS)
–
–
–
–
safe Datalog
default negation
built-in predicates
WSML (XML-Schema) data types
Join
p(X,Z) :- q(X,Y), r(X), s(Z), X != Y
path(X,Y) :- path(X,Z), path(Z,Y)
diff(X) :- q(X), not r(X)
Set difference of q and r
4
Technical Fair
11th December 2007
Built-in predicate
Transitive closure
Established components
• WSML2Reasoner
– a framework for all WSML language variants
WSML2Reasoner
WSML-Core
WSML-Flight
WSML-Rule
WSML-DL
WSML-Full
(any)
IRIS
MINS
KAON2
TPTP
Pellet
5
Technical Fair
11th December 2007
Established components
• RDFSReasoner
–
–
–
–
6
framework for reasoning over RDFS graphs
executes WSML conjunctive queries
RDF, RDFS and eRDFS entailment regimes
uses IRIS as the underlying reasoning engine
Technical Fair
11th December 2007
Evaluating Datalog
• Evaulating pure Datalog is straightforward,
because
– there is no negation, function symbols or built-in
predicates
– when starting with a finite set of facts, a finite
minimal model is guaranteed
– all programs can be evaluated
• However, IRIS is more sophisticated!
7
Technical Fair
11th December 2007
Evaluating Datalog
• IRIS supports more data types
– Datalog has only integer and string
– WSML has all the XML schema types
• Now we have some ambiguity:
p(X,Y) :- q(X,Y), X = 2
p(2,Y) :- q(2,Y)
(what‘s the difference?)
8
Technical Fair
11th December 2007
Evaluating Datalog
• Built-in predicates (e.g. EQUALS, LESS, ADD, etc)
• Test for safe rules requires that every variable that
occurs in a built-in also occurs in a non-negated
ordinary body predicate (or is equated with one)
e.g.
p(X,Y) :- q(X), X < Y
is not safe.
9
Technical Fair
11th December 2007
Evaluating Datalog
• However, it can be useful to relax this rule, e.g.
p(Z) :- q(X,Y), X+Y=Z
• But beware:
p(0)
p(Y) :- p(X), X+1=Y
does not converge! (More about this later)
10
Technical Fair
11th December 2007
Evaluating Datalog
• NEGATION
– Monotonicity – essential to know at each evaluation
step, that any new fact is always true.
p(X) :- r(X), not s(X)
s(X) :- t(X)
– Requires that the second rule is evaluated before
the first rule.
– This layering of rules is called STRATIFICATION
(More about this later)
11
Technical Fair
11th December 2007
Evaluating Datalog
• Computing the fixed point is expensive!
• Although, when answering a query such as
?- p(?X,?Y)
the fixed point computation will have to be done
anyway.
• However, when the query contains constants, e.g.
?- p('a', ?Y)
then an optimisation is possible: Magic Sets
12
Technical Fair
11th December 2007
Evaluating Datalog
• Magic sets
– This technique generates a modified program in
order to take advantage of constants in the query
– A bottom-up evaluation procedure is used to
evaluate the new program
13
Technical Fair
11th December 2007
Evaluating Datalog
Magic sets example
Before:
sg(?X, ?X) :- person(?X).
sg(?X, ?Y) :- parent(?X, ?Xp), sg(?Xp, ?Yp), parent(?Y, ?Yp).
?- sg('a', ?W).
After:
m_sg('a').
m_sg(?Xp) :- sup2_1(?X, ?Xp).
sup2_1(?X,?Xp) :- m_sg(?X), parent(?X, ?Xp).
sg(?X, ?X) :- m_sg(?X), person(?X).
sg(?X, ?Y) :- sup2_1(?X, ?Xp), sg(?Xp, ?Yp), parent(?Y, ?Yp).
?- sg('a', ?W).
14
Technical Fair
11th December 2007
Recent Work
• Stabilisation of IRIS
– more unit/functional tests
• fixing bugs found
– identifying undefined behaviour
• built-ins with incompatible data types
• negated built-ins
– documentation
• design (UML)
• user guide
15
Technical Fair
11th December 2007
Recent Work
• Locally Stratified Negation
– a rule has a negative dependency on itself, BUT
– the input and output of the rule are partitioned due to
the presence of constants, e.g.
p('a',X) :- r(X), ¬ p('b',X)
Add a tuple (a,X) in to p if X is in r, but not if (b,X) is in p
16
Technical Fair
11th December 2007
Recent Work
• Why is local stratification important?
– because of how WSML is evaluated, e.g.
axiom isSingle definedBy
?x[family_status hasValue single] :?x memberOf Human and naf ( ?x[married_to hasValue ?y] )
– is translated in to datalog as:
_has_values(?x, 'family_status', 'single') :_member_of(?x, 'Human'), ¬ _has_values(?x, 'married_to', ?y)
17
Technical Fair
11th December 2007
Recent Work
• Locally stratified negation – trickier example
p('a',X) :- r(X), not q('b',X)
q(X,Y) :- p(X,Y)
– Which rule should be evaluated first?
– What are the strata?
• IRIS re-writes these rules to:
Stratum 0:
Stratum 1:
18
q('b',Y) :- p('b',Y)
p('a',X) :- r(X), not q('b',X)
q(X,Y) :- p(X,Y), X != 'b'
Technical Fair
11th December 2007
Recent Work
• Query Containment
– is a reasoning related task
• Will the results of query q1 contain the results of
query q2? Always?
• Query containment could be used in web service
discovery:
– Plug-in (goal is completely achieved)
– Subsumption (goal subsumes web-service)
– Exact match
19
Technical Fair
11th December 2007
Recent Work
• Query Containment
– The current algorithm (frozen fact*) is limited to
positive datalog only
– Further work will produce an algorithm that also
works in the presence of negation
*This algorithm is presented in Ramakrishnan, R., Y. Sagiv, J. D. Ullman and M. Y. Vardi
(1989). Proof-Tree Transformation Theorems and their Applications. 8th ACM
Symposium on Principles of Database Systems, pp. 172 - 181, Philadelphia
20
Technical Fair
11th December 2007
Recent Work
• Query extensions
– Formal languages group have specified a query
language called WSML-Flight-A
– Implemented using post-processing on
WSML2Reasoner
SELECT ?place, COUNT(*)
FROM _"file:/C:/deri/workspace/WSMLQuery/test/files/the-simpsons-ontology.wsml"
WHERE ?employee[hasWorkingPlace hasValue ?place]
ORDER BY COUNT(*) DESC
GROUP BY ?place
HAVING COUNT(*) > 1
PLACE
springfield_elementary
channel_6
nuclear_plant
21
COUNT(*)
6
5
4
Technical Fair
11th December 2007
Recent Work
• Reasoning over external data sources
• Motivation:
– Not convenient to all include instance data in a
WSML document
– To answer a query, the reasoner may not need all
instance data
– Impossible to provide all instance data when the
data set is very large
– Allows reasoner to use data in any format
22
Technical Fair
11th December 2007
Recent Work
Overview at the WSML layer
WSML Document
ontologies, web
services, goals,
mediators...
ExternalDataSource
HasValue[] hasValue(IRI id, IRI name, Term value)
MemberOf[] memberOf(IRI id, IRI concept)
WSMLReasoner
UserDataSourceClass
Queries
23
Technical Fair
11th December 2007
Future Work
• Reminder
– WSML language variants:
• different levels of logical expressiveness and
• different languages paradigms
– WSML-Core, -Flight and -Rule can be evaluated
using Datalog
• Core Function free and negation free
• Flight With inequality and locally stratified negation
• Rule Unsafe/unstratified rules and function symbols
24
Technical Fair
11th December 2007
Future Work
• Concentrate on WSML-Rule
– Function symbols
– Unsafe rules
– Unstratified logic programs
• Continue evolution of framework
– Plug-ins
• Program optimisers
• Storage algorithms
• Evaluation strategies
– Description Logics
– Rule Interchange Format (RIF)
25
Technical Fair
11th December 2007
Future Work
• Function Symbols
– A generalisation of Datalog
– Extra work for storage and selection of facts
– Required for WSML-Rule
axiom aaMapingRule14 definedBy
mediated1(?X11,Name)[lName hasValue ?Y12] memberOf Name
:?X11[o1#hasLastName hasValue ?Y12] memberOf o1#person
and ?X11 memberOf ?SC13
and mappedConcepts(?SC13,Name).
26
Technical Fair
11th December 2007
Future Work
• Without function symbols
– straightforward to match tuples in a relation, e.g.
p(X,Y) :- q(X,Y), r(X,2), s(Y,Y)
Everything
Tuples whose two terms are equal
Tuples whose last term is 2
• With function symbols
– term matching is harder, e.g.
p(f(X),Y) :- q(g(X), h(X,Y))
27
Relation Q
match
q(g(1), h(1, 2))
X=1, Y=2
q(g(1), h(2, 2))
no match
q(g(k(3)), h(k(3), m(2,3)))
X=k(3), Y=m(2,3)
Technical Fair
11th December 2007
Future Work
• With function symbols, safe rules can have an
infinite minimal model:
p(f(X)) :- p(X)
• Which is the same convergence problem as before!
• Possible solutions
– time constraint
– space constraint
– complexity constraint
28
Technical Fair
11th December 2007
Future Work
• Stratified Logic Programs
– Have acyclic negation
– Have a unique minimal model
– Have an intuitive meaning
• Unstratified Logic Programs
– Often do not have a clear meaning
– Often have several minimal models or a minimal
model that is the empty set
• WSML-Rule allows unsafe and unstratified rules
29
Technical Fair
11th December 2007
Future Work
• Stable-model semantics
– Gives meaningful results to some programs
– However, some programs have no stable model, e.g.
p(X) :- not p(X)
(odd loop)
– And some programs have two stable models, e.g.
p(X) :- not q(X)
q(X) :- not p(X)
(even loop)
(hinting at disjunctive information)
– Worst of all, computationally hard!
30
Technical Fair
11th December 2007
Future Work
• Well-founded semantics
– Every rule set has a unique well-founded model
– Several published evaluation techniques
– However, even loops give an empty set (no
disjunction)
• Interesting papers:
– Kemp, Stuckey and Srivastava on well-founded
semantics and magic sets
– Zukowski, alternative computation of well-founded
semantics
31
Technical Fair
11th December 2007
Summary
• Over the last 18 months much has been achieved
– Datalog reasoner created
– Framework for reasoning with RDFS and WSML
• However, there is much more to do
– Function symbols – end of February 2008
– Unsafe/unstratified programs – end of March 2008
• Target
– a complete in house WSML-Rule reasoner by start
of April at the latest (bye-bye MINS)
32
Technical Fair
11th December 2007
Descargar

Slide 1