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(a)gmail.com>
Hi Edson,
2009/4/17 Edson Tirelli <tirelli(a)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(a)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(a)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(a)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(a)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(a)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(a)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(a)yahoo.com> wrote:
>>>> >>>>
>>>> >>>> > From: Greg Barton <greg_barton(a)yahoo.com>
>>>> >>>> > Subject: Re: [rules-users] Negation semantics in
Drools
>>>> >>>> > To: "Rules Users List"
<rules-users(a)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(a)post.com>
>>>> >>>> > wrote:
>>>> >>>> >
>>>> >>>> > > We need to investigate if that is still
happening
>>>> >>>> > in
>>>> >>>> > > latest trunk.
>>>> >>>> >
>>>> >>>> >
>>>> >>>> >
>>>> >>>> > _______________________________________________
>>>> >>>> > rules-users mailing list
>>>> >>>> > rules-users(a)lists.jboss.org
>>>> >>>> >
https://lists.jboss.org/mailman/listinfo/rules-users
>>>> >>>>
>>>> >>>>
>>>> >>>>
>>>> >>>> _______________________________________________
>>>> >>>> rules-users mailing list
>>>> >>>> rules-users(a)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(a)lists.jboss.org
>>>> >>>
https://lists.jboss.org/mailman/listinfo/rules-users
>>>> >>>
>>>> >>
>>>> >>
>>>> >> _______________________________________________
>>>> >> rules-users mailing list
>>>> >> rules-users(a)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(a)lists.jboss.org
>>>> >
https://lists.jboss.org/mailman/listinfo/rules-users
>>>> >
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> rules-users mailing list
>>>> rules-users(a)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(a)lists.jboss.org
>>>
https://lists.jboss.org/mailman/listinfo/rules-users
>>>
>>>
>>
>> _______________________________________________
>> rules-users mailing list
>> rules-users(a)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(a)lists.jboss.org
>
https://lists.jboss.org/mailman/listinfo/rules-users
>
>
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
--
Edson Tirelli
JBoss Drools Core Development
JBoss, a division of Red Hat @