2003/05/13 by C. A. Johnson, Chris Johnson, Johnson, C. A.
Computer Science · #Advanced Algebra and Logic #Advanced Database Systems and Queries #F4.1 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #cs.LO
paper · pdf · doi:10.48550/arxiv.cs/0305007
48 pages
arxiv created 2003/05/13 · openalex publication_date 2003/05/13 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A method is presented for computing minimal answers in disjunctive deductive databases under the disjunctive stable model semantics. Such answers are constructed by repeatedly extending partial answers. Our method is complete (in that every minimal answer can be computed) and does not admit redundancy (in the sense that every partial answer generated can be extended to a minimal answer), whence no non-minimal answer is generated. For stratified databases, the method does not (necessarily) require the computation of models of the database in their entirety. Compilation is proposed as a tool by which problems relating to computational efficiency and the non-existence of disjunctive stable models can be overcome. The extension of our method to other semantics is also considered.