Re: (DQL) Expressiveness of Query Patterns

From: Pat Hayes (
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".

Can you give some arguments for that position? What for example would 
be wrong with a query binding a variable to a term containing another 
variable? Why not just allow arbitrary unifications to occur when 
binding query variables?

>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.

I don't mean to argue against it, but Id like to see some justification for it.

>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.

Maybe I missed something at the telecon, but doesn't that depend on 
the class and what we know about it? If we know it is empty, for 
example, then its easy to answer the query.

>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<<.

But that could still be an infinite set if you ask for all ancestors, right?

BTW, I'm tempted to ask, determine *how*? (If it thought harder it 
might be able to some up with more answers, in general, right? How is 
it to know when it has finished trying, in general?)

>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.

But consider. Does it KNOW that it knows nothing more? If in fact it 
could infer something more, but has an explicit assertion that it 
does not know more, then it is inconsistent. If it does not have such 
an assertion, then how does it know when to stop looking for answers?

The standard closed-world assumptions used in databases short-circuit 
this problem, but it doesn't have an easy solution in general.

IHMC					(850)434 8903   home
40 South Alcaniz St.			(850)202 4416   office
Pensacola,  FL 32501			(850)202 4440   fax

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