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