When the theory of deductive databases emerged to offer more powerful capabilities to relational databases by means of the mathematical logic paradigm, new problems came up with the use of the so-called “closed world assumption.” While first-order logic is monotonic, logic databases are not, because only positive information is explicitly specified. It is easy to define a relation’s transitive closure for Horn databases or positive logic programs, which is not definable by a relational algebraic expression. On the other hand, simple relations like the complement of a relation with respect to another relation are not definable by Horn databases, even if they are definable by relational algebra formulas. If positive logic programs are well understood from the procedural, declarative, and computational points of view, providing the declarative semantics for a general logic program is a difficult task because of the extralogical implicit use of negation. The author compares various approaches to this thorny problem.

The starting point is an overview of the major solutions to defining the declarative semantics of positive programs. Bidoit covers both minimal model and least fixpoint semantics, which have been proven to be the same for positive logic programs, emphasizing the problems that arise when negation is introduced. Each approach is characterized mainly from two points of view: the semantic viewpoint interprets negation to be as much like complementation as possible, and the computational viewpoint provides a constructive  definition. 

Several sections of the paper are devoted to approaches based on fixpoint techniques. The author analyzes stratifiable programs, which preclude the use of recursive negation, and two variants, loosely stratifiable and locally stratifiable logic programs. The restriction mentioned before is overruled when considering well-founded semantics. Generating negative facts at each iteration is guided by the syntax of the program and is now totally independent of the derivation of positive facts. Finally, a third approach based on fixpoint techniques is inflationary semantics, which is seen as an extension of the iterative fixpoint semantics, giving a meaning not only to stratifiable logic programs but to all logic programs. This approach is more concerned with computational issues and has an expressive power strictly greater than that of stratifiable programs with iterative fixpoint and equal to that of well-founded semantics, even though programs are written in a less natural manner.

Two more sections are devoted to model-theoretic semantics. The first provides an equivalent alternative to the iterative fixpoint semantics of stratifiable logic programs, using such concepts as circumscription. In the second, Bidoit discusses the non-monotonic approach to defining the declarative semantics of logic programs. That is by no means a surprise, considering that the closed world assumption is an instance of default reasoning and that default rules can be used to derive negative information. The author is careful to state the analogies and differences among various models both formally when possible and informally. Throughout the paper, he uses a carefully chosen set of examples that underline the differences of various approaches.

Even if the author assumes that the reader is familiar with basic concepts of first-order logic, logic programming, and fixpoint theory, he summarizes major definitions and results. Few proofs are given for the stated theorems, and the reader eager to know more is referred to some additional work.

I fully recommend the paper to anyone interested in logic programming and semantics.