[rules-users] Negation semantics in Drools
Edson Tirelli
tirelli at post.com
Sat Apr 18 09:06:55 EDT 2009
Hi Paul,
"We are interested in measuring the performance for a set of features
that are considered important for the Semantic Web (computing logical
models, dynamic updates, joins or relations, recursion rules, persistent
data, etc.)."
That is what I wanted to understand.
Anyway, I will take a look at your benchmark docs and code and check if
we can contribute in any way, as soon as we get 5.0 out of the door.
[]s
Edson
2009/4/18 Paul Fodor <paul.i.fodor at gmail.com>
> Hi Edson,
>
> 2009/4/17 Edson Tirelli <tirelli at post.com>
>
>>
>>
>> Paul,
>>
>> I am not an expert on logic programming, but in this case, your example
>> is negating a goal (not a fact) in the backward chaining:
>>
>> win(X):- move(X,Y), not(win(Y)).
>>
>> Pure forward chaining systems don't have goals, since they are data
>> driven.
>>
>> I don't think this would be a good or fair comparison because it is
>> comparing a native concept in one side and an emulated concept in the other
>> side. If you were negating an actual fact, the comparison would be more an
>> apples-to-apples comparison.
>>
>
> From the logic point of view, win/2 and move/2 are both literals (atoms, if
> no explicit negation is used) and we define clauses (which can be
> facts or rules). The logical semantics (well-founded model theory or stable
> model semantics) makes no distinction between the negation of a literal
> move/2 (defined through a set of facts) and the negation of a literal win/2
> (which is defined through a recursive rule).
>
> These are declarative semantics and have nothing to do with the operational
> semantics (how to actually compute them).
> There are forward chaining systems (such as: DLV, OntoBroker from
> Ontoprise, IRIS) that compute them as well as some top-down systems (tabled
> XSB, Yap).
>
> We are interested in measuring the performance for a set of features
> that are considered important for the Semantic Web (computing logical
> models, dynamic updates, joins or relations, recursion rules, persistent
> data, etc.). For all these features we wanted to test the technology for
> rule systems (production rule systems were one of the technologies we
> studied). I agree that production rule systems are more fit for other
> tasks (for instance, reactive rules), but we wanted to see if they can be
> easily used for the Semantic Web tasks. For each feature that we tested, we
> tried our best to represent it in the best way for every given system. We
> are always open to sugestions of other banchmarks to test.
>
> Regards,
> Paul
>
>
>>
>> Just my .02c
>>
>>
>> Edson
>>
>> 2009/4/17 Paul Fodor <paul.i.fodor at gmail.com>
>>
>>> Now, I am curious. What is the background on this exercise? There
>>>> are some problems that are better suited for backward and others better
>>>> suited for forward chaining. Most problems would be modeled in very
>>>> different ways in each technology.
>>>
>>>
>>> It is just a set of tests we made in a suite of benchmarks. We wanted
>>> compare and benchmark both the different the technologies and various rule
>>> systems.
>>>
>>>
>>>> If we were just searching for the solution, it would just be the case
>>>> of writing (in forward chaining) one or two rules that would provide the
>>>> correct answer. But since this seems to be an academic exercise, I am
>>>> curious to understand the goals of it so that we can properly model it.
>>>
>>>
>>> The goal of this particular test (and our other stratified or
>>> non-stratified tests) was to see how efficient are implementations of
>>> default negation in rule systems. Programs using negation can be very
>>> various, but we tried to come up with a bunch of standard classic problems
>>> and implemented them in the best way possible in each rule system.
>>>
>>> You are right that each technology has its own strong and weak points
>>> depending on the tasks intended to solve. Even the way of implementing each
>>> particular task differs a lot on various rule systems.
>>>
>>> Regards,
>>> Paul.
>>>
>>>
>>>> Cheers,
>>>
>>>
>>>> Edson
>>>>
>>>> 2009/4/17 Paul Fodor <paul.i.fodor at gmail.com>
>>>>
>>>>> Hi Edson,
>>>>>
>>>>> The "insertLogical" doesn't work for non-stratified programs.
>>>>> For instance, in the win-nowin example, if there is a move(1,2) and
>>>>> a move(2,1), the order in which the two facts are inserted determines the
>>>>> final model (please see hte tests below).
>>>>>
>>>>> In logic programming, this example has two stable models: {win(1)} and
>>>>> {win(2)}, or a well-founded model {} (win(1) and win(2) are both undefined).
>>>>>
>>>>> Regards,
>>>>> Paul.
>>>>> *
>>>>>
>>>>> package
>>>>> *tests;
>>>>>
>>>>> *
>>>>>
>>>>> import
>>>>> *tests.Test.Win;*
>>>>>
>>>>> import
>>>>> *tests.Test.Move;
>>>>>
>>>>> *
>>>>>
>>>>> rule
>>>>> *"direct"
>>>>>
>>>>> *when*
>>>>>
>>>>> m : Move(x : first, y : second)
>>>>>
>>>>> *not* Win(first == y)
>>>>>
>>>>> *then*
>>>>>
>>>>> *insertLogical*(*new* Win(m.getFirst()));*
>>>>>
>>>>> end
>>>>> *
>>>>>
>>>>> move
>>>>>
>>>>> 1
>>>>>
>>>>> 2
>>>>>
>>>>> move
>>>>>
>>>>> 2
>>>>>
>>>>> 1
>>>>>
>>>>> Test:
>>>>>
>>>>> reading rulefile: win.drl ...
>>>>>
>>>>> reading datafile: win_upper3_drools.drools ...
>>>>>
>>>>> loading cputime: 0.016
>>>>>
>>>>> loading walltime: 0.016
>>>>>
>>>>> calculating ...
>>>>>
>>>>> computing cputime: 0.0
>>>>>
>>>>> computing walltime: 0.0040
>>>>>
>>>>> Derived facts in memory:move(1, 2).
>>>>>
>>>>> win(2).
>>>>>
>>>>> move(2, 1).
>>>>>
>>>>> 3
>>>>>
>>>>> move
>>>>>
>>>>> 2
>>>>>
>>>>> 1
>>>>>
>>>>> move
>>>>>
>>>>> 1
>>>>>
>>>>> 2
>>>>>
>>>>> Test:
>>>>>
>>>>> reading rulefile: win.drl ...
>>>>>
>>>>> reading datafile: win_upper4_drools.drools ...
>>>>>
>>>>> loading cputime: 0.016
>>>>>
>>>>> loading walltime: 0.016
>>>>>
>>>>> calculating ...
>>>>>
>>>>> computing cputime: 0.0
>>>>>
>>>>> computing walltime: 0.0040
>>>>>
>>>>> Derived facts in memory:move(2, 1).
>>>>>
>>>>> win(1).
>>>>>
>>>>> move(1, 2).
>>>>>
>>>>> 3
>>>>>
>>>>> 2009/4/17 Edson Tirelli <tirelli at post.com>
>>>>> >
>>>>> >
>>>>> > I did not had time to analyze what jess is doing, but note that
>>>>> what is important is the final answer. In your example, with Move(1,2) and
>>>>> Move(2,3), the final answer must be Win(2), right? And that is what Drools
>>>>> will answer, does not matter the order in which the data is entered into the
>>>>> engine.
>>>>> >
>>>>> > BUT, *very important*: the following construct in backward
>>>>> chaining:
>>>>> >
>>>>> > win(X):- move(X,Y), not(win(Y)).
>>>>> >
>>>>> > Is better represented in forward chaining using *logicalInsert*
>>>>> instead of a regular *insert*:
>>>>> >
>>>>> > rule "direct" % Drools
>>>>> >
>>>>> > when
>>>>> > m : Move(x : first, y : second)
>>>>> > not Win(first == y)
>>>>> > then
>>>>> > logicalInsert(new Win(m.getFirst()));
>>>>> > end
>>>>> >
>>>>> > Since in your backward chaining rule, only one win() predicate
>>>>> instantiation will remain true.
>>>>> >
>>>>> > So, even with differences in the reasoning algorithm, the answer
>>>>> is correct.
>>>>> >
>>>>> > Please explain further if I am missing anything.
>>>>> >
>>>>> > Edson
>>>>> >
>>>>> >
>>>>> > 2009/4/17 Paul Fodor <paul.i.fodor at gmail.com>
>>>>> >>
>>>>> >> Hi Edson, Greg,
>>>>> >> I don't think the rule is written wrong. This is how the win-nowin
>>>>> program is written in logic programming: X wins if there is a move from X to
>>>>> some Y and Y doesn't win:
>>>>> >>
>>>>> >> win(X):- move(X,Y), not(win(Y)).
>>>>> >>
>>>>> >> rule "direct" % Drools
>>>>> >>
>>>>> >> when
>>>>> >> m : Move(x : first, y : second)
>>>>> >> not Win(first == y)
>>>>> >> then
>>>>> >> insert(new Win(m.getFirst()));
>>>>> >> end
>>>>> >>
>>>>> >> I think that it's interesting that, in Jess (another production rule
>>>>> system), the stratified model is always computed right, no matter what was
>>>>> the order of the facts in the database. If you want to take a look, please
>>>>> see the equivalent program in Jess for win-nowin that I attached. Just run
>>>>> it with:
>>>>> >> jess test.clp
>>>>> >>
>>>>> >> win_upper1_jess.jess
>>>>> >>
>>>>> >> (move (cur 1) (next 2))
>>>>> >> (move (cur 1) (next 3))
>>>>> >> (move (cur 2) (next 4))
>>>>> >> (move (cur 2) (next 5))
>>>>> >> ...
>>>>> >>
>>>>> >> win_upper2_jess.jess
>>>>> >>
>>>>> >> (move (cur 2) (next 4))
>>>>> >> (move (cur 2) (next 5))
>>>>> >> (move (cur 1) (next 2))
>>>>> >> (move (cur 1) (next 3))
>>>>> >> ...
>>>>> >>
>>>>> >> test.clp:
>>>>> >>
>>>>> >> (deftemplate move (slot cur) (slot next))
>>>>> >> (deftemplate win (slot val))
>>>>> >>
>>>>> >> (defrule find_win
>>>>> >> (move (cur ?cur) (next ?next))
>>>>> >> (not (win (val ?next)))
>>>>> >> =>
>>>>> >> (assert (win (val ?cur)))
>>>>> >> )
>>>>> >>
>>>>> >> (defquery query-win
>>>>> >> (win (val ?val))
>>>>> >> )
>>>>> >> (open "win_result.txt" output a)
>>>>> >> (printout output ./win_upper1_jess.jess crlf)
>>>>> >> (reset)
>>>>> >> (load-facts "./win_upper1_jess.jess")
>>>>> >> (bind ?tmx (call java.lang.management.ManagementFactory
>>>>> getThreadMXBean))
>>>>> >> (deffunction cputime () (return (* (?tmx getCurrentThreadCpuTime)
>>>>> 1E-9)))
>>>>> >> (bind ?starttime_wall (time))
>>>>> >> (bind ?starttime_cpu (cputime))
>>>>> >> (run)
>>>>> >> (bind ?query_result (run-query* query-win))
>>>>> >> (bind ?count 0)
>>>>> >> (while (?query_result next)
>>>>> >> (++ ?count)
>>>>> >> )
>>>>> >> (printout output "solutions: " ?count crlf)
>>>>> >> (bind ?endtime_cpu (cputime))
>>>>> >> (bind ?endtime_wall (time))
>>>>> >> (bind ?walltime (- ?endtime_wall ?starttime_wall))
>>>>> >> (bind ?cputime (- ?endtime_cpu ?starttime_cpu))
>>>>> >> (printout output "computing cputime: " ?cputime crlf)
>>>>> >> (printout output "computing walltime: " ?walltime crlf)
>>>>> >> (close output)
>>>>> >>
>>>>> >> Regards,
>>>>> >> Paul Fodor.
>>>>> >>
>>>>> >> 2009/4/16 Edson Tirelli <tirelli at post.com>
>>>>> >>>
>>>>> >>> Ha, thanks a lot Greg. I need new glasses... he is actually
>>>>> comparing with the parameter "second", but when creating the win fact, using
>>>>> the parameter "first".
>>>>> >>>
>>>>> >>> not Win(first == m.second)
>>>>> >>> insert(new Win(m.first));
>>>>> >>>
>>>>> >>> Yes, in this case the engine is working exactly as it should.
>>>>> >>>
>>>>> >>> Anyway, I added the (fixed) test case to the codebase, just in
>>>>> case. :)
>>>>> >>>
>>>>> >>> Thanks,
>>>>> >>> Edson
>>>>> >>>
>>>>> >>> 2009/4/16 Greg Barton <greg_barton at yahoo.com>
>>>>> >>>>
>>>>> >>>> You don't have to worry. The engine is acting as it should.
>>>>> >>>>
>>>>> >>>> The rule Paul had was this, a bit simplified for clarity:
>>>>> >>>>
>>>>> >>>> rule "direct"
>>>>> >>>> when
>>>>> >>>> m : Move()
>>>>> >>>> not Win(first == m.second)
>>>>> >>>> then
>>>>> >>>> insert(new Win(m.first));
>>>>> >>>> end
>>>>> >>>>
>>>>> >>>> If the insertion order is [Move(1,2), Move(2,3)] then the rule
>>>>> matches first on Move(2,3) and Win(2) is inserted. No other rule fires
>>>>> because now Move(1,2) and Win(2) match up, removing the instantiation with
>>>>> Move(1,2) from the agenda.
>>>>> >>>>
>>>>> >>>> If the insertion order is [Move(2,3), Move(1,2)] then the order is
>>>>> this:
>>>>> >>>>
>>>>> >>>> matched Move(1,2) insert Win(1)
>>>>> >>>> matched Move(2,3) insert Win(2)
>>>>> >>>>
>>>>> >>>> The insertion of Win(1) in the first firing does NOT prevent the
>>>>> instantiation with Move(2,3) from then firing.
>>>>> >>>>
>>>>> >>>> So it's all good. :) Sample code and output attached.
>>>>> >>>>
>>>>> >>>> --- On Thu, 4/16/09, Greg Barton <greg_barton at yahoo.com> wrote:
>>>>> >>>>
>>>>> >>>> > From: Greg Barton <greg_barton at yahoo.com>
>>>>> >>>> > Subject: Re: [rules-users] Negation semantics in Drools
>>>>> >>>> > To: "Rules Users List" <rules-users at lists.jboss.org>
>>>>> >>>> > Date: Thursday, April 16, 2009, 8:50 PM
>>>>> >>>> > It is on the latest snapshot release,
>>>>> >>>> > 5.0.0.20090417.005612-483
>>>>> >>>> >
>>>>> >>>> > --- On Thu, 4/16/09, Edson Tirelli <tirelli at post.com>
>>>>> >>>> > wrote:
>>>>> >>>> >
>>>>> >>>> > > We need to investigate if that is still happening
>>>>> >>>> > in
>>>>> >>>> > > latest trunk.
>>>>> >>>> >
>>>>> >>>> >
>>>>> >>>> >
>>>>> >>>> > _______________________________________________
>>>>> >>>> > rules-users mailing list
>>>>> >>>> > rules-users at lists.jboss.org
>>>>> >>>> > https://lists.jboss.org/mailman/listinfo/rules-users
>>>>> >>>>
>>>>> >>>>
>>>>> >>>>
>>>>> >>>> _______________________________________________
>>>>> >>>> rules-users mailing list
>>>>> >>>> rules-users at lists.jboss.org
>>>>> >>>> https://lists.jboss.org/mailman/listinfo/rules-users
>>>>> >>>>
>>>>> >>>
>>>>> >>>
>>>>> >>>
>>>>> >>> --
>>>>> >>> Edson Tirelli
>>>>> >>> JBoss Drools Core Development
>>>>> >>> JBoss, a division of Red Hat @ www.jboss.com
>>>>> >>>
>>>>> >>> _______________________________________________
>>>>> >>> rules-users mailing list
>>>>> >>> rules-users at lists.jboss.org
>>>>> >>> https://lists.jboss.org/mailman/listinfo/rules-users
>>>>> >>>
>>>>> >>
>>>>> >>
>>>>> >> _______________________________________________
>>>>> >> rules-users mailing list
>>>>> >> rules-users at lists.jboss.org
>>>>> >> https://lists.jboss.org/mailman/listinfo/rules-users
>>>>> >>
>>>>> >
>>>>> >
>>>>> >
>>>>> > --
>>>>> > Edson Tirelli
>>>>> > JBoss Drools Core Development
>>>>> > JBoss, a division of Red Hat @ www.jboss.com
>>>>> >
>>>>> > _______________________________________________
>>>>> > rules-users mailing list
>>>>> > rules-users at lists.jboss.org
>>>>> > https://lists.jboss.org/mailman/listinfo/rules-users
>>>>> >
>>>>>
>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> rules-users mailing list
>>>>> rules-users at lists.jboss.org
>>>>> https://lists.jboss.org/mailman/listinfo/rules-users
>>>>>
>>>>>
>>>>
>>>>
>>>> --
>>>> Edson Tirelli
>>>> JBoss Drools Core Development
>>>> JBoss, a division of Red Hat @ www.jboss.com
>>>>
>>>> _______________________________________________
>>>> rules-users mailing list
>>>> rules-users at lists.jboss.org
>>>> https://lists.jboss.org/mailman/listinfo/rules-users
>>>>
>>>>
>>>
>>> _______________________________________________
>>> rules-users mailing list
>>> rules-users at lists.jboss.org
>>> https://lists.jboss.org/mailman/listinfo/rules-users
>>>
>>>
>>
>>
>> --
>> Edson Tirelli
>> JBoss Drools Core Development
>> JBoss, a division of Red Hat @ www.jboss.com
>>
>> _______________________________________________
>> rules-users mailing list
>> rules-users at lists.jboss.org
>> https://lists.jboss.org/mailman/listinfo/rules-users
>>
>>
>
> _______________________________________________
> rules-users mailing list
> rules-users at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>
>
--
Edson Tirelli
JBoss Drools Core Development
JBoss, a division of Red Hat @ www.jboss.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.jboss.org/pipermail/rules-users/attachments/20090418/efa261a1/attachment.html
More information about the rules-users
mailing list