Query continuations (was: Re: DQL Query Patterns and Variable Bindings)

From: Pat Hayes (phayes@ai.uwf.edu)
Date: 12/11/01

Here's a modification to Richard's suggestion for handling queries. 
Ive put into a separate message to keep message-bloat within bounds.


A query is an expression containing d-variables and nd-variables 
which would be legal DAML+OIL when appropriate bindings are made to 
the variables. (Same as Richard.)

An answer is a set of bindings to some of the d-variables, with the 
understanding that the expression got taking the existential closure 
of the expression got by applying those bindings to the query follows 
from the KB. An answer may be empty, which simply means that the 
existential closure of the query follows from the KB. Notice that 
there is no need to have a special 'blank' binding, with this 
convention.  (Pretty much same as Richard, particularly as it was me 
that insisted on the damn blanks in the first place.)

(The exact sense of 'follows from' has to be specified as part of the 
full specification of the query-answering process; for example, it 
may be understood in a rather narrow constructive sense to mean that 
some ground instance is constructively provable.)

A response (different from Richard) is (an indication of the KB and 
query, plus) either
1. a special token 'none' indicating that there are no further 
bindings to be found;  or
2. a pair consisting of an answer and a server continuation.

(Each answer indicates a distinct proof found by the KB, but there is 
no guarantee that each answer represents a distinct set of entities, 
so it is not in general valid to infer numbers of distinct answers 
from numbers of responses; the task of finding a set of semantically 
distinct answers is a different, quite complex inference process.)

A server continuation is an item which when returned to the server, 
causes it to continue the search for bindings at the point where it 
left off the search.

The idea is that this now allows some external agent to control more 
elaborate querying protocols, eg to find all answers, or all answers 
in batches, or the first N answers, etc.., without thereby requiring 
all KBs to maintain the machinery needed to support such 
functionality, and also keeping the basic querying language 
arithmetic-free. The only 'core' requirement on a server is that it 
be able to handle its own continuations, which need only record 
enough of the state of the search process to guarantee that they will 
not miss anything, which I think will usually be pretty easy; it 
amounts to a hash-coding of a position in the KB from which to 
continue a search.


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