Hypothetical queries to deductive databases

Troels Andreasen, 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, which must be taken into account during evaluation. In principle, the answer to a hypothetical query h>q with a hypothesis h is 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. In this paper we discuss and compare different approaches to hypothetical queries. We pay in this context 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, as opposed to the other approaches discussed, to require only minor overhead in query evaluation. This approach is thus realistic for implementation in environments supporting large databases. The "price" for efficient evaluation is an altered semantics, as compared to the other approaches. However, we will argue that our semantics is at least as appropriate for database applications.

Eds. Geske, U., Ruiz, C., Seipel, D., Proc. of the 5th International Workshop on Deductive Databases and Logic Programming. Workshop in Conjunction with ICLP'97, Leuven, Belgium, July 11, 1997. GMD-Studien 317, GMD-Forschungszentrum, Informationstechnik GMBH, pp. 37-48, 1997.