A practical approach to hypothetical database queries
Department of Computer Science
Roskilde University, P.O.Box 260, DK-4000 Roskilde, Denmark
Hypothetical queries are queries
embedding hypotheses about the database. The embedded hypothesis in a
hypothetical query indicates, so to say, a state of the database
intended for the rest of the query. Thus the answer to a hypothetical
query h>q, with a hypothesis h,
is in principle the result of
evaluating q against the database revised with h.
In case h is
inconsistent with the database, query evaluation becomes a special
case of counterfactual reasoning. However, the possible worlds
semantics usually applied for this notion
is not relevant for database applications
due to reasons of inefficiency.
In this paper we discuss and
compare different approaches to hypothetical queries, paying
special attention to potentials for efficient evaluation. As
a central part of the paper we present and discuss our own approach
"counterfactual exceptions", which have the important property of,
as opposed to the other approaches discussed, requiring only minor
overhead in query evaluation. This approach is thus realistic for
practical implementation and use in environments supporting large
databases. The "price" for efficient evaluation is an altered
semantics, as compared to the other approaches. However, it can be
argued that this semantics is at least as appropriate for database
applications as that of the other approaches mentioned.
Freitag, B., Decker, H., Kifer, M.,
Voronkov, A. (eds.),
"Transactions and Change in Logic Databases"
Lecture Notes in Artificial Intelligence 1472,
Springer-Verlag, pp. 340-356, 1998.