A practical approach to hypothetical database queries

Troels Andreasen and Henning Christiansen
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.
See pdf.