COMPUTING CIRCUMSCRIPTIVE DATABASES .1. THEORY AND ALGORITHMS

Though circumscription was introduced by McCarthy over a decade ago, t here has been relatively little work on algorithms for computing circu mscriptive databases. In this paper, we develop algorithms to compute the preferred models of circumscriptive databases at compile-time usin g mixed integer linear programming techniques. Two advantages of this (bottom-up) approach are that it makes efficient re-use of previous co mputations and it provides much faster run-time performance. Some othe r advantages of using linear programming to automate deduction at comp ile time are that its re-optimization facilities elegantly accommodate database updates and also that it leads to a completely declarative f ormulation in which ordering of rules and literals in rule bodies play s no real role. Finally, we plan to use a standard relational database system as our run-time environment; this should yield relatively fast run-time processing, and provide a more expressive query language in which aggregates and the like can be expressed easily. (C) 1995 Academ ic Press. Inc.