Re: (DQL) Expressiveness of Query Patterns

From: Richard Fikes (
Date: 11/30/01

> >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.
> I'm happy with that, but I'm surprised that you are. For example, 
> this would rule out queries about the immediate superclass of a 
> class, or about the numbers of different answers, and so on.

We indeed will need to add on capabilities for "immediate superclass of
a class", "numbers of different answers", etc.  I am becoming
increasingly concerned that we do not have agreement on even the basics
of DQL, and so I am focusing on one piece at a time.  The query pattern
and the bindings seem to be a core place to start.  Note that in the
above I didn't say that a query *is* a query pattern, I said that a
query *contains* a query pattern.  

> >Let's focus here only on issues related to the expressive power of the
> >query pattern.  I proposed that we define the query pattern language so
> >that a query pattern specifies a conjunction of RDF statements
> >containing variables.  A query pattern instance would then specify a
> >collection of RDF statements that are entailed by the query KB.
> Entailed in RDF or in DAML+OIL?

Entailed in DAML+OIL.

> But in any case, this seems wrong-headed. Why a conjunction of RDF 
> statements? Wouldn't it be more fitting for us to have a conjunction 
> of DAML+OIL statements? After all, arbitrary conjunctions of RDF have 
> almost nothing to do with DAML+OIL: they might not encode any 
> DAML+OIL, and quite a lot of DAML+OIL, when encoded in RDF, is not 
> validly RDF-entailed (as Peter pointed out recently).

This issue came up in the telecon this week.

The first sentence of the "Introductory remarks" section of the
reference description for DAML+OIL
( says: "A DAML+OIL knowledge
base is a collection of RDF triples."

I mean for a query pattern to specify a conjunction of DAML+OIL
sentences.  I thought since a DAML+OIL knowledge base is a collection of
RDF triples that an appropriate form for the query pattern is a set of
triples corresponding to RDF statements with variables.  If you disagree
with that, propose an alternative.  That is, what would "a conjunction
of DAML+OIL statements" look like?

In any case, I presume we agree that a query pattern is to be a
specification of a conjunction of DAML+OIL statements containing

> >In general, I don't think we should restrict the expressiveness of our
> >query language based on the capabilities of our reasoning algorithms.
> I strongly disagree. The entire philosophy of DAML+OIL has been to 
> take reasoning capability as a central guiding principle. There is no 
> other reason to even consider description logics, in fact: if we are 
> not concerned with reasoning efficiency, then full omega-order logic 
> provides a much more natural, compact and expressive notation. I 
> think we should retain processing efficiency as a central guiding 
> principle of the DAML+OIL 'class' of web logics.

Well, there is an issue here of goals.  I am interested in designing a
query-answering language and protocol for DAML+OIL that will be
generally useful for the Semantic Web.  Almost no one outside the KR&R
community cares about logical completeness or tractability in most
cases.  The typical application needs to be able to effectively retrieve
information from a knowledge base and have the retrieval operation be
able to make simple inferences from the information in the associated
ontologies.  We don't want to force people to reformulate simple queries
into class membership or subsumption queries or to interpret results
stated in those terms.

Also, as soon as we expand the expressiveness of DAML to include some
kinds of rules, I expect that most of the formal reasoning results will
be inapplicable.  So, I think that a successful markup language for the
Semantic Web is indeed going to be sufficiently expressive to be
difficult to reason with and that a successful query language for the
Semantic Web is indeed going to allow one to express queries that are
extremely difficult or perhaps impossible to answer.  I don't think we
want to require that knowledge servers be able to answer any query that
is expressible, nor do we want to require them to be logically complete.

> I would suggest a different proposal. Let us adopt as a very simple 
> basic query format which the DL gurus know how to answer rapidly in a 
> guaranteed timeframe, eg the query of membership in a named class. 
> Then, let us invent a set of query/client protocols for encoding more 
> elaborate or subtle queries as 'conversations' made up of these 
> simpler queries, perhaps taking place in an order that is sensitive 
> to the replies gotten from earlier queries and perhaps involving the 
> maintenance of a temporary namespace to act as a common ground 
> between the server and client (which is now acting as a server for 
> the more elaborate querying process.) In this way, rather than invent 
> querying formats in the abstract, we can ensure that the more 
> elaborate queries are implementable; and, if we design the protocols 
> with care, that they have appropriate logical properties.
> For example, to find out how many things there are in a class, one 
> way might be to ask if it has any members; then ask the same question 
> about the class defined by the intersection of the previous class 
> with the complement of the set of members found so far. This might 
> iterate for a while, of course, but if it terminates then you have a 
> list of the members. And the client/server agent could, for example, 
> be delivering those answers to its client in real time, as it finds 
> them on its server.

The floor is open to alternative proposals.  I would encourage you to
turn the sketch above into a specific detailed proposal for the
committee's consideration.


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