From: Richard Fikes (fikes@ksl.stanford.edu)
Date: 06/18/02
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". Richard
This archive was generated by hypermail 2.1.4 : 06/18/02 EDT