Computing circumscriptive databases. I. Theory and algorithms

Anil Nerode, Raymond T. Ng, V. S. Subrahmanian

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


Though circumscription was introduced by McCarthy over a decade ago, there has been relatively little work on algorithms for computing circumscriptive databases. In this paper, we develop algorithms to compute the preferred models of circumscriptive databases at compile-time using mixed integer linear programming techniques. Two advantages of this (bottom-up) approach are that it makes efficient re-use of previous computations and it provides much faster run-time performance. Some other advantages of using linear programming to automate deduction at compile time are that its re-optimization facilities elegantly accommodate database updates and also that it leads to a completely declarative formulation in which ordering of rules and literals in rule bodies plays 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.

Original languageEnglish (US)
Pages (from-to)58-80
Number of pages23
JournalInformation and Computation
Issue number1
StatePublished - Jan 1995
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Computing circumscriptive databases. I. Theory and algorithms'. Together they form a unique fingerprint.

Cite this