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

So,

A consumer of an RIF document must have available enough information so that
they can recognize if they can handle the document or not or whom to pass it
on to so it can be processed.

If the consumer is an RIF language editor then chances are they are only
worried about the syntax and possible constructions - but they are a
consumer and a producer and worried about complying with the abilities of a
planned target consumer.  

If the consumer is an execution broker of some sort they must have enough
information available to recognize which "execution engine" to send the
document off to for processing.

The practical use of dialects should help us to make those decisions and
that seems to suggest that the dialects should be based on a classification
of existing systems if it is ever to be realized. Of course, there is some
room for stretching the existing systems, but the implied work to fit a
classification must be manageable.  

Can we build up the dialects out of modules of operations, one (or a
collection) of which captures decidability, and with the practical dialects
simply being appropriate collections of modules?

Stan Devitt

-----Original Message-----
From: public-rif-wg-request@w3.org [mailto:public-rif-wg-request@w3.org] On
Behalf Of Christian de Sainte Marie
Sent: Tuesday, April 11, 2006 3:52 PM
To: Dave Reynolds
Cc: RIF WG
Subject: Re: [RIF][UCR] Decidability a requirement?

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.
[SD] 
This is very important. 
[SD]
> 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 Wednesday, 12 April 2006 07:39:27 UTC