Re: Query Language Issues

From: Harold Boley (boley@informatik.uni-kl.de)
Date: 11/13/01


Richard,

since you asked for more feedback, here are just a few comments:

> What follows is a proposal for discussion for how to handle query
> answers that include bindings to constants created by the server.  Such
> constants would either be the labels of anonymous RDF nodes or Skolem
> constants that denote objects whose existence is entailed (e.g., by
> cardinality restrictions).

Maybe these "created constants" should be better called "existentially
quantified variables" from the outset, as you do later when discussing
semantics. Operationally, they may be "created anonymous variables".
They may come with (implicit?) disequality constraints, corresponding to
the unique name assumption for named constants.

> It seems to me that the use of a single <blank> binding in query answers
> is inadequate.  What I would suggest is needed is a vocabulary of blank
> bindings, say <blank-1>, <blank-2>, ..., that can be used as bindings in
> query answers and that have the semantics of existentially quantified
> variables.  Such a vocabulary would be used in our example as follows:

> A query result of [[x/blank-1 y/blank-2]] would mean that the following
> sentence is entailed by the query KB:
> 
>    (exists b1 b2) (P b1 & RC b2 & O b1 b2)

Adding the disequality constraint blank-1 <> blank-2, with "<>" being the
disequality infix, you would give us the more precise

     (exists b1 b2) (P b1 & RC b2 & O b1 b2 & b1 <> b2)

or
     (exists b1 <> b2) (P b1 & RC b2 & O b1 b2)

> If the only requirement in the query is that each set of bindings is
> unique (rather than each set of objects denoted by the bindings), then
> the server could generate any number of answers by simply using
> different blank-i bindings.

That requirement could be handled by implicit disequality constraints
over all pairs of blank-i variables.

> Uniqueness of Answers
> 
> In general, a query result may contain multiple query answers.
> 
> ISSUE: What guarantees do we want to make about the distinctiveness of
> multiple query answers in a query result?  We may want to guarantee that
> no two answers consist of identical sets of bindings.  That would say
> that if A1 and A2 are query answers in a query result, then there exists
> a query variable xi for which the binding for xi in A1 is not the same
> constant as the binding for xi in A2.  A more difficult guarantee would
> be that no two answers consist of equal sets of bindings.  That would
> say that if A1 and A2 are query answers in a query result, then there
> exists a query variable xi for which the binding for xi in A1 is not
> equal to (i.e., does not denote the same object as) the binding for xi
> in A2.
> 
> PROPOSAL:  We guarantee there are no identical sets of bindings and that
> we enable a query to include an indicator as to whether equal sets of
> bindings are acceptable.

Perhaps it's more convenient to talk about unique anonymous variables than
about unique sets of bindings.

Language constructs and implementation techniques for (explicit) disequality
constraints over variables were introduced in Prolog II by Alain Colmerauer
around 1982 (I have no convenient public URL handy). The ensuing field of
Constraint Logic Programming may be more generally relevant to the current
discussion of query languages.

Harold


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