Nonmonotonic Databases and Epistemic Queries

Abstract

The approach to database query evaluation developed by Levesque and Reiter treats databases as first order theories, and queries as formulas of the language which includes, in addition to the language of the database, an epistemic modal operator . In this epistemic query language, one can express questions not only about the external world described by the database, but also about the database itselfabout what the database knows. On the other hand, epistemic formulas are used in knowledge representation for the purpose of expressing defaults. Autoepistemic logic is the best known epistemic nonmonotonic formalism· the logic of grounded knowledge, proposed rec~ntly by Lin and Shoham, is another such system. This paper brings these two directions of research together. We describe a new version of the Lin/Shoham logic, similar in spirit to the Levesque/Reiter theory of epistemic queries. Using this formalism, we can give meaning to epistemic queries in the context of nonmonotonic databases, including logic programs with negation as failure.