Re: [iris-reasoner-support] Questions on Magic Sets

[Barry B. <bar...@st...>]

Hi Murat,

I'll do my best to answer these, but I ma not an expert on magic sets.

Murat Knecht wrote:
> Hi all,
> 
> once more, I have come up with some questions. Currently, I am looking 
> at the magic set implementation, so the questions mostly concern it.
> 
> 1. Conjunctive queries
> The following rules give different adorned predicates, since the order 
> of predicates in this case determines the adornments. In the following 
> example, the first rule (with the given query) produces four, while the 
> second rule produces just two adorned predicates of anc/2.
> 
>            anc(?x,?z) :- anc(?x,?y), par(?y,?z).     // 1.
>            anc(?x,?z) :- par(?x,?y), anc(?y,?z).     // 2.
>            ?-anc(?x, 'l3-1'), anc(?x, 'l3-2').
> 
> The difference between rule 1 and 2 in respect to the query ought to be 
> nullified by the SIP, which resides over the order of evaluation, right?

Not sure. If the rule body predicates have a different order, then I
would expect different bindings and therefore adornments.

> 2. AdornedProgram.createAdornedRules(Collection, IQuery)
> The method assumes there to be exactly one literal:
> 
> final ILiteral head_literal = rule.getHead().get(0);
> // ...
> adorned_rule = adorned_rule.replaceHeadLiteral(head_literal, 
> adorned_predicate);
> 
> Why is this? replaceHeadLiteral() could easily support more.
> Additionally, this generates a java.lang.IllegalArgumentException:
> 
>                      anc(?x,?y),blub(?y) :- anc(?y,?x).
>                      ?-anc('l1-1', ?z).

The reason that the object model for rules allow multiple head
predicates, is that we wanted to leave open the possibility that we
*might* one day extend IRIS to be a disjunctive Datalog reasoner.

Multiple rule body predicates are interpreted as being conjunctive,
whereas multiple head predicates (at least in Datalog type scenarios)
are interpreted as being disjunctive. If a conjunctive rule head is
required, one only needs two rules with the same body, but different
heads. Disjunctive rule heads is a whole new ball game, as it were.

So to answer your question, some algorithms make perfect sense for rules
with one or more rule head predicates, but some do not. At the moment,
IRIS does not allow it.


> 3. AdornedProgram.createAdornedRules(Collection,IQuery)
> Just a small coding question. With
> final Set<AdornedPredicate> predicatesToProcess = new 
> HashSet<AdornedPredicate>();
> you simulate a queue. Why not just use one?

Good question. It is used like a queue, but not quite, because the order
 of a set is determined to some degree by the hash code of its elements.
This is basically a rather suspect (but probably harmless)
implementation detail. A queue, list or something simpler would be more
appropriate.

> 4. Bug in OptimisedProgramStrategyAdaptor.evaluateQuery(IQuery, List) ?
> While applying optimizations, you iterate through the configured 
> optimizers. In my understanding, each optimizer gets the results of the 
> previous optimizations, i.e. rules and the query for which the rules are 
> being optimized, as in the case of magic sets. But in the crucial line, 
> you always fall back to the original rules (mRules) - though using the 
> possibly previously optimized query.
> 
>                 IProgramOptimisation.Result result = 
> optimisation.optimise( mRules, query );
> 
> Is this as intended?
> As far as I understand this, it probably never posed a problem, as there 
> is but one optimization available, the magic sets.

I looks very much like a bug to me. Thanks!

> 5. You often impose the limitation of rules having at most one head 
> literal. While queries with more predicates are simply conjunctively 
> connected (as they are a rule without head), are rules with multiple 
> disjunctively connected?

I think I answered this already:

Rule body literals are conjunctive
Rule head literals are disjunctive*

*but not allowed in IRIS (at the moment)

> Thanks and hoping to hear from you soon.

No problem. Thanks for your interest and for finding bugs for us!

Get in touch whenever you have questions,
barry