Relating Database Updates to Nonmonotonic Reasoning

In this paper, we prove that the problem of updating (monotonic) deductive databases (both insertions and deletions) have simple, elegant analogs in nonmonotonic reasoning formalisms including both default and auto-epistemic logic. Subsequently, we show that the problem of updating nonmonotonic deductive databases can also be viewed in terms of such analogs. Thus, nonmonotonic reasoning paradigms provide a general declarative framework whereby a wide variety of database updating problems may be clearly specified. 1 Introduction There has been extensive work on the problem of realizing updates in deductive databases [6, 5, 9, 17, 4]. Perhaps one of the best-known attempts to formally characterize database updates is that of Fagin, et. al.[6, 5], who introduced the notion of a flock -- intuitively if a first order theory T (representing a database) is updated by inserting/deleting some fact, a flock is a set of theories that are minimally different from T , but which accomplish the desi..