Re: CWM Bug: Rules That Strip Quantification

On Nov 11, 2007 8:15 AM, Sean B. Palmer <sean@miscoranda.com> wrote:

> On the other hand, the quantification and implication in N3 and CWM
> seem to be modelled very strongly after First Order Predicate Logic,

I've since done some research, and the best two statements on this
situation I've found are as follows:

[[[
There's a trick to making RDF rules be Horn-expressive instead of
merely datalog-expressive with only a slight change in the rules
language.  We use this trick in cwm/n3, and I used it in some
unpublished pre-w3c work.  I've mentioned it before (in proposals I
wouldn't exactly support any more) [1] [2], but I still haven't come
up with any proper references.

The idea is this: if an RDF rule is a pair of RDF graphs (the
body/antecedent and the head/consequent), with certain nodes/arcs in
the graph marked as variables (just like in DQL), then we only have
datalog rules.  If, however, we also allow nodes/arcs in the
consequent to be marked as existential variables in the scope of the
consequent, we have Horn expressivity.
]]] - http://www.daml.org/listarchive/joint-committee/1237.html

(Old, though, being from 2002.)

[[[
We do not expect rule engines or other rule processing systems (such
as editors) to handle even a large set of the features standardized by
this Working Group. There are many viable rule languages and rule
engines which do not handle even all the Phase 1 features. (In
particular, it is common to implement only function-free Horn Logic
(Datalog), which is has a finite deductive closure.)
]]] - http://www.w3.org/2005/rules/wg/charter.html#conformance

Which suggests that there is a decidable level of expressivity,
datalog, and an undecidable level of expressivity, Horn Logic, and
that CWM kinda implements both in some way. I also found this:

[[[
TimBL: should we support --datalog in cwm?
<DanC> (seems like a reasonable idea, but I don't see any specific
benefit that motivates me to write the RFE)
]]] - http://www.policyawareweb.org/2005/pf-dev/09-28-paw-minutes

Which suggests that it's possible to add a mode to cwm to restrict it
to only those rules which are decidable. Cf. also what Yosi wrote
recently about lean graphs:

[[[
When writing cwm's rule engine, the decision was made to try to not
entail redundant triples. A set of triples is redundant if the graph
after those triples are added is rdf-entailed by the graph
beforehand. Because of this, the following will not loop forever

echo '{?x ?p ?y} => {[] ?p []} . :a :b :c . ' | cwm --think
]]] - http://lists.w3.org/Archives/Public/public-cwm-bugs/2007Oct/0015

Which seems like it's related, but I'm not sure how.

JHendler dropped by #swig and commented on the SWIG Scratchpad posting
of this bug, saying that there's some paper due out about how CWM
works:

[[[
hendler: There is a new paper coming soon on the semantics of N3 in a
more operational way -- I was looking for a pointer from Dig or arxiv
but couldn't find it
hendler: will try to get it posted at dig
]]] - http://swig.xmlhack.com/2007/11/11/2007-11-11.html#1194768958.252283

Which might be one of those papers that I've personally overheard
mention of in DIG circles. I'd certainly be very grateful if that
paper were to be posted on Breadcrumbs, as I think JHendler was
suggesting he'd try to make happen.

-- 
Sean B. Palmer, http://inamidst.com/sbp/

Received on Sunday, 11 November 2007 10:06:07 UTC