Re: DQL semantics

From: Richard Fikes (
Date: 03/12/02

> A preliminary proposal for a formalisation of the semantics of DQL can
> be found at:

I haven't been able to generate this message in time for it to be read
before the telecon, but I thought I would send it along now anyway so
that we can all have it in front of us for the discussion.  

I think your DQL semantics document is useful and important.  I, also,
am accustomed to thinking of the truth value of a sentence containing
variables to be defined in terms of mappings of the variables in the
sentence to objects in the domain of discourse (rather than to names in
the vocabulary of the knowledge base).

Regarding Partial Bindings --

Your comment that achieving partial bindings can be achieved by making
one of more of the variables no longer distinguished is formally true
but impractical.  That is, if there are n distinguished variables in a
query and each answer is required to have non-nil bindings for all of
the distinguished variables, then a client would have to ask the query
with as many as (2**n)-1 different sets of distinguished variables in
order to obtain all the bindings that the server could provide.  For
example, consider a case in which a query contains three distinguished
variables ?x, ?y, and ?z, and the server replies that it has no answer
sets (i.e., no answer which has a named binding for ?x, ?y, and ?z). 
How is the client to find out whether the server can say whether there
are any answers and what the bindings are for the variables in those
answers?  The client would need to ask the query with each possible
subset of the three variables designated as distinguished.  There are
some "cuts" in that process in that if there are no answers for a given
subset S, then there will be no answers for subsets that include all the
variables in S, but such a process of repeatedly asking the query is not

My conclusion is that we do indeed need to allow an answer to include
null bindings for distinguished variables.

Regarding the question of whether a tuple containing null binding(s)
should be allowed in an answer set that contains a more-specific answer,
I think not.  However, there is an ordering issue to be considered. 
That is, the server may produce the less-specific answer before the
more-specific answer.  Since we don't want a server to be required to
produce all of its answers before returning any of them, we have to
allow the server to return each answer as it produces it.  We can do
that by saying that the server is not allowed to produce an answer that
is less specific than any of the answers it has already produced, but
that it is allowed to produce an answer that is more specific than an
answer it has already produced.  (Note that this introduces a problem
regarding the "how many" question addressed below.)

Regarding the question of whether an answer set should be allowed to
contain multiple answers that differ only in that they use different
"null" bindings.  No.  I think we should support only one "null" binding
and that every answer in an answer set must be distinct  (i.e., no two
answers can have the same binding (including "null") for every

Regarding Size of Answers --

I think it is fine to consider "size of answers" (or, as I would prefer
to say "number of answers") in terms of the number of answers in the
answer set.  We need to decide where that information fits into the DQL
language (e.g., can a client ask for "number of answers" of a given
query?  Can a client ask "how many more answers are there to the
query"?  Can a server give a range (i.e., an upper and lower bound) as
an answer?), and whether we count less-specific answers returned before
more-specific answers.

That's it for now.  We'll talk in a few minutes.


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