Re: notes by Benjamin from today's JC telecon on Rules Literequirements, expressiveness, work items, action plans, schedule

From: Harold Boley (boley@informatik.uni-kl.de)
Date: 08/09/03

• Next message: Frank van Harmelen: "Re: notes by Benjamin from today's JC telecon on Rules Lite requirements, expressiveness, work items, action plans, schedule"
```Hi Benjamin and All,

> issue: restrict to Datalog?  [Benj]

> - binary Horn FOL with possibly further restrictions

Binary Datalog is certainly a (modest) possibility.
It's also one of the RuleML sublanguages:

http://www.ruleml.org/dtd/0.8/ruleml-bindatalog.dtd

We defined it as a restriction of N-ary Datalog:

http://www.ruleml.org/dtd/0.8/ruleml-datalog.dtd

Bindatalog is currently prefix or postfix:

<!ELEMENT atom ((_opr, (ind | var), (ind | var))
| ((ind | var), (ind | var), _opr))>

This could be extended to infix:

<!ELEMENT atom ((_opr, (ind | var),       (ind | var))
| ((ind | var),       (ind | var), _opr))
| ((ind | var), _opr, (ind | var))>

> Harold:  possible issue of essential expressive limitation arising from
> combination of finite lists with binary relations
> - may not be able to show the general case of the usual reduction of
> n-ary to binary

I actually meant the following:

N-ary Datalog is closed w.r.t. bounded lists, since any
argument aI containing a list of fixed length L can be
'flattened' to a subsequence of L arguments (N=M+L-1):

aI
/----^----\
r(a1,...,[e1,...,eL],...,aM) --> r(a1,...,e1,...,eL,...,aM)

This can be continued recursively, for any eJ that is
again a bounded list, etc., down to a fixed depth D.

The result of such flattening of a given KB utilizing
"Datalog with bounded lists" still gives us an N-ary
Datalog KB.
(In practice 'bounded' means rest variables, like X
in [e1,...,eL|X], are forbidden on all list levels.)

A given binary Datalog KB, however, will not normally
be N=2 after flattening.
(I had exemplified a binary-to-ternary leap at the end of
http://www.daml.org/listarchive/joint-committee/1420.html.)

Best,
Harold
```

This archive was generated by hypermail 2.1.4 : 08/09/03 EST