Re: (DQL) Expressiveness of Query Patterns

From: Pat Hayes (
Date: 12/04/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.

Hmm, I don't like that strategy, as we never know quite what we are 
agreeing to. Lets have the overall design sorted out first and then 
get to the details.

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

Then I want to know what else it contains before agreeing on whether 
this is reasonable. For example, it may be that other aspects of the 
query will require us to envision different kinds of binding.

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

Well then why not say that the pattern is a set of DAML+OIL 
statements? Why mention RDF at all?

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

OK, then just say that and leave it at that. Then if at any future 
time the relationship of DAML+OIL to RDF is changed, you won't have 
to rewrite the query spec.

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

That is a question that is to be settled by the designers of the 
language; but whatever the answer is, the query language should 
conform to it, and defining it to be DAML+OIL makes that 'tracking' 
automatic. Also, it makes the intent clearer, since not all sets of 
RDF triples are DAML+OIL; and moreover, it clarifies what it means to 
speak of DAML-entailment, which is well-defined for DAML+OIL but not 
(yet) well-defined for RDF.

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

OK, that reads much better :-)

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

OK, you are stating a different agenda (and one that I am myself 
sympathetic to) but it really is a DIFFERENT agenda than the one that 
has driven DAML+OIL so far. I worry that the resulting language is 
going to be a mixture of incoherent fragments driven by different, 
and divergent, agendas. I would prefer DAML+OIL development to be 
continued in the DL tradition, and if the WebOnt initiative feels 
that some other approach should be adopted, perhaps as an 
alternative, then another, different, intiative be begun to 
investigate that.

In any case, I think that many people are keenly interested in 
tractability, in fact, even though they might not call it that. And 
as for "logical completeness", I am not sure what you mean, but I am 
arguing for LESS logical expressiveness, not more.

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

Well, Richard, I tend to agree; but I am tempted to ask, why are you 
working on DAML+OIL?

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

I believe not, if we are careful.

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

Again, I tend to agree; but to pursue *that* ambition, we shouldn't 
be working on DAML+OIL; we ought to be working on something else.

>I don't think we
>want to require that knowledge servers be able to answer any query that
>is expressible,

I think that people will become rather upset if they find that 
queries are often unanswerable, and there is no guidance about how to 
make them answerable.

>nor do we want to require them to be logically complete.

Again, I really do not know what you mean by that in this context.

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

OK, but I will need some help with the DL details.


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