'null' Bindings in DQL Answers

From: Richard Fikes (fikes@ksl.stanford.edu)
Date: 06/18/02

  • Next message: Jeff Heflin: "Re: Joint Committee telecon tomorrow 18 June"
    Pat and Ian and I are in the middle of a discussion involving 'null'
    bindings in DQL answers.  That discussion won't come to a consensus in
    the next half hour, so I am forwarding to the committee the proposal on
    the table as input for our telecon discussion.  As before, I don't
    necessarily expect you to have digested the proposal before the telecon,
    but having the message to refer to should help facilitate the
    discussion.  Here are excerpts from a message from me containing the
    proposal --
    As Pat and I discussed week before last when he was here, I would very
    much like for us to find some way of including in DQL the notion that a
    query answering server could return a query answer corresponding to any
    successful proof that it finds of the query pattern, even when the proof
    does not produce a term in the KB Herbrand universe as a binding for
    every distinguished variable in the query pattern.  By doing so, we
    would both allow an answer to be produced whenever a server can prove
    that an answer exists, and it would give more substance to this whole
    DQL effort.  On that second point, it seems to me that if we restrict
    answers to be ones that have terms in the KB Herbrand universe as
    bindings for all of the distinguished variables, that DQL then becomes a
    rather mundane contribution to deductive query answering.  Perhaps that
    is all we can produce, but then again, it would be satisfying if we got
    a more significant result of this rather extended effort.
    (The following is a proposal that I mentioned awhile back.  Pat
    responded positively at the time, but we didn't pursue it seriously.)
    As background, the issue is specifying what answers a server is to
    produce for a DQL query.  The problem we have encountered is that if we
    allow answers to contain bindings of distinguished variables to 'null',
    then when a server finds an answer that contains one or more bindings to
    'null', it, in general, doesn't know whether it will find an answer
    later that is more specific than the answer it has just found.  Thus,
    the set of answers to a query would then seem to be dependent on the
    order in which they are produced.
    The proposal is to allow answers to contain bindings of distinguished
    variables to 'null', and let the server return any answer it finds that
    is not the same as or less specific than the previous answers it has
    returned.  (which is an easy filter for the server to apply before
    returning an answer)
    The primary problem we had with that proposal was how to formalize what
    the answer set is for a query, because what answers any given server
    will produce is dependent on the order in which it generates the
    answers.  Here is the formalization that I proposed to deal with that
    problem.  Define a "super answer set" to be the set of all the answers
    to a query that are entailed by the KB unioned with the less-specific
    versions of each of those answers (e.g., if [?x/a ?y/b] is an answer in
    the super answer set, then [?x/null ?y/b], [?x/a ?y/null], and [?x/null
    ?y/null] are also in that set).  Then define the "minimal answer set" to
    be the subset of the "super answer set" in which no answer subsumes any
    other answer.  Finally, simply require the answers produced by a server
    to be a subset of the "super answer set".  The formal semantics would
    specify the "minimal answer set" and the "super answer set" is a
    straightforward extension of the "minimal answer set".

    This archive was generated by hypermail 2.1.4 : 06/18/02 EDT