DQL Description (for today's telecon)

From: Richard Fikes ([email protected])
Date: 02/05/02


Attached below is an informal description of DQL distilled from recent
message and telephone interchanges.  Although I take responsibility for
the description, it contains substantial ideas from multiple committee
members other than myself, primarily Pat.

I sent out a draft version of this description last evening and have had
feedback e-mails and a telephone discussion with Pat and have received
an e-mail response from Ian earlier today.  There has not yet been time
to have a feedback discussion with Ian.

I think that Pat and I agree in principle on this description.  Pat can
comment on the state of agreement in the telecon today.  There are still
some open issues with Ian.

I don't expect you to have read this message before the telecon, but we
can go through it together then.

Richard

---------------------

OVERVIEW

DQL will be a formal language and protocol for posing queries from a
querying agent (which we refer to as the "client") to an answering agent
(which we refer to as the "server").  A query contains a "query pattern"
that is a collection of DAML+OIL sentences in which literals and/or
resources have been replaced by variables.  A query includes a
specification of which of the variables in the query pattern are
designated as "distinguished variables".  We consider query-answering
using DQL to mean determining answers each of which includes a binding
for some or all of the distinguished variables such that the sentences
produced by applying the bindings to the query pattern and considering
the remaining variables in the query pattern to be existentially
quantified produces sentences that are entailed by the knowledge base
with respect to which the query was answered.

A query can optionally specify a DAML+OIL knowledge base that is
referred to as the "query KB".  If a query KB is specified in the query,
the query is considered to be posed with respect to that knowledge
base.  If no query KB is specified in the query, the server is free to
select a query KB.  It is presumed that a query-answering server will
provide information as to the knowledge bases it considers when
selecting a query KB and may also provide additional facilities for a
client to constrain and guide that choice.

Each binding in a query answer is either a literal or a URI that is
either explicitly mentioned in the query KB or is defined in DAML+OIL. 
That is, DQL is designed for answering queries of the form "What URIs or
literals from the vocabulary of the query KB denote objects that make
the query pattern true?"  Or, in the case that there are no
distinguished variables in the query pattern, the query is of the form:
"Is the query pattern true in the query KB?".


DETAILED SPECIFICATION

WHAT'S IN A QUERY

* Query Pattern - A query necessarily includes 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.   A query pattern is a collection of DAML+OIL sentences in
which some of the literals and resources have been replaced by
variables.

* Distinguished Variables - A query includes a specification of which of
the variables that occur in the query pattern are "distinguished
variables".  We refer to the variables in the query pattern that are not
distinguished variables as "undistinguished variables".

* Knowledge Base - A query can optionally include a URI for a DAML+OIL
knowledge base that is referred to as the "query KB".  If a query KB is
specified in the query, the query is considered to be posed with respect
to that knowledge base.  If no query KB is specified in the query, the
server is free to select a query KB.  It is presumed that a
query-answering server will provide information as to the knowledge
bases it considers when selecting a query KB and may also provide
additional facilities for a client to constrain and guide that choice.

* Query Premise - A query can optionally include a "query premise" to
facilitate if-then queries while still remaining within the
expressiveness of DAML+OIL.  A query premise is a URI for an arbitrary
DAML+OIL knowledge base.  When a query premise is specified, the
sentences in the query premise are considered to be included in the
query KB.

* Answer Justification Request - A query can optionally include a
request for a justification of each query answer.  The content and
structure of a justification for a query answer has not yet been
designed.  Options include a full proof, the premises used in the proof,
the source ontologies of the premises, that a certain property is true
of the source ontologies (e.g., that they were all warranted by a
certain authority, or had transaction dates later than some named date,
etc.).

  
WHAT'S IN A QUERY RESPONSE

A "query response" is either:

1. A special token 'none' indicating that there are no further answers
entailed by the query KB;

2. A special token 'unknown' indicating that the server cannot provide
any more answers, but that more answers may be entailed by the query KB;
or

3. A pair consisting of a "query answer" and a "server continuation".

A server continuation is an item which when returned to the server,
causes it to continue its query-answering process from the point where
it stopped when it produced the previous answer.

Each query answer contains a set of bindings for some or all of the
distinguished variables in the query pattern.  [Note: When multiple
answers for a query are produced, DQL does not impose any constraints
regarding the distinctiveness of the answers.  That is, a server can
produce the same answer to a query more than once.  We observe that a
protocol which does not produce duplicate answers could easily be
produced from the DQL protocol.] 

This protocol can be used in more elaborate querying protocols that find
all answers or the first N answers, etc., without thereby requiring all
query-answering servers 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.


WHAT'S IN A QUERY ANSWER

* Query Bindings - A query answer includes a set of "query bindings" for
some or all of the query pattern's distinguished variables.  Each
binding is to either a literal or a URI that is either explicitly
mentioned in the query KB or is defined in DAML+OIL.  An answer's query
bindings are such that (1) the sentences produced by applying the
bindings to the query pattern and considering the remaining variables in
the query pattern to be existentially quantified produces sentences that
are entailed by the knowledge base with respect to which the query was
answered, and (2) the query bindings include all the bindings for
distinguished variables that are extractable from the server's proof
that it would return if it were asked for a proof as a justification of
the answer.  The second requirement is a conformance requirement on a
DQL server to assure that servers are returning all the bindings that
they have.  

* Answer Justification - If the query included an answer justification
request, then a query answer would include an "answer justification".

* Query - A query answer includes the query to which it is an answer.

* Server - A query answer includes a URI identifying the server that
produced the answer.


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