Re: (DQL) Expressiveness of Query Patterns

From: Richard Fikes (fikes@ksl.stanford.edu)
Date: 11/29/01


The telecon discussion on Tuesday suggested to me that we don't yet
agree on some fundamental notions involved in query-answering.  This
message is an attempt to move the discussion forward by focusing on some
of those fundamental issues.

I said the following in my last message on this topic:

> We seem to agree on the following: a query contains a "query pattern"
> that specifies relationships among unknown sets of objects in a domain
> of discourse.  Each unknown object is represented in the query pattern
> by a variable.  Answering a query with variables x1,,xn involves
> identifying tuples of term expressions such that for any such tuple 
> <c1,,cn>, if ci is substituted for xi in the query pattern for i=1,,n,
> then the resulting "query pattern instance" specifies a sentence that is
> entailed by the query KB.  For each such ci, the pair [xi, ci] is a
> binding for the corresponding variable xi.  Each set of such variable
> bindings specifies a candidate answer to the query.

Note that, in the above paragraph, I am considering query answering to
be a process of determining term expressions that denote objects in the
domain of discourse for which the relationships specified in a query
pattern hold.  Also, note that each query pattern instance produced by
substituting those expressions for variables in the query pattern is to
be a sentence entailed by the query KB.

A fundamental question is then what "term expressions" can serve as
bindings for variables in a query pattern.  I was earlier arguing for
allowing such bindings to be only names that are in the KB or in
DAML+OIL.  Then, query answering is a process of identifying objects in
the domain of discourse that are named in the KB or in DAML+OIL.

Our subsequent discussions have led us to consider allowing as legal
bindings to query variables in query answers place holders (i.e.,
blank-1, blank-2, ...) denoting objects that are unnamed in the KB but
which are either referred to in the KB anonymously or whose existence
can be entailed from the KB.  

So, do we allow anything else to be a binding of a query variable in a
query answer?  That is, do we allow an arbitrary term expression to be a
binding?  I would argue "no".  I think this is a design choice in that
what we decide here is fundamental to what we choose to mean by query
answering.  What I am recommending is that we do not allow a binding to
be anything other than a name or a blank-i place holder.  If that is
controversial, then let's have that discussion.


Another related issue --

In the telecon we discussed a query whose query pattern is "(subclassOf
?x C1)", i.e., "find ?x such that ?x is a subclass of class C1" and
which is asking for all answers.  As we know, there is no way of
determining all of the subclasses of a given class.  So, what do we want
such a query to mean?  Analogously, what do we want a query to mean
whose query pattern is "(ancesterOf ?x P1)", i.e., "find ?x such that ?x
is an ancestor of P1" (for the usual meaning of ancesterOf), and which
is asking for all answers?  Also, what do we want a query to mean whose
query pattern is "(siblingOf ?x P1)", i.e., "find ?x such that ?x is a
sibling of P1" (for the usual meaning of siblingOf), and which is asking
for all answers?

I am recommending that what we are asking the server for in such queries
are all the bindings >>that it can determine<<.  That is, a server may
know that S1 is a sibling of P1 and nothing more about the siblings of
P1, even if more information about the siblings of P1 is inferable from
the KB.  In that case, that server would return exactly one query answer
that identifies S1 as a sibling of P1.  Some other server when asked the
same query might return two query answers because it is able to identify
another sibling of P1 or to conclude that there are at least two such
siblings.  The same situation holds for the other two queries.  For
example, even though there are an arbitrary number of subclasses of C1,
a server can answer the query by returning a query answer for each
subclass of C1 that it can identify.

One might argue, that where the existence of an arbitrary number of
objects that could answer a query can be entailed (as with subClassOf
and ancesterOf), that the server could simply return an arbitrary number
of place holder bindings.  Without getting into the issue of whether we
will allow that to occur, I would simply comment that we will need to
have some way in general of dealing with the case in which a server can
produce an infinite number of answers to a query.  That mechanism
(whatever it turns out to be) would apply to the subClassOf and
ancesterOf case if we allow the server to produce an arbitrary number of
bindings sets that differ only in the names of the place holders.

Is this an acceptable notion of "find all answers"?  If not, how do we
otherwise express that typical query of "find all ?x that you can"?  

Richard


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