From: Ian Horrocks ([email protected])
Date: 11/15/01
On November 15, Dan Connolly writes:
> Ian Horrocks wrote:
> [...]
> > 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).
>
> I find that pretty appealing, really.
Me too!
> I'm most interested in general-purpose RDF query and rules stuff;
> I've been wondering what a "DAML+OIL query language" would look
> like if it weren't a general-purpose RDF query langauge.
> The above is a pretty satisfying bumper-sticker description
> for a DAML+OIL query language.
>
>
> > 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.
>
> That sorta appeals to me, but after scratching my head
> for a few minutes, I don't quite get it.
>
> I would very much appreciate a tutorial on rewriting horn
> clauses as DAML+OIL descriptions.
The basic trick is this. Think of the query as a labelled directed
graph where each clause of the form R(x,y) is an R labelled edge from
x to y and each node x is labelled with a class formed from the
intersection of the classes Ci such that Ci(x) is a clause in the
query (or Thing if there are no such clauses). In the simple case, the
graph will be a tree. You can just start at leaf nodes and "roll up"
the query.
The basic transformation is as follows. If y is a leaf node labelled C,
y is a non-distinguished variable, there is an R labeled edge from x
to y, and x is labelled D, then you can eliminate y and the R-labelled
x-y edge and change the label on x to the intersection of D and the
restriction (hasClass R C). Pick (one of) the distinguished variable
as the root and repeat this transformation until only the root node is
left. The answer to the query is then just those instances of the
class labeling the root node.
If one of the non-root nodes is a distinguished variable (i.e., the
query returns n-ary tuples, with n>1), then you need to extend the
transformation. E.g., if the query returns <x,y>, then you can roll
the query up into x by inventing a fresh class name Py and including
that in the intersection when you roll up y. Say that the rolling up
produces a class C as the label of x, then a tuple <a,b> answers the
query iff the KB is unsatisfiable when you assert that a is of type
not C and b is of type Py. (You could just use a nominal, i.e.,
substitute the class (oneOf b) for Py in C, but reasoning with
nominals is hard, and the little trick with Py is sound and complete
due to the negation of C in the final test.)
If the query graph contains named individuals other than in the root
node, then you can deal with them via a similar trick to the one I
just mentioned (or using a nominal).
That is the rough idea (errors and omissions excluded!). You can find
more details in the AAAI paper [1] or DL paper [2] (probably enough
for what you will need), or even more in the thesis [3].
Regards, Ian
[1] http://www.cs.man.ac.uk/~horrocks/Publications/download/2000/AAAI-2000.ps.gz
[2] http://www.cs.man.ac.uk/~horrocks/Publications/download/2000/DL00-interfaces.ps.gz
[3] http://www.cs.man.ac.uk/~tessaris/papers/phd-thesis.ps.gz
>
> The tools I use (http://www.w3.org/2000/10/swap/) are pretty
> much rules-based, but I'm making an effort, lately, to replace
> application-specific rules ala:
>
> { :n1 a rm:external} log:implies
> { :n1 dot:color "grey5"; dot:shape "plaintext"}.
>
> with rules to capture DAML+OIL:
>
> # hasValue
> { :s a [ ont:onProperty :p; ont:hasValue :o ] }
> log:implies { :s :p :o }.
>
> and facts written in the DAML+OIL vocabulary:
>
> _:doesAnnoProto ont:onProperty rm:prototypes; ont:hasValue
> :annoteaProtocol.
> psum:AnnoteaClient u:subClassOf _:doesAnnoProto.
> psum:AnnoteaService u:subClassOf _:doesAnnoProto.
>
>
> but it takes significant mental energy to think this way,
> and I'm only able to do it in simple cases.
>
>
>
> --
> Dan Connolly, W3C http://www.w3.org/People/Connolly/
This archive was generated by hypermail 2.1.4 : 04/02/02 EST