Scaling Up Reasoning about Actions Using Relational Database Technology

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 19

Knowledge Representation and Reasoning

Reiter’s variant of the Situation Calculus is tightly related to relational databases, when complete information on the initial situation is available. In particular, the information on the initial situation can be seen as a relational database, and actions, as specified by the preconditions and successor state axioms, can be seen as operations that change the state of the database. In this paper, we show how to exploit such a correspondence to build systems for reasoning about actions based on standard relational database technology. Indeed, by exploiting standard relational DBMS services, a system may be able to perform both Projection, exploiting DBMS querying services, and Progression, exploiting DBMS update services, in very large action theories. A key result towards such a realization, is that under very natural conditions Reiter’s basic action theories turn out to be made of “safe formulas” (where basically negation is used as a form of difference between predicates only) and that regression and progression preserve such a safeness. This is a fundamental property to efficiently exploit relational database technology for reasoning. We then show that, even when action theories are not “safe”, they can be made so while trying to retain efficiency as much as possible. Finally, we briefly discuss how such results can be extended to certain forms of incomplete information.