Re: Query Language Issues

From: Ian Horrocks (
Date: 11/15/01

A couple of additional points regarding the query language.

I am more and more convinced that we need to start simple and think
about extending the language only when we have built a firm
foundation. This general approach seems to have served us well up to

The additional point regarding cycles can be summarised as
follows. When there are no cycles in the non-distinguished variables,
queries can easily be "collapsed" into a single class and answered
using our standard reasoning services, e.g., a query of the form:

(x) <- Q(x,y) ^ R(y,z) ^ S(z,w)

can be reduced to:

(x) <- C(x)

where C is the class (hasClass Q (hasClass R (hasClass S
Thing))). Note that (an extended version of) the technique can still
be used when there are n distinguished variables.

This is not possible when there are cycles in the non-distinguished
variables, e.g., a query of the form:

(x) <- Q(x,y) ^ R(y,z) ^ S(z,y)

In less expressive languages one can overcome this problem by showing
that one (all) of the non-distinguished variables in a cycle must be
bound to named individuals, and so answer the query by using a non
deterministic identification and collapsing.

This is not, however, the case for DAML+OIL. In this case, it isn't
clear yet if/how one can answer such queries (but we are working on it
:-)). One way forward is to avoid the problem by simply forbidding such
cycles, but this of course makes the query language much less
expressive - in a certain sense, it then just becomes a fancy "user
interface" for our old friend realisation (tell me the members of
class C). A middle way is to try to restrict queries so the above
mentioned non-deterministic "trick" will still work, e.g., by
forbidding cycles with transitive properties (this may not be enough).

Some information on this can be found in the AAAI paper from Sergio
Tessaris and myself that I already mentioned, and in Sergio's thesis.

Regards, Ian

This archive was generated by hypermail 2.1.4 : 04/02/02 EST