W3C home > Mailing lists > Public > public-rif-wg@w3.org > May 2006

RE: RIFRAF analysis for DLV

From: Boley, Harold <Harold.Boley@nrc-cnrc.gc.ca>
Date: Tue, 23 May 2006 19:16:01 -0400
Message-ID: <E4D07AB09F5F044299333C8D0FEB45E9023AFCB2@nrccenexb1.nrc.ca>
To: <public-rif-wg@w3.org>

Axel and all,

This refers to http://www.w3.org/2005/rules/wg/track/actions/25 and
http://lists.w3.org/Archives/Public/public-rif-wg/2006May/0197.html,
http://lists.w3.org/Archives/Public/public-rif-wg/2006May/0198.html
(to your former email, explicitly; to your latter one, implicitly).


Most Discriminators you are missing go beyond Phase 1, but the RIFRAF
has already been extended towards Phase 2 through Hassan's email
(http://lists.w3.org/Archives/Public/public-rif-wg/2006May/0179.html,
 http://lists.w3.org/Archives/Public/public-rif-wg/2006May/0184.html).
However, it would make sense to keep a Phase 1 / Phase 2 distinction
with (or within certain values of) the Discriminators.


> Syn: Syntactic Discriminators
>   . . .
>      --> comment axel: Also concerning the recent mailinglist
>          discussions I miss an own category for typed vs.
>          untyped variables in the RIFRAF classification.

I agree, could be spliced in thus:

1. Restricted vs. Unrestricted Use of Logic Variables
2. Typed vs. Untyped Variables
   * Types can reuse class definitions in RDFS and OWL
3. Predicate Variables Permitted vs. Not Permitted


>   SYN.1.3. (FURTHER RESTRICTIONS FROM STATIC ANALYSIS RESEARCH)
>
>      --> comment axel: unclear, please explain?

E.g.: Allowing vs. Not Allowing Body-Only Variables


> SYN.3. MONOTONIC LLOYD-TOPOR EXTENSIONS ALLOWED VS. NOT ALLOWED
>   . . .
>       --> comment axel: this shows us that there rewritings
>        beyond extensions of Lloyd-Topor, which also allow
>        formulae in the rule head. Has not been considered
>        in current RAF, but might be worthwhile at least for phase 2

The rule head can be a formula such as  head1 AND head2:
http://www.w3.org/Submission/SWSF-SWSL/#swsl-rules-mon-lt


> SES.1. HOMOGENEOUS (BODY HAS SINGLE EXPRESSIVENESS CLASS) VS. HYBRID
(BODY
>      HAS TWO EXPRESSIVENESS CLASSES) RULES
>   . . .
>   --> comment axel: however, I am not sure whether this discriminator
is
>       really applicable, in principle, what Harold mentioned in his
>       comment to Hassan:
>           "'constraints' (e.g., solved by DL engines) goals."
>       are achievable by dlvhex predicates.
>
>   --> comment axel (alternative):  In case this refers to the terms
>       homogeneous vs. heterogeneous ontology integration as described
in
>       http://rewerse.net/deliverables/m12/i3-d3.pdf
>       (which would IMO probably be the better discriminator here,
>       I'd reformulate this as follows:

It is meant in the sense of the REWERSE deliverable m12, and the
heterogeneous option is further explained as splitting the body into
'resolution' goals and 'constraint' goals, where the latter are
delegated to a decidable solver (e.g., an OWL-DL engine).


>   --> comment axel: I didn't find anything on binding patterns in the
>       descriminators, but most systems which support interpreted
>       functions support such different binding patterns,
>       e.g. that the interpreted function X = Y + Z is used with the
>       binding patterns  "bfb","bbf","fbb", where "b" stands for
>       'bound' and "f" for 'free'. Probably this should be added in
>       the discriminators for interpreted functions?

Such 'mode declarations' are most useful when interpreted functions
are used but can also be helpful for relations such as to restrict
the invertibility of Prolog's append. However, since modes are an
'extra-logical' feature, they should go to PRAGMATIC DISCRIMINATORS.
They may be especially useful for specifying partial interchange/
interoperation: a target system may accept rules only in a submode
(with more "b" arguments) of their definitions in a source system.


>   SES.4.1. VARIABLE-FUL (NON-GROUND) VS. VARIABLE-FREE (GROUND) FACTS
>            (ALSO UNDER "FACT-ONLY ... BASES")
>   . . .
>     --> comment axel: there seems to be an overlap with this
>         discriminator with SYN1.2 and SES2.1

It is the same as SES2.1 since these are orthogonal Discriminators
(see also MichaelK's taxonomy lattice). Also overlaps with SYN1.2


>   SES.7.1. LABELS ALLOWED VS. NOT ALLOWED AS ARGUMENTS OF USER
PREDICATES
>   . . .
>   --> comment axel: Please clarify this criterion! If you mean named
>       attributes in relations, I don't see this as a subcriterion
>       of labels for rules.
>       What exactly is meant by "user predicates"?

This is the basic option to use names of clauses ('labels') as
arguments of predicates in clauses (some systems may also allow:
as arguments of functions). Example (prioritized Nixon diamond):
http://www.w3.org/Submission/SWSF-SWSL/#swsl-rules-courteous
If the 'overrides' predicate of a fact like overrides(rep,qua) is
a "user predicate" in the intended sense, then the definition of
overrides can be specified not only by providing such ground
facts, but also by providing rules, say for a limited form of
'overrides' transitivity or for conditional overriding.


>    SES.7.2. LABELS ALLOWED VS. NOT ALLOWED AS ARGUMENTS OF 
> PRIORITY-GIVING SYSTEM PREDICATE 'OVERRIDES' (CF. SCLP)
>   . . .
>    --> comment axel: Please clarify this criterion! The current
>        formulation seems to suggest a particular framerwork for
>        modeling preferences/priorities, while as we see for instance
in
>        the example there are many options for this.

If the 'overrides' predicate of a fact like overrides(rep,qua) is
a "system predicate" in the intended sense, then the definition of
'overrides' can only be specified by ground facts, so hard-coded
axioms for, say, standard transitivity have to be employed.


>   SEM.1. TERMINATING (ALL QUERIES TERMINATE) VS. NON-TERMINATING (AT 
> LEAST ONE QUERY DOES NOT TERMINATE) RULEBASES
>   . . .
>        --> comment axel: obviously even simple interpreted functions
can
>        cause non-termination even for a datalog based engine, which
>        makes such syntactic restrictions useful. In what way will
>        we be able to describe such syntactic restrictions in RIF?
>        It is probably important to also be able to exchange
>        such syntactic restrictions (which e.g. prohibit certain uses
of
>        recursvie rules in a formally defined way.

Cf. the Eighth International Workshop on Termination (WST 2006):
http://www.cs.mu.oz.au/wst2006
Annotating rulebases with results of static (termination) analysis
appears to be a good example of using metadata / semantic attributes
(see PHASE 1, section 9., of the F2F2 Preliminary Design Roadmap at
http://lists.w3.org/Archives/Public/public-rif-wg/2006Feb/0255.html).


>   PRAG.1.2. INCREMENTAL VS. EXHAUSTIVE
>   . . .
>   --> comment axel: I am not sure about how this criterion fits to
>       forward-chaining but several answer sets.  If it concerns the
>       strategy of forward-chaining evaluation, then I'd say. However,
>       DLV incrementally computes all stable models,
>       i.e. incrementally, whereas one could also compute ALL and only
>       give the cautious entailments in ALL stable models.

I meant one-solution-at-a-time (for finite and infinite models) vs.
all-solutions-at-once (for finite models) for backward-chaining, but
it could be broadened to also encompass DLV's approach to incremental
forward-chaining etc.


>   PRAG.3.2. TEST CASES
>   . . .
>    --> comment axel: I am not sure what you put here, at least
>    "test cases" do not seem to be a proper "discriminator", unless
>    you put a set of several practical test caes and ask: "Can this be
>    expressed/solved in your rule language/engine?" I.e. the WG should
>    provide these test cases derived from these discriminators, yes?

Right, the test cases of various systems will be hard to compare, but
the WG could encourage work on an increasing set of shared test cases.


>   PRAG.3.3. MAPPINGS
>   . . .
>   --> comment axel: ???? I still don't really sure to understand that
>       criterion, even after Harold's comment: "Does the system have
>       pre-defined mappings between various of it own sublanguages?"
>       Please clarify if I misinterpreted this.

You interpreted it as I had intended: Mapping a language's syntactic
extensions back to its core looks like the most important 3.3.1. case.


>     PRAG.3.3.1. WITHIN EXPRESSIVE EQUIVALENCE CLASSES ("CLUSTERS")
>
>    --> comment axel: ???? see above.

See above.


>     PRAG.3.3.2. BETWEEN EXPRESSIVE EQUIVALENCE CLASSES (IMPERFECT OR
>     "LOSSY")

>     --> comment axel: ???? see above. I think for some extensions this
>       discriminator cannot be answered yes or no. Depends how you
>       define lossy/imperfect.

Let me expand 'lossy/imperfect' to 'with unavoidable information loss':
E.g., mappings from the Horn logic (with Unfixed Function Nesting Depth)
class to the Datalog class entail some unavoidable information loss.
Yet, such approximative mappings may be relevant to prepare partial
interchange/interoperation with another, less expressive, language.


>  PRAG.3.4. (FURTHER INTEROPERABILITY DISCRIMINATORS SHOULD GO HERE)
>
> --> comment axel: Features, I didn't find a category for:
>
> - preference/priorities of rules:  DLV's weak constraint and several
>    other ASP extensions supports  a certain kind of preference
definition
>    between rule derivations, which can be adopted in case of
conflicting
>    conclusions. I'd assume that this is an important feature also
>    supported by other rule languages? (P.S.: priorization/preference
>    frameworks for rules probably would deserve an own ontology to be
>    analyzed in this WG, although for sure not in phase 1)

This seems to be a different priorization approach than the one in
SES.7.1.


> - Aggregates: In which discriminator do features such as the use of
>    aggregates in rule bodies (e.g. sum/avg/max/min)  go? (yes, this is
>    also probably phase 2)

The charter's "3.2.6. Knowledge Base Access" primitives as well as
the cwm/SWRL/Forum built-ins and XQuery and XPath Functions and
Operators
(http://www.w3.org/TR/xpath-functions) for arithmetics etc. should be
reconsidered as Discriminators.


-- Harold
Received on Tuesday, 23 May 2006 23:16:14 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 2 June 2009 18:33:29 GMT