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

Re: [RIF][UCR] Decidability a requirement?

From: Christian de Sainte Marie <csma@ilog.fr>
Date: Tue, 11 Apr 2006 15:49:23 +0200
Message-ID: <443BB3E3.60800@ilog.fr>
To: Dave Reynolds <der@hplb.hpl.hp.com>
CC: RIF WG <public-rif-wg@w3.org>
Dave Reynolds wrote:
> 
> Consider the problem of a person implementing a translator from RIF to 
> their own rule language. If their rule language is decidable (e.g. it is 
> a datalog engine) and there is *no* RIF dialect which is decidable then 
> they cannot implement RIF, period. They could implement a subset of some 
> nearby dialect but I presume the point of a dialect is to achieve 
> interoperability between some subset of rule languages and partial 
> implementations fail to achieve that.

It depends what you call "implementing RIF": if a compliant application 
has to be able to process any rule retrieved from a valid RIF document, 
then I agree with you. But, then, we may have to chose an even weaker 
subset than Datalog, and even so, we might still exclude many useful use 
cases (if I understood the discussion about production rules VS logic 
programming correctly, a production rule engine cannot handle all 
Datalog rulesets).

My understanding of implementing the RIF is rather that a compliant 
application is able to handle an valid RIF document in a predictable 
way: if an application than process a Datalog-like rule language DRL 
implements compliantly a RIF Core that covers Horn rules, including 
n-ary functions, all the rulesets that contain no n-ary function symbols 
will be just translated in DRL and processed by the application; but the 
implementer of the RIF-DRL translator must know what to do when it 
encounters a function in a retieved RIF document, and the producer of 
that RIF document must know what consummers will do if they cannot 
understand all the elements in the document. That is, the spec must tell 
them, or it must allow the producer to tell the consummer, or both. But 
the default behaviour must *not* set any constraint on the consummer 
rule language or rule processing capability.

That way, the burden of recognizing what rulesets it can handle is on 
the consummer application, not on the producer or the RIF specification.

> The question is not "should RIF be decidable", clearly there must be RIF 
> dialects which are undecidable.
> 
> The question is "should RIF Core be decidable". As far as I can 
> understand the charter and the term "extension", if RIF Core is 
> undecidable then *all* RIF dialects are undecidable which doesn't seem 
> ideal.
> 
> If RIF core is undecidable then either:
> 
> (a) the "extension" mechanism needs to include narrowings/constraints 
> which can reduce the expressibility of the core; and/or
> 
> (b) there needs to be some mechanism other than RIF Dialect (as 
> described on the terminology page) for subsetting RIF so that a provider 
> can scope the RIF fragment they are using narrowly enough that consumers 
> know that they can provide a complete implementation.

I propose that "don't know" behaviours as describe above could be such a 
mechanism. It seems to me that this is one way to avoid the RIF to end 
up being just a collection of incompatible dialects.

I added two proposed desing constraints reflecting that view.

To make the discussion more concrete, I also tried my hand at a simple 
XML schema for a kind-of-Horn-level RIF, extensible using the notion of 
substitution groups, and where two elements (the priority and function 
elements) have a "dontKnowBehaviour" (but, in my view, all or almost all 
elements should or must have one).

The attached schemas are sloppily edietd (because I do not know XML 
schema) from a attempt by Philippe Bonnard (who explained me the benefit 
of the extension groups for extensibility).

Could we discuss this further based on examples using this schema? (Or 
another one: if somebody has a preference, then, propose your schema 
along with your examples).

Cheers,

Christian



Received on Tuesday, 11 April 2006 13:52:01 GMT

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