Monotonic and nonmonotonic reasoning in Datalog

Datalog¹, a declarative logic programming language, is known for its ability to express knowledge and relationships between data. When reasoning about this knowledge, the way new information affects existing conclusions plays a crucial role. This article gives an introduction to monotonic and nonmonotonic reasoning in Datalog, exploring how adding information can influence the inferences drawn from a knowledge base.

Monotonic reasoning: Stable and Predictable

Monotonic reasoning is a fundamental concept in logic, where adding new information to a knowledge base preserves the existing conclusions. In simpler terms, if a statement holds true based on the current knowledge, it remains true even after adding more information. It is a form of logical reasoning where adding new information to the knowledge base does not invalidate or contradict any previously derived conclusions. This characteristic makes monotonic reasoning predictable and reliable.

Linear Datalog, the basic form of Datalog, exhibits monotonic reasoning. This means that as we add more facts or rules to the Datalog program, the set of facts that can be derived from the program can only grow or remain the same, but it cannot shrink or contradict previously derived conclusions.

To give an example of monotonic reasoning, consider a Datalog program defining parent-child relationships and inferring ancestor relations:

.decl parent(n: symbol, m: symbol)
.decl ancestor(n: symbol, m: symbol)
parent("john", "bob").
parent("bob", "alice").
ancestor(X, Y) :- parent(X, Y).                      // Base rule: parent is an ancestor
ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).      // Inductive rule: transitive ancestor relation
.output ancestor

Executing this program with a Datalog engine like Soufflé (Soufflé installation guide can be found in Install Soufflé on Ubuntu using Docker), we can infer the following facts in ancestor relation:

john	bob
john	alice
bob  alice

If we add a new fact parent("alice", "charlie"). to the program, it will add new facts to the existing facts of ancestor relation without invalidating or contradicting the previously derived facts:

john	bob
john	alice
john	charlie     // New ancestor relation
bob  alice
bob  charlie     // New ancestor relation
alice	charlie     // New ancestor relation

In this example, the addition of new information (alice is a parent of charlie) strengthens the knowledge base but doesn’t invalidate previous conclusions about ancestor relationships.

Nonmonotonic reasoning: Flexible and Context-Sensitive

Nonmonotonic reasoning allows adding new information to a knowledge base to potentially invalidate or revise existing conclusions. In other words, a statement that holds true initially might become false or require modification when new information comes to light. This flexibility makes nonmonotonic reasoning valuable for dealing with incomplete or evolving knowledge.

While linear Datalog doesn’t directly support nonmonotonic reasoning, stratified Datalog, an extension of Datalog, introduces this capability.

For example, let’s see a Datalog program with three relations: person, adult, and child:

.decl person(n: symbol)
.decl adult(n: symbol)
.decl child(n: symbol)

person("john").
person("alice").
adult(X) :- person(X), !child(X).

.output adult, child

If we run the program, we see both john and alice in the adult relation and the child relation is empty:

adult
===============
john
alice
===============

This initial conclusion assumes everyone is an adult by default unless explicitly stated as a child. The program selects both the person as adult because there are no facts stating that they are children.

Now, if we add a new fact child("alice"). to the program, it will invalidate the previous facts and give the following output:

child
===============
alice
===============

adult
===============
john
===============

The addition of the new facts invalidated the previous conclusion about alice being an adult. This behavior is nonmonotonic because adding the new information (child("alice").) caused a previously derived conclusion (alice is adult) to be revised or retracted. Nonmonotonic reasoning is useful in situations where we need to make default assumptions or handle incomplete or evolving information. It allows for more flexible and context-sensitive reasoning, which can be beneficial in areas like knowledge representation, expert systems, and AI applications.

Stratified negations

Nonmonotonic reasoning can introduce complexities and potential inconsistencies (such as circular definition) if not handled properly. Thus, not all negations are semantically permissible as they may lead to circular dependencies or ambiguities. Stratified Datalog addresses this challenge by supporting nonmonotonic features through techniques like stratified negation, ensuring consistency and termination guarantees. For example, we cannot use the following negations in the above program:

adult(X) :- person(X), !child(X).
child(X) :- person(X), !adult(X).

This would add circular definition and would generate the following error:

Error: Unable to stratify relation(s) {adult,child}
Relation adult in file nonmono.dl at line 2
.decl adult(n: symbol)
------^----------------
has cyclic negation in file nonmono.dl at line 10
child(X) :- person(X), !adult(X).
------------------------^---------
1 errors generated, evaluation aborted

Such circular definition is forbidden as it creates circular definition. It’s also important to ensure that your Datalog program adheres to the stratification rules and avoids circular definitions when using nonmonotonic reasoning. Rules containing negations must be stratifiable to maintain the integrity and coherence of the logical system². Stratification ensures consistency and termination guarantees, preventing potential issues such as infinite loops or contradictory conclusions.

📝 When working with Datalog, it’s essential to carefully consider the nature of the problem and the requirements for reasoning.

If we’re dealing with a static or gradually expanding knowledge base, monotonic reasoning with traditional Datalog may be the most appropriate choice. However, if we need to handle incomplete or evolving information and make default assumptions that can be revised, stratified Datalog with nonmonotonic reasoning capabilities may be a better fit.

References