This paper introduces an extension of Logic Programming which integrates queries and updates. The proposed language, "Hypothetical Datalog", provides an elegant tool for certain types of reasoning encountered in many applications, such as encountered in many applications, such as legal expert systems. Hypothetical reasoning allows capturing statements such as the following, from the British Nationality Act: "You are eligible for citizenship if your father would be eligible if he were still alive". Such statements are hard to capture with traditional tools; indeed, the semantics and proof theory of Hypothetical Datalog are based on intuitionistic logic. The resulting language provides new features which are very appealing in many applications. Moreover, perhaps surprisingly, Hypothetical Datalog is particularly well-behaved with respect to expressibility: natural syntactic restrictions of the language express the queries of data complexity EXPTIME, PSPACE, and each level of the polynomial hierarchy. These results involve particularly elegant and insightful simulations.
a service of  Schloss Dagstuhl - Leibniz Center for Informatics