Contradiction in Database [1]

Suppose you have a database, of any type: SQL, NoSQL, not-yet-SQL, a spreadsheet, a bunch of CSV files, or a shoebox full of post-it notes.

I would argue that the database represents a bag (multiset) of facts; even if it does not look like that, it can be verbalized as such.

Let’s name this bag of facts: Γ.

Consider a case when two of these facts contradict each other.
Suppose that in Γ we find a fact: today is Monday; then another fact that states: today is Friday. Let’s see if I can formalize this:

A = Today is Monday.
B = Today is Friday.

        B ⊢ ¬A   Γ ⊢ B
        ----------------- (e1)
Γ ⊢ A   Γ ⊢ ¬A
------------------------- (i1)
Γ ⊢ (A ∧ ¬A)

Rule e1 states that B entails (not A) and given that Γ entails B, from Γ we can conclude that (not A) is true. Rule i1 states that Γ entails A is true and (not A) is true, so we conclude that (A and not A) is true.

According to the database, both propositions — today is Monday, and today is not Monday — are true; hence the contradiction.


There is a problem with contradiction and reasoning. Let’s introduce a proposition, a pure nonsense: pigs can fly.

A,B ∈ Γ
A = Today is Monday.
B = Today is Friday.
N = Pigs can fly.

Γ ⊢ B      B ⊢ ¬A
---------------------- (e1)
Γ ⊢ ¬A

           Γ ⊢ A            
           ----------- (i2)
Γ ⊢ ¬A     Γ ⊢ (A ∨ N)       
---------------------- (e4)
Γ ⊢ N

Rule i2 states that given that Γ entails A is true, we can conclude that (A or N) is true; this is simple: (true or x) evaluates to true.
According to the rule e4, Γ entails A is false, and (A or N) is true; hence from Γ we conclude that N must be true.

Note that initially the proposition N did not come from Γ, but the conclusion that N is true does.


In general, for a database Γ having a proposition (fact) A that can be considered true and false at the same time, the following holds:

A ∈ Γ, Γ ⊢ (A ∧ ¬A)
A = Any fact.
N = Any nonsense.

                   Γ ⊢ (A ∧ ¬A)
                   ----------- (e2)
Γ ⊢ (A ∧ ¬A)       Γ ⊢ A            
----------- (e3)   ----------- (i2)
Γ ⊢ ¬A             Γ ⊢ (A ∨ N)       
------------------------------ (e4)
Γ ⊢ N

This is called the principle of explosion, and is usually stated as: “from contradiction anything follows”. I prefer a bit more dramatic version:

Contradiction leads to nonsense.

How does a contradiction enter a database? Is it possible to prevent it? What are the consequences, if any? About all that, in the remainder of this series.