11institutetext: Dominique Laurent 22institutetext: ETIS Laboratory - ENSEA,
CY Cergy Paris University, CNRS
F-95000 Cergy-Pontoise, France
<EMAIL_ADDRESS>Nicolas Spyratos 44institutetext:
LISN Laboratory - University Paris-Saclay, CNRS
F-91405 Orsay, France
<EMAIL_ADDRESS>

Acknowledgment: Work conducted while the second author was visiting at FORTH
Institute of Computer Science, Crete, Greece (https://www.ics.forth.gr/)

# Deductive Databases in Four-Valued Logic:
Rule Semantics and Models

Dominique Laurent  Nicolas Spyratos

###### Abstract

In this paper, we investigate rule semantics for deductive databases in the
context of Four-valued logic. In our approach a database is a pair
$\Delta=(E,R)$, where $E$ is a set of pairs, each pair associating a ground
fact with a truth value (thus allowing to store true, false or inconsistent
facts) and $R$ is a set of rules generalizing standard Datalog rules in the
following sense: $(i)$ the head of a rule can be a positive or a negative
atom, and $(ii)$ the body can involve any among the connectors of Four-valued
logic. We define the database semantics as the least fixed point of a
monotonic operator and we compare this semantics with that of k-existential
programs defined by Fitting and paraconsistent extended logic programs defined
by Arieli.

Our main contribution is to show that, if we consider rules as implications
(that is, if we view the database as a set of formulas) then the semantics of
the database is the unique minimal model of the set of database formulas.
Here, minimality is understood with respect to the knowledge ordering of Four-
valued logic satisfying a monotonicity property whereby the truth value of the
head of an instantiated rule is greater than that of the body. Moreover, we
address the issue of updating databases with finite semantics in the context
of Four-valued logic. We argue that our approach allows for a new kind of
updates, in which the update result depends not only on the fact involved in
the update, but also on its current truth value in the database.

###### Keywords:

Four-valued logic . Deductive database . Least fix point . Rule semantics .
Database model . Database update

##  1 Introduction

In this paper, we extend the notion of deductive databases CeriGT90; Ullman to
the context of Four-valued logic Belnap, a formalism known to be suitable for
data integration, as it allows to deal with unknown, inconsistent, true and
false information.

In our approach, a database is a pair $\Delta=(E,R)$ where $E$ is the database
extension and $R$ is a set of rules. More precisely:

  * •

the database extension $E$ is a set of pairs of the form $\langle\varphi,{\tt
v}\rangle$, where $\varphi$ is a ground fact and v its truth value, thus
allowing to store true, false or inconsistent facts

  * •

the rules generalize standard Datalog rules in the sense that: $(i)$ the head
of a rule can be a positive or negative fact, and $(ii)$ the body can involve
any among the connectors of Four-valued logic, namely $\neg$, $\vee$,
$\wedge$, $\oplus$ and $\otimes$.

Database semantics is defined as the least fixed point of a monotonic
operator, as done for paraconsistent extended logic programs defined in
Arieli02 and for $k$-existential programs defined by Fitting Fitting90. A
comparison between our semantics and the semantics in Arieli02 and Fitting90
is discussed in detail later in the paper. Before going into technical
details, let us motivate our approach through an example that we shall use as
our running example throughout the paper.

Running Example. Consider bags of rice grains that are transported from rice
farms to warehouses where they are stored. Two important factors that (among
others) influence the storage of rice, are color and humidity of the rice
grains Batay. Each bag is tested for color and humidity in two different
sites, first just before leaving the rice farm and then just before entering
the warehouse.

Assuming that each bag has a unique identifier, the bag with identifier $ID$
is associated with two atomic formulas, namely $W\\_Fit(ID)$ and $H\\_Fit(ID)$
whose truth values respectively account for its fitness with respect to
‘whiteness’ and for its fitness with respect to ‘humidity’. To pass the
‘whiteness’ criterion, i.e., to ensure that $W\\_Fit(ID)$ is true, the tests
should say that the grains in the bag are indeed white, while to pass the
‘humidity’ criterion, i.e., to ensure that $H\\_Fit(ID)$ is true, the tests
should say that the grains in the bag are not humid.

Then, the overall fitness for a bag with identifier $ID$, denoted by
$Fit(ID)$, is assessed through the conjunction $W\\_Fit(ID)\wedge
H\\_Fit(ID)$, which is generalized as the rule $Fit(x)\leftarrow
W\\_Fit(x)\wedge H\\_Fit(x)$, where $x$ is a variable.

Assume now that the tests are conducted by sensors: two sensors at the rice
farm, one for color, denoted $W_{1}$, and one for humidity denoted $H_{1}$;
and two sensors at the warehouse denoted $W_{2}$ and $H_{2}$. We also assume
that, during a test, if the sensor is functioning then it returns a Boolean
value (true or false), otherwise it returns no value. Under these assumptions,
one of the following cases can appear for the sensors testing color (and
similarly for the sensors testing humidity):

  1. 1.

The two sensors return the same value.

  2. 2.

The two sensors return different values.

  3. 3.

Only one of the two sensors returns a value.

  4. 4.

Neither of the two sensors returns a value.

Then the question is: what value should we assign to $W\\_Fit(ID)$ in each of
the four cases above? In our approach, we answer this question by
‘integrating’ the outputs of $W_{1}$ and $W_{2}$ as follows (and similarly for
the outputs of $H_{1}$ and $H_{2}$):

  1. 1.

$W\\_Fit(ID)$ is set to the common value returned by the two sensors.

  2. 2.

$W\\_Fit(ID)$ is set to inconsistent, as the two sensors returned different
values.

  3. 3.

$W\\_Fit(ID)$ is set to the value returned by the sensor which returned a
value.

  4. 4.

$W\\_Fit(ID)$ is set to unknown, as neither of the two sensors returned a
value.

It should be clear that we need more than the standard truth values, True and
False, to express cases 2 and 4 above. It turns out that the Four-valued logic
introduced in Belnap is actually the right formalism as it provides the
additional truth values needed and also the appropriate connectors to work
with these additional truth values. For instance, using a connector denoted by
$\oplus$ we can express all four cases above as a single expression:
$W_{1}(ID)\oplus W_{2}(ID)$. We can therefore generalize this situation
through the rule $W\\_Fit(x)\leftarrow W_{1}(x)\oplus W_{2}(x)$, where $x$ is
a variable. The situation regarding humidity is expressed by means of a
similar rule whose head involves negation, namely $\neg H\\_Fit(x)\leftarrow
H_{1}(x)\oplus H_{2}(x)$. $\Box$

In the light of this example, our contributions are the following:

  1. 1.

We define the formalism for expressing rules as discussed above, and then we
define database semantics as the least fixed point of a monotonic operator.
Moreover, we compare our semantics with that of $k$-existential programs as
defined by Fitting in Fitting90; Fitting91, and that of paraconsistent
extended logic programs as defined by Arieli in Arieli02.

  2. 2.

We show that if one considers the rules as implications then database
semantics is the unique minimal model of the set of implications. Here
minimality is understood with respect to the knowledge ordering of the Four-
valued logic satisfying a monotonicity property whereby the truth value of the
head of an instantiated rule is greater than that of the body. Our notion of
minimality is then compared with that in Arieli02.

  3. 3.

We characterize databases having finite semantics by means of the concept of
safe rule. This is an important issue as it guarantees that all answers to
queries are finite (except if we query for unknown facts). This is an issue
not addressed in Fitting90; Fitting91 or Arieli02.

  4. 4.

We investigate the issue of database updating in the context of Four-valued
logic. This issue is not addressed in Fitting90; Fitting91 or in Arieli02,
although knowledge revision is considered in Arieli02. We argue that the
context of Four-valued logic allows for defining a new kind of updates by
which the result of an update depends not only on the fact involved in the
update, but also on its current truth value in the database content.

The paper is organized as follows: In Section 2 we review the formalism
related to Four-valued logic. Section 3 provides the definitions of syntax and
semantics of databases in the context of Four-valued logic; in this section,
we also investigate properties of our semantics, in particular, in relation
with Fitting90; Fitting91 and Arieli02. In Section 4, we address the issue of
safe rules, to guarantee finite database semantics. Section 5 is devoted to
database updates in the context of our approach. In Section 6, we review some
of the numerous approaches related to our work. Finally, in Section 7, we
provide an overview of our results and outline directions for further
research.

##  2 Background: Four-Valued Logic

###  2.1 Basics of Four-Valued Logic

Four-valued logic was introduced by Belnap in Belnap, who argued that this
formalism could be of interest when integrating data from various data
sources. To this end, denoting by t, b, n and f the four truth values, the
usual connectives $\neg$, $\vee$ and $\wedge$ have been defined as shown in
Figure 1. A prominent feature of this Four-valued logic is that truth values
can be compared according to two partial orderings, known as truth ordering
and knowledge ordering, denoted by $\preceq_{t}$ and $\preceq_{k}$,
respectively, and defined as follows:

${\tt f}\preceq_{t}{\tt n}\preceq_{t}{\tt t}$ ; ${\tt f}\preceq_{t}{\tt
b}\preceq_{t}{\tt t}$ and ${\tt n}\preceq_{k}{\tt t}\preceq_{k}{\tt b}$ ;
${\tt n}\preceq_{k}{\tt f}\preceq_{k}{\tt b}$.

We recall from Belnap that the notation b and n for inconsistent and unknown,
can be read respectively as both and none. This is because considering the set
$\\{{\tt t},{\tt b},{\tt n},{\tt f}\\}$ as the power set of $\\{{\tt
True},{\tt False}\\}$, the truth values ${\tt n}$, ${\tt f}$, ${\tt t}$, ${\tt
b}$ are respectively associated with $\emptyset$, $\\{{\tt False}\\}$,
$\\{{\tt True}\\}$, $\\{{\tt True},\,{\tt False}\\}$. We note that, under this
association, the ordering $\preceq_{k}$ and the connectors $\oplus$ and
$\otimes$ are respectively set theoretic inclusion, union and intersection
applied to the power set of $\\{{\tt True},{\tt False}\\}$.

$\varphi$ |  $\neg\varphi$
---|---
${\tt t}$ | ${\tt f}$
${\tt b}$ | ${\tt b}$
${\tt n}$ | ${\tt n}$
${\tt f}$ | ${\tt t}$

$\varphi$ |  $\not\sim\varphi$
---|---
t | b
b | t
n | f
f | n

$\varphi$ |  $\sim\varphi$
---|---
t | f
b | n
n | b
f | t

$\vee$ | t | b | n | f
---|---|---|---|---
t | t | t | t | t
b | t | b | t | b
n | t | t | n | n
f | t | b | n | f

$\wedge$ | t | b | n | f
---|---|---|---|---
t | t | b | n | f
b | b | b | f | f
n | n | f | n | f
f | f | f | f | f

$\oplus$ | t | b | n | f
---|---|---|---|---
t | t | b | t | b
b | b | b | b | b
n | t | b | n | f
f | b | b | f | f

$\otimes$ | t | b | n | f
---|---|---|---|---
t | t | t | n | n
b | t | b | n | f
n | n | n | n | n
f | n | f | n | f

Figure 1: Truth tables of basic connectors

As in standard two-valued logic, conjunction (respectively disjunction)
corresponds to minimum (respectively maximum) truth value, when considering
the truth ordering. It has also been shown in Arieli02; Belnap; Fitting90;
Fitting91 that the set $\\{{\tt t},{\tt b},{\tt n},{\tt f}\\}$ equipped with
these two orderings has a distributive bi-lattice structure, where the minimum
and maximum with respect to $\preceq_{k}$ are denoted by $\otimes$ and
$\oplus$, respectively.

It should be emphasized that, not surprisingly, some basic properties holding
in standard logic do not hold in this Four-valued logic. For example, Figure 1
shows that formulas of the form $\Phi\vee\neg\Phi$ are not always true,
independently from the truth value of $\Phi$. More importantly, it has been
argued in Arieli1998; Hazen17; Tsoukias that defining the implication
$\Phi_{1}\Rightarrow\Phi_{2}$ by $\neg\Phi_{1}\vee\Phi_{2}$, is problematic.

To see this, as done in Arieli1998; Belnap; Hazen17; Tsoukias, the
distinguished truth values in our approach, are t and b, meaning that
distinguished truth values are those that ‘contain some truth’. Then, a given
propositional formula $\Phi$ is said to be valid for a given truth value
assignment of its propositional variables if the corresponding truth value of
$\Phi$ is distinguished.

Considering now the formula $\Phi$ defined by
$(\Phi_{1}\wedge(\Phi_{1}\Rightarrow\Phi_{2}))\Rightarrow\Phi_{2}$, Figure 2
shows that if $v$ is a truth value assignment such that $v(\Phi_{1})={\tt n}$
and $v(\Phi_{2})={\tt f}$, then $v(\Phi_{1}\Rightarrow\Phi_{2})={\tt n}$ and
thus, $v(\Phi)={\tt n}$. Hence in this case, $\Phi$ is not valid, which is
counter-intuitive, because it is expected that $\Phi$ should be valid in any
case. This remark leads to discard $\Rightarrow$ as an implication.

|  $\Rightarrow$ | t | b | n | f
---|---|---|---|---
t | t | b | n | f
b | t | b | t | b
n | t | t | n | n
f | t | t | t | t
|  $\to_{1}$ | t | b | n | f
---|---|---|---|---
t | t | b | n | f
b | t | b | n | f
n | t | t | t | t
f | t | t | t | t
|  $\to_{2}$ | t | b | n | f
---|---|---|---|---
t | t | b | n | f
b | t | t | n | n
n | t | b | t | b
f | t | t | t | t
|  $\to_{3}$ | t | b | n | f
---|---|---|---|---
t | t | b | n | f
b | t | b | n | f
n | b | b | b | b
f | b | b | b | b
|  |  $\stackrel{{\scriptstyle*}}{{\to}}_{1}$ | t | b | n | f
---|---|---|---|---
t | t | f | n | f
b | t | b | n | f
n | t | n | t | n
f | t | t | t | t
|  $\stackrel{{\scriptstyle*}}{{\to}}_{2}$ | t | b | n | f
---|---|---|---|---
t | t | f | f | f
b | t | t | f | f
n | t | f | t | f
f | t | t | t | t
|  $\stackrel{{\scriptstyle*}}{{\to}}_{3}$ | t | b | n | f
---|---|---|---|---
t | b | f | f | f
b | b | b | f | f
n | b | f | b | f
f | b | b | b | b
Figure 2: Truth tables of $\Rightarrow$ and of implications in Four-Valued
Logic

###  2.2 Implication in Four-Valued Logic

Although rule based languages and implication are two distinct concepts, we
recall that, in standard logic programming, there is a strong link between the
two. Indeed, it is well known that the semantics of a positive logic program
(i.e., a set of rules with no negation) is the least model of the set of first
order formulas obtained by considering the rules as implications. In order to
set a similar result in our framework, we need to define an implication and,
as our earlier discussion shows, this implication cannot be $\Rightarrow$.

Among the various proposals introduced in the literature (see Arieli1998;
Hazen17; OmoriW17; Tsoukias), we mention six implications whose truth tables
are shown in Figure 2. Considering $\leadsto$ as a generic symbol standing for
any of the symbols $\to_{i}$ or $\stackrel{{\scriptstyle*}}{{\to}}_{i}$
($i=1,2,3$), let $\overline{\Phi}$ be the formula
$(\Phi_{1}\leadsto(\Phi_{1}\leadsto\Phi_{2}))\leadsto\Phi_{2}$. Then, contrary
to $\Phi$, the formula $\overline{\Phi}$ has truth value ${\tt t}$ of ${\tt
b}$ for all truth value assignments of $\Phi_{1}$ and $\Phi_{2}$. In other
words, $\overline{\Phi}$ is always valid, whatever the truth values assigned
to $\Phi_{1}$ and $\Phi_{2}$. Thus, all six implications $\to_{i}$ and
$\stackrel{{\scriptstyle*}}{{\to}}_{i}$ for $i=1,2,3$, are therefore
acceptable regarding the validity of $\overline{\Phi}$.

Although our purpose in this paper is not to assess which implication could be
‘better’ than another, it is nevertheless relevant to recall some of their
basic properties. In doing so, we shall argue that, in our context, for every
$i=1,2,3$, the implication $\to_{i}$ has suitable properties, whereas such is
not the case for $\stackrel{{\scriptstyle*}}{{\to}}_{i}$.

First, it is well known that none of these implications can be expressed using
the standard connectors $\neg$, $\vee$ and $\wedge$ (see Corollary 9 in
Arieli1998 regarding $\to_{1}$), and that this becomes possible when
considering the additional connectors available in the Four-valued logic. To
see this, considering as in Tsoukias the basic connectors $\neg$, $\vee$,
$\wedge$, $\not\sim$, $\oplus$ and $\otimes$, the connector $\sim$ is defined
for every formula $\phi$ by:

$\sim\phi=\neg\not\sim\neg\not\sim\phi=\not\sim\neg\not\sim\neg\phi$.

Moreover, the additional connectors ${\bf T}$, ${\bf B}$, ${\bf N}$ and ${\bf
F}$ are introduced in Tsoukias, with truth tables as shown in Figure 3. These
connectors allow to ‘characterize’ each truth value in terms of only the
standard ones, namely ${\tt t}$ and ${\tt f}$. Roughly speaking, given a truth
value ${\tt v}$, the corresponding connector which we denote by ${\bf V}$, is
defined for every formula $\phi$ by the fact that ${\bf V}\phi$ is true if
$\phi$ has the truth value ${\tt v}$ and false otherwise.

$\phi$ |  ${\bf T}\phi$
---|---
t | t
b | f
n | f
f | f

$\phi$ |  ${\bf B}\phi$
---|---
t | f
b | t
n | f
f | f

$\phi$ |  ${\bf N}\phi$
---|---
t | f
b | f
n | t
f | f

$\phi$ |  ${\bf F}\phi$
---|---
t | f
b | f
n | f
f | t

$\phi$ |  $\circ\phi$
---|---
t | f
b | f
n | t
f | t

$\phi$ |  $\diamond\phi$
---|---
t | n
b | n
n | b
f | b

Figure 3: Truth tables of unary connectors from Tsoukias and of connectors
$\circ$ and $\diamond$

Then, considering that two propositional formulas $\phi_{1}$ and $\phi_{2}$
are equivalent, denoted by $\phi_{1}\equiv\phi_{2}$, if they have the same
truth tables, the following equivalences are shown in Tsoukias:

${\bf T}\phi\equiv\phi\,\wedge\sim\neg\phi$ ; ${\bf
B}\phi\equiv\,\not\sim\phi\,\wedge\not\sim\neg\phi$ ; ${\bf
N}\phi\equiv\,\sim\not\sim\phi\,\wedge\neg\not\sim\phi$ ; ${\bf
F}\phi\equiv\,\sim\phi\wedge\neg\phi$.

Now, let the additional connectors $\circ$ and $\diamond$ be defined by:

$\circ\phi=\neg({\bf T(\phi)}\vee{\bf B}(\phi))$ and
$\diamond\phi=\,\not\sim\neg({\bf T(\phi)}\vee{\bf B}(\phi))$.

It turns out that $\circ$ ‘characterizes’ the non validity of a formula $\phi$
in terms of the truth values ${\tt t}$ and ${\tt f}$. In other words, as shown
by Figure 3, $\circ\phi$ is true if $\phi$ is not valid and false otherwise.
The connector $\diamond$ expresses a similar formula, using truth values ${\tt
b}$ and ${\tt n}$ instead of ${\tt t}$ and ${\tt f}$.

These connectors provide the following simple formulas expressing the
implications whose truth tables are shown in Figure 2.

  1. 1.

$\phi_{1}\to_{1}\phi_{2}\equiv\circ\phi_{1}\vee\phi_{2}$ (easy to prove based
on the truth tables)

  2. 2.

$\phi_{1}\to_{2}\phi_{2}\equiv\,\sim\phi_{1}\vee\phi_{2}$ (see Tsoukias for
the proof of this result)

  3. 3.

$\phi_{1}\to_{3}\phi_{2}\equiv\diamond\phi_{1}\oplus\phi_{2}$ (easy to prove
based on the truth tables)

  4. 4.

$\phi_{1}\stackrel{{\scriptstyle*}}{{\to}}_{1}\phi_{2}\equiv(\phi_{1}\to_{1}\phi_{2})\wedge(\neg\phi_{2}\to_{1}\neg\phi_{1})$

  5. 5.

$\phi_{1}\stackrel{{\scriptstyle*}}{{\to}}_{2}\phi_{2}\equiv(\phi_{1}\to_{2}\phi_{2})\wedge(\neg\phi_{2}\to_{2}\neg\phi_{1})$

  6. 6.

$\phi_{1}\stackrel{{\scriptstyle*}}{{\to}}_{3}\phi_{2}\equiv(\phi_{1}\to_{3}\phi_{2})\wedge(\neg\phi_{2}\to_{3}\neg\phi_{1})$

The last three items above show that, for $i=1,2,3$,
$\stackrel{{\scriptstyle*}}{{\to}}_{i}$ has been introduced due to the fact
that $\to_{i}$ does not satisfy the appealing property of contraposition of
implication, namely $\phi_{1}\to_{i}\phi_{2}$ and
$\neg\phi_{2}\to_{i}\neg\phi_{1}$ are not equivalent. It is of course easy to
see that for $i=1,2,3$, $\stackrel{{\scriptstyle*}}{{\to}}_{i}$ satisfies the
property of contraposition of implication, i.e., the equivalence
$\phi_{1}\stackrel{{\scriptstyle*}}{{\to}}_{i}\phi_{2}\equiv\neg\phi_{2}\stackrel{{\scriptstyle*}}{{\to}}_{i}\neg\phi_{1}$
holds.

On the other hand, since $\circ\phi$ can be read as $\phi$ is not valid, the
first item above shows that $\phi_{1}\to_{1}\phi_{2}$ can be read as either
$\phi_{1}$ is not valid or $\phi_{2}$, as mentioned in Arieli02. A similar
remark holds regarding $\to_{3}$, using $\not\sim\neg$ instead of $\neg$ as
negation, and $\oplus$ instead of $\vee$ as disjunction. As for $\to_{2}$, it
is argued in Tsoukias that $\sim\phi$ can be read as the ‘complement’ of
$\phi$, and so, $\phi_{1}\to_{2}\phi_{2}$ can be read as either the complement
of $\phi_{1}$ or $\phi_{2}$.

For the purpose of our work, we emphasize that, as Figure 2 shows, the
implications $\phi_{1}\to_{i}\phi_{2}$, for $i=1,2,3$, are valid in the same
cases, namely when $\phi_{1}$ and $\phi_{2}$ are valid or when $\phi_{1}$ is
not valid. This remark shows that, regarding validity, the implications
$\to_{i}$ behave in a similar way as $\Rightarrow$ does in the context of two-
valued logic (that is, $\phi\Rightarrow\phi_{2}$ is true if and only if
$\phi_{1}$ and $\phi_{2}$ are true or $\phi_{1}$ is false). However, this
remark does not hold for the implications
$\stackrel{{\scriptstyle*}}{{\to}}_{i}$, $i=1,2,3$.

As we shall see later (Definition 5), the notion of database model relies only
on the validity of implications.It therefore follows from the above discussion
that choosing one implication among $\to_{1}$, $\to_{2}$ or $\to_{3}$ makes no
difference in the results obtained in our approach (see Section 4): these
results hold no matter which of these implications is chosen. However, the
above discussion also shows that the implications
$\stackrel{{\scriptstyle*}}{{\to}}_{i}$, $i=1,2,3$, have to be discarded in
the context of our approach.

Therefore, in this paper we choose $\to$ as a generic symbol for implication.
One can replace it by any of the symbols $\to_{1}$, $\to_{2}$ or $\to_{3}$,
with no effect on the results.

##  3 Four-Valued Logic and Databases

###  3.1 Database Syntax

As usual, when dealing with deductive databases, the alphabet is made up of
constants, variables and predicate symbols with a fixed arity. We thus assume
a fixed set of constants, called the Herbrand Universe and denoted by ${\cal
H}$. Note that ${\cal H}$ may be infinite.

As in traditional approaches, a term is either a constant from ${\cal H}$ or a
variable, and an atomic formula (also called atom) is a formula of the form
$P(t_{1},t_{2},\ldots,t_{k})$ where $P$ is a $k$-ary predicate and $t_{i}$ is
a term, for every $i=1,2,\ldots,k$. A formula is said to be a ground formula
if it contains no variables. A fact is a ground atom that is an atom in which
all terms are constants. Moreover, a literal is either an atom or the negation
of an atom; in the former case the literal is said to be positive and in the
latter case it is said to be negative. The Herbrand Base associated with
${\cal H}$, denoted by ${\cal HB}$, is the set of all facts that can be built
up using the constants in ${\cal H}$ and the predicates. Clearly, if ${\cal
H}$ is infinite, then so is ${\cal HB}$.

In this setting, a valuation (or interpretation) of ${\cal HB}$ is defined to
be a truth value assignment associating every fact in ${\cal HB}$ with a truth
value in $\\{{\tt t},{\tt b},{\tt n},{\tt f}\\}$. More formally, a valuation
is a total function $v:{\cal HB}\to\\{{\tt t},{\tt b},{\tt n},{\tt f}\\}$, and
for every fact $\varphi$ in ${\cal HB}$, $v(\varphi)$ is referred to as the
truth value of $\varphi$ under $v$. The set $S_{v}=\\{\langle\varphi,{\tt
v}\rangle~{}|~{}v(\varphi)\neq{\tt n}\\}$ is called the known part of $v$.

Conversely, let $S$ be a set of pairs of the form $\langle\varphi,{\tt
v}\rangle$ where $\varphi$ is in ${\cal HB}$ and ${\tt v}$ is a truth value.
Then, based on $S$, we can define a valuation $v_{S}$ if the following
assumptions hold:
(1) ${\tt v}$ is different than ${\tt n}$, i.e., ${\tt v}$ is in $\\{{\tt
t},{\tt b},{\tt f}\\}$,
(2) for all $\langle\varphi_{1},{\tt v}_{1}\rangle$ and
$\langle\varphi_{2},{\tt v}_{2}\rangle$ in $S$, if $\varphi_{1}=\varphi_{2}$
then ${\tt v}_{1}={\tt v}_{2}$,
(3) for every $\varphi$ not occurring in $S$, $v_{S}(\varphi)={\tt n}$.

Such set $S$ is called a valuated-set, or v-set for short. As for the above
assumptions, we emphasize the following:

  1. 1.

Assumption (1) means that if a fact $\varphi$ appears in $S$ then it is in the
known part of $v_{S}$, i.e., $v_{S}(\varphi)\neq{\tt n}$.

  2. 2.

Assumption (2) means that every fact $\varphi$ occurring in $S$ is associated
with one and only one truth-value (which according to (1), belongs to $\\{{\tt
t},{\tt b},{\tt f}\\}$). We shall refer to this assumption as the
‘functionality’ of $S$.

  3. 3.

Assumption (3) means that every fact $\varphi$ not occurring in $S$ is
‘unknown’, i.e., $v_{S}(\varphi)={\tt n}$. We shall refer to this assumption
as the ‘Open World Assumption’ (or OWA for short).

We are now ready to define the concept of database in Four-valued logic.

###### Definition 1

A database over ${\cal HB}$ is a pair $\Delta=(E,R)$ such that:

  * •

$E$ is a finite v-set over ${\cal HB}$ called the extension of $\Delta$.

  * •

$R$ is a set of rules called the rule set of $\Delta$. A rule in $R$ is an
expression of the form $\rho:h(X)\leftarrow B(X,Y)$ where $X$ and $Y$ are
vectors of variables such that all variables in $X$ occur in $B(X,Y)$.
Moreover:

    * –

$h(X)$ is a positive or negative literal

    * –

$B(X,Y)$ is a quantifier free, well formed formula built up using the
connectors $\neg$, $\vee$, $\wedge$, $\oplus$ and $\otimes$.

Given a rule $\rho:h(X)\leftarrow B(X,Y)$, $h(X)$ is called the head of
$\rho$, denoted by $head(\rho)$, and $B(X,Y)$ is called the body of $\rho$,
denoted by $body(\rho)$. $\Box$

It should be clear that our definition of database generalizes that of
standard Datalogneg databases (Bidoit91; CeriGT90) in significant ways.
Indeed:

  * •

Contrary to Datalog databases, the database extension $E$ is not a set of
ground facts, but a v-set. Therefore $E$ stores not only true facts, but also
false facts or inconsistent facts. Moreover, contrary to Datalog databases, we
allow the predicate symbols occurring in $E$ to also occur in the rule heads.
In other words we do not assume that the set of predicate symbols is
partitioned into a set of extensional and a set of intentional predicate
symbols.

  * •

As in Datalog, all variables occurring in the head of a rule also occur in the
body. However, in our approach, the rule body may involve any among the
connectors $\neg$, $\vee$, $\wedge$, $\oplus$ and $\otimes$, and the head may
be a positive or a negative literal.

  * •

Our definition generalizes rules as defined in Lau2019 where the bodies of the
rules are restricted to be conjunctions only.

Before investigating the close relationship between our approach and the works
in Fitting90; Fitting91 and Arieli02, we illustrate Definition 1 in the
context of our Running Example.

###### Example 1

In our Running Example, let us consider the set of predicate symbols
$Pred=\\{H_{1},H_{2},W_{1},W_{2},H\\_Fit,W\\_Fit,Fit,Species,Alert\\}$, the
set of constants ${\cal H}=\\{101,202,303,s_{1},s_{2},low,high\\}$ and the
corresponding Herbrand base ${\cal HB}$. Moreover, let us define the database
$\Delta=(E,R)$ as follows:

$E=\\{$ | $\langle W_{1}(101),{\tt t}\rangle,\langle W_{1}(202),{\tt f}\rangle,\langle W_{2}(202),{\tt t}\rangle,\langle W_{1}(303),{\tt f}\rangle,$
---|---
| $\langle H_{1}(101),{\tt f}\rangle,\langle H_{2}(101),{\tt f}\rangle,\langle
H_{2}(202),{\tt t}\rangle,$
| $\langle Species(101,s_{1}),{\tt t}\rangle,\langle Species(202,s_{1}),{\tt
t}\rangle,\langle Species(303,s_{2}),{\tt t}\rangle,\qquad$
| $\langle Fragile(s_{1},low),{\tt t}\rangle,\langle Fragile(s_{2},high),{\tt
t}\rangle\hfill\\}$

$R=\\{\rho_{1},\rho^{\prime}_{1},\rho_{2},\rho^{\prime}_{2},\rho_{3},\rho^{\prime}_{3},\rho_{4}\\}$
where:

$~{}\rho_{1}:$ | $W\\_Fit(x)\leftarrow$ | $W_{1}(x)\oplus W_{2}(x)$ | $~{}\rho^{\prime}_{1}:$ | $\neg W\\_Fit(x)\leftarrow$ | $\neg(W_{1}(x)\oplus W_{2}(x))$
---|---|---|---|---|---
$~{}\rho_{2}:$ | $\neg H\\_Fit(x)\leftarrow$ | $H_{1}(x)\oplus H_{2}(x)$ | $~{}\rho^{\prime}_{2}:$ | $H\\_Fit(x)\leftarrow$ | $\neg(H_{1}(x)\oplus H_{2}(x))$

$~{}\rho_{3}:$ | $Fit(x)\leftarrow$ | $W\\_Fit(x)~{}\wedge H\\_Fit(x)$
---|---|---
$~{}\rho^{\prime}_{3}:$ | $\neg Fit(x)\leftarrow$ | $\neg(W\\_Fit(x)~{}\wedge H\\_Fit(x))$
$~{}\rho_{4}:$ | $Alert(x,z)\leftarrow$ | $\neg Fit(x)\otimes(Species(x,y)\wedge Fragile(y,z))$

We refer to the introductory section regarding the intuition for the rules
$\rho_{1}$, $\rho_{2}$ and $\rho_{3}$. Regarding their ‘dual’ versions
$\rho^{\prime}_{1}$, $\rho^{\prime}_{2}$ and $\rho^{\prime}_{3}$, these rules
are introduced because negation $\neg$ in Four-valued logic is explicit, in
the sense that $\neg\varphi$ is inferred only if either this piece of
information is given in the database extension, or if it is explicitly
obtained through the rules. Thus, if no rule head involves, say $\neg
W\\_Fit(x)$, for some instance $ID$ of $x$ then it is not possible to state
that $\neg W\\_Fit(ID)$ is true (i.e., that $W\\_Fit(ID)$ is false). In fact,
considering $\rho_{1}$ and $\rho^{\prime}_{1}$ amounts to considering these
rules as an equivalence that is $W\\_Fit(ID)$ holds if and only if so does
$W_{1}\oplus W_{2}$. We shall come back to this important point later in the
paper, when comparing our approach with those in Fitting90; Fitting91 and
Arieli02.

Regarding $\rho_{4}$, the intuition is that an alert should be raised in case
of an unFit bag whose content is fragile, and moreover the level of the alert
is set to be that of species fragility ($high$ or $low$ in our example).

More precisely, based on the truth tables shown in Figure 1, it turns out that
the formula $\neg Fit(ID)\otimes(Species(ID,s)\wedge Fragile(s,l))$ has truth
value ${\tt t}$ when the truth value of $\neg Fit(ID)$ is ${\tt t}$ or ${\tt
b}$ and that of $Species(ID,s)\wedge Fragile(s,l)$ is ${\tt t}$. Moreover, if
facts as $Species(ID,s)$ or $Fragile(s,l)$ are:
$-$ either true (i.e., the pairs $\langle Species(ID,s),{\tt t}\rangle$ or
$\langle Fragile(s,l),{\tt t}\rangle$ occur in $E$)
$-$ or unknown (i.e., nothing has been stored regarding these facts),
then the formula $Species(ID,s)\wedge Fragile(s,l)$ has truth value ${\tt t}$
if and only if $Species(ID,s)$ and $Fragile(s,l)$ both have truth value ${\tt
t}$.

In other words, the intuition behind rule $\rho_{4}$ is that an alert of level
$l$ is raised for the bag $ID$ and species $s$ if the following holds: $(i)$
the grains are unFit or an inconsistent measure was made, and $(ii)$ the
grains are of species $s$ whose fragility level is $l$. Notice in this respect
that raising such an alert needs to know that $Fit(ID)$ is false, which is
achieved through the rule $\rho^{\prime}_{3}$, which in turn needs the rules
$\rho^{\prime}_{1}$ and $\rho^{\prime}_{2}$ to be properly triggered. $\Box$

We end this section by observing that, from a technical point of view, the
database extension $E$ is actually a means for the finite representation of a
potentially infinite function over ${\cal HB}$ under the assumptions seen
earlier in the definition of $v_{E}$ (namely the functionality of $E$ and
OWA).

###  3.2 Database Semantics

In our approach, as for Datalog, database semantics is defined as the least
fixed point of a monotonic operator. The definition of this operator relies on
the following extensions of the orderings $\preceq_{k}$ and $\preceq_{t}$ to
the family of all v-sets over ${\cal HB}$.

###### Definition 2

For all v-sets $S_{1}$ and $S_{2}$ over ${\cal HB}$, $S_{1}\preceq_{k}S_{2}$,
respectively $S_{1}\preceq_{t}S_{2}$, holds if for every $\varphi$ in ${\cal
HB}$, $v_{S_{1}}(\varphi)\preceq_{k}v_{S_{2}}(\varphi)$, respectively
$v_{S_{1}}(\varphi)\preceq_{t}v_{S_{2}}(\varphi)$, holds. $\Box$

For example for ${\cal HB}=\\{P(a),$ $P(b),$ $P(c)\\}$, $S_{1}=\\{\langle
P(a),{\tt t}\rangle\\}$ and $S_{2}=\\{\langle P(a),{\tt b}\rangle,$ $\langle
P(b),{\tt f}\rangle\\}$, we have
$v_{S_{1}}(P(b))=v_{S_{1}}(P(c))=v_{S_{2}}(P(c))={\tt n}$. Thus:

  * •

$v_{S_{1}}(P(a))\preceq_{k}v_{S_{2}}(P(a))$,
$v_{S_{1}}(P(b))\preceq_{k}v_{S_{2}}(P(b))$ and
$v_{S_{1}}(P(c))\preceq_{k}v_{S_{2}}(P(c))$, implying that
$S_{1}\preceq_{k}S_{2}$ holds.

  * •

$v_{S_{2}}(P(a))\preceq_{t}v_{S_{1}}(P(a))$,
$v_{S_{2}}(P(b))\preceq_{t}v_{S_{1}}(P(b))$ and
$v_{S_{2}}(P(c))\preceq_{t}v_{S_{1}}(P(c))$, implying that
$S_{2}\preceq_{t}S_{1}$ holds.

  * •

$\emptyset\preceq_{k}S_{2}$, because for every $\varphi$,
$v_{\emptyset}(\varphi)={\tt n}$, the least value with respect to
$\preceq_{k}$.

  * •

$\emptyset$ and $S_{2}$ are not comparable with respect to $\preceq_{t}$,
because $v_{\emptyset}(P(a))={\tt n}$ and $v_{S_{2}}(P(a))={\tt b}$ are not
comparable with respect to $\preceq_{t}$.

The extension of $\preceq_{k}$ generalizes set inclusion in the sense that if
$S_{1}\subseteq S_{2}$, then we have $S_{1}\preceq_{k}S_{2}$. Notice that, as
the last item above shows, the truth ordering $\preceq_{t}$ does not satisfy
this property, because $\emptyset\subseteq S_{2}$ holds while
$\emptyset\preceq_{t}S_{2}$ does not.

We now state the definition of the operator allowing for the computation of
database semantics. In this definition as well as in the remainder of the
paper, $\bigoplus$ denotes the least upper bound with respect to
$\preceq_{k}$.

###### Definition 3

Given a set of rules $R$, let $inst(R)$ be the set of all instantiations of
the rules in $R$ based on the atoms in ${\cal HB}$. For every v-set $V$ and
every $\varphi$ in ${\cal HB}$, let $B^{+}(\varphi)$ and $B^{-}(\varphi)$, be
respectively defined by:

$-$ $B^{+}(V,\varphi)=\\{\rho\in inst(R)~{}|~{}head(\rho)=\varphi\wedge
v_{V}(body(\rho))\in\\{{\tt t},{\tt b}\\}\\}$
$-$ $B^{-}(V,\varphi)=\\{\rho\in inst(R)~{}|~{}head(\rho)=\neg\varphi\wedge
v_{V}(body(\rho))\in\\{{\tt t},{\tt b}\\}\\}$.

The semantic immediate consequence operator associated with a database
$\Delta=(E,R)$, denoted by $\Psi_{\Delta}$, associates a v-set $V$ with the
set $\Psi_{\Delta}(V)$ containing all pairs $\langle\varphi,{\tt v}\rangle$
where $\varphi$ is in ${\cal HB}$ and ${\tt v}$ is a truth value different
than ${\tt n}$ defined by:

${\tt v}=v_{E}(\varphi)~{}\oplus$ | $\bigoplus\\{v_{V}(body(\rho))~{}|~{}\rho\in B^{+}(V,\varphi)\\}$
---|---
$\oplus$ |  $\bigoplus\\{\neg v_{V}(body(\rho))~{}|~{}\rho\in B^{-}(V,\varphi)\\}$.

$\Box$

Notice that if $B^{+}(V,\varphi)\cup B^{-}(V,\varphi)=\emptyset$ (i.e., if
there is no instantiated rule whose body is valid in $V$ and whose head
involves $\varphi$) and if $\varphi$ does not occur in $E$ then the content of
$\Delta$ does not provide any relevant piece of information regarding
$\varphi$. In this case, it is intuitively justified to state that the truth
value of $\varphi$ in $\Psi_{\Delta}(V)$ is ${\tt n}$. This is precisely what
is done according to Definition 3 because, in this case, no pair involving
$\varphi$ is inserted in $\Psi_{\Delta}(V)$.

It should also be emphasized that, according to Definition 3, for every v-set
$V$, $\Psi_{\Delta}(V)$ is a v-set in which, for every $\langle\varphi,{\tt
v}\rangle$ in $E$, $\Psi_{\Delta}(V)$ contains $\langle\varphi,{\tt
v}^{\prime}\rangle$ such that ${\tt v}\preceq_{k}{\tt v}^{\prime}$. The
following lemma shows a basic property of the operator $\Psi_{\Delta}$.

###### Lemma 1

For every $\Delta=(E,R)$, let $\left(\Psi^{i}\right)_{i\geq 0}$ be the
sequence defined by

$\Psi^{0}=\emptyset$, $\Psi^{n}=\Psi_{\Delta}(\Psi^{n-1})$ for $n\geq 1$, and
$\Psi^{\lambda}=\bigoplus_{\alpha<\lambda}\Psi^{\alpha}$ if $\lambda$ is a
limit ordinal.

The sequence $\left(\Psi^{i}\right)_{i\geq 0}$ has a limit which is the unique
least fixed point of $\Psi_{\Delta}$ with respect to $\preceq_{k}$. Moreover,
the least fixed point is reached for an ordinal at most $\omega$.

###### Proof

First, we notice that the connectors involved in standard rules are monotonic,
that is, for all formulas $\phi_{1}$ and $\phi_{2}$ involving $\neg$, $\vee$,
$\wedge$, $\oplus$ or $\otimes$, if $S_{1}$ and $S_{2}$ are two v-sets such
that $S_{1}\preceq_{k}S_{2}$ then
$v_{S_{1}}(\phi_{1})\preceq_{k}v_{S_{2}}(\phi_{2})$ (this can be checked for
each operator based on the truth tables in Figure 1). Therefore
$\Psi_{\Delta}$ is monotonic with respect to $\preceq_{k}$, which by the
Knaster-Tarski theorem implies that the sequence $\left(\Psi^{i}\right)_{i\geq
0}$ has a unique least fixed point. Moreover, since the only infinitary
operator in our computation is $\bigoplus$, $\Psi_{\Delta}$ can be shown to be
continuous as in Fitting90. Therefore, the ordinal for which the least fixed
point is reached is at most $\omega$. $\Box$

We are now ready to define what we call database semantics in our approach.

###### Definition 4

The semantics of a given database $\Delta=(E,R)$, denoted by $sem(\Delta)$, is
defined as the least fixed point of the sequence $\left(\Psi^{i}\right)_{i\geq
0}$.

The valuation defined by the v-set $sem(\Delta)$ is denoted by $v_{\Delta}$
and for every $\varphi$ in ${\cal HB}$, $v_{\Delta}(\varphi)$ is referred to
as the truth value of $\varphi$ in $\Delta$. $\Box$

We note that according to the above definition, the truth value of the head is
changed only if that of the body is designated (either ${\tt t}$ or ${\tt
b}$), as Arieli does in Arieli02, and contrary to Fitting in Fitting90;
Fitting91, who does so also when the body is false. However, in our approach,
if the body is inconsistent, the head is inconsistent as well, whereas in
Arieli02 it is set to true in this case. A more detailed comparison is
provided in the next sub-section.

The following example illustrates Definitions 3 and 4 and Lemma 2 in the
context of our running example.

###### Example 2

Continuing with our running example, let $\Delta=(E,R)$ be the database as
defined in Example 1. Then the v-set $sem(\Delta)$ is computed as follows,
starting from $\Psi^{0}=\emptyset$ and denoting by $v_{i}(\varphi)$ the truth
value of $\varphi$ in $\Psi^{i}$ for every $i\geq 0$:

(1) For every $\varphi$ in ${\cal HB}$, we have $v_{0}(\varphi)={\tt n}$, and
thus for every $\rho$ in $inst(R)$, $v_{0}(body(\rho))={\tt n}$. Hence,
$B^{+}(\Psi_{0},\varphi)=B^{-}(\Psi_{0},\varphi)=\emptyset$, and
$\Psi^{1}=\Psi_{\Delta}(\Psi^{0})=E$.

(2) Computing $\Psi^{2}=\Psi_{\Delta}(\Psi^{1})$, we first consider $\rho_{1}$
and $\rho^{\prime}_{1}$, which are the only rules whose head involves
$W\\_Fit$.
$\bullet$ For $\varphi=W\\_Fit(101)$, $v_{1}(W_{1}(101)\oplus W_{2}(101))={\tt
t}\oplus{\tt n}={\tt t}$, thus
$B^{+}(\Psi^{1},\varphi)=\\{W\\_Fit(101)\leftarrow W_{1}(101)\oplus
W_{2}(101)\\}$, and $B^{-}(\Psi^{1},\varphi)=\emptyset$, as
$v_{1}(\neg(W_{1}(101)\oplus W_{2}(101)))={\tt f}$. Hence $\langle
W\\_Fit(101),{\tt t}\rangle$ is inserted in $\Psi^{2}$.
$\bullet$ For $\varphi=W\\_Fit(202)$, $v_{1}(W_{1}(202)\oplus W_{2}(202))={\tt
f}\oplus{\tt t}={\tt b}$, implying that
$B^{+}(\Psi^{1},\varphi)=\\{W\\_Fit(202)\leftarrow
W_{1}(202)\,\oplus\,W_{2}(202)\\}$, and that $B^{-}(\Psi^{1},\varphi)=\\{\neg
W\\_Fit(202)\leftarrow\neg(W_{1}(202)\oplus W_{2}(202))\\}$. So $\langle
W\\_Fit(202),{\tt b}\rangle$ is inserted in $\Psi^{2}$.
$\bullet$ For $\varphi=W\\_Fit(303)$, $v_{1}(W_{1}(303)\oplus W_{2}(303))={\tt
f}\oplus{\tt n}={\tt f}$, thus $B^{+}(\Psi^{1},\varphi)=\emptyset$, and
$B^{-}(\Psi^{1},\varphi)=\\{\neg W\\_Fit(303)\leftarrow\neg(W_{1}(303)\oplus
W_{2}(303))\\}$. So, $\langle W\\_Fit(303),{\tt f}\rangle$ is inserted in
$\Psi^{2}$.

Considering now $\rho_{2}$ and $\rho^{\prime}_{2}$, which are the only rules
whose head involves $H\\_Fit$, we have the following:
$\bullet$ For $\varphi=H\\_Fit(101)$, $v_{1}(H_{1}(101)\oplus H_{2}(101))={\tt
f}\oplus{\tt f}={\tt f}$, thus
$B^{+}(\Psi^{1},\varphi)=\\{H\\_Fit(101)\leftarrow\neg(H_{1}(101)\oplus
H_{2}(101))\\}$, and $B^{-}(\Psi^{1},\varphi)=\emptyset$. Hence $\langle
H\\_Fit(101),{\tt t}\rangle$ is inserted in $\Psi^{2}$.
$\bullet$ For $\varphi=H\\_Fit(202)$, $v_{1}(H_{1}(202)\oplus H_{2}(202))={\tt
n}\oplus{\tt t}={\tt t}$, thus we obtain that
$B^{+}(\Psi^{1},\varphi)=\emptyset$, and that $B^{-}(\Psi^{1},\varphi)=\\{\neg
H\\_Fit(202)\leftarrow H_{1}(202)\oplus H_{2}(202)\\}$. Hence $\langle
H\\_Fit(202),{\tt f}\rangle$ is inserted in $\Psi^{2}$.
$\bullet$ For $\varphi=H\\_Fit(303)$, $v_{1}(H_{1}(303)\oplus H_{2}(303))={\tt
n}\oplus{\tt n}={\tt n}$, thus
$B^{+}(\Psi^{1},\varphi)=B^{-}(\Psi^{1},\varphi)=\emptyset$, which implies no
modification of $\Psi^{2}$.
Since no other rule can be applied at this stage, we have:

$\Psi^{2}=E\cup\\{\langle W\\_Fit(101),{\tt t}\rangle,$ $\langle
W\\_Fit(202),{\tt b}\rangle,$ $\langle W\\_Fit(303),{\tt f}\rangle,$

$\langle H\\_Fit(101),{\tt t}\rangle,$ $\langle H\\_Fit(202),{\tt
f}\rangle\\}$.

(3) When computing $\Psi^{3}=\Psi_{\Delta}(\Psi^{2})$, $\rho_{3}$ and
$\rho^{\prime}_{3}$ are the only rules involving atoms occurring in $\Psi^{2}$
and not in $\Psi^{1}$. The computations are as follows:
$\bullet$ For $\varphi=Fit(101)$, $v_{2}(W\\_Fit(101)\wedge H\\_Fit(101))={\tt
t}\wedge{\tt t}={\tt t}$, thus $B^{+}(\Psi^{2},\varphi)=\\{Fit(101)\leftarrow
W\\_Fit(101)\wedge H\\_Fit(101)\\}$, and $B^{-}(\Psi^{2},\varphi)=\emptyset$.
Hence $\langle Fit(101),{\tt t}\rangle$ is inserted in $\Psi^{3}$.
$\bullet$ For $\varphi=Fit(202)$, $v_{2}(W\\_Fit(202)\wedge H\\_Fit(202))={\tt
b}\wedge{\tt f}={\tt f}$, thus we obtain that
$B^{+}(\Psi^{1},\varphi)=\emptyset$, and that $B^{-}(\Psi^{1},\varphi)=\\{\neg
Fit(202)\leftarrow\neg(W\\_Fit(202)\wedge H\\_Fit(202))\\}$. Hence $\langle
Fit(202),{\tt f}\rangle$ is inserted in $\Psi^{3}$.
$\bullet$ For $\varphi=Fit(303)$, $v_{2}(W\\_Fit(303)\wedge H\\_Fit(303))={\tt
f}\wedge{\tt n}={\tt f}$, thus $B^{+}(\Psi^{1},\varphi)=\emptyset$ and
$B^{-}(\Psi^{1},\varphi)=\\{\neg Fit(303)\leftarrow\neg(W\\_Fit(303)\wedge
H\\_Fit(303))\\}$. Hence $\langle Fit(303),{\tt f}\rangle$ is inserted in
$\Psi^{3}$. We therefore obtain:

$\Psi^{3}=\Psi^{2}\cup\\{\langle Fit(101),{\tt t}\rangle,$ $\langle
Fit(202),{\tt f}\rangle,$ $\langle Fit(303),{\tt f}\rangle\\}$.

(4) When computing $\Psi^{4}=\Psi_{\Delta}(\Psi^{3})$, $\rho_{4}$ is the only
rule applying to the atoms occurring in $\Psi^{3}$ and not in $\Psi^{2}$, and
this rule generates ground atoms of the form $Alert(ID,l)$. In this case, for
every such atom, $B^{-}(Alert(ID,l),\Psi_{3})$ is always empty. On the other
hand, since for all $ID$ and $l$, $\neg Fit(ID)\otimes(Species(ID,s)\wedge
Fragile(s,l))$ is valid if and only if all involved literals are valid, the
only cases for which $B^{+}(Alert(ID,l),\Psi_{3})$ is not empty are when the
triple $(ID,s,l)$ is either $(202,s_{1},low)$ or $(303,s_{2},high)$. The
corresponding computations are as follows:
$\bullet$ For $(202,s_{1},low)$ thus for $\varphi=Alert(202,low)$, $v_{3}(\neg
Fit(101)\otimes(Species(202,s_{1})\wedge Fragile(s_{2},low)))={\tt
t}\otimes({\tt t}\wedge{\tt t})={\tt t}$. Thus, $\langle Alert(202,low),{\tt
t}\rangle$ is inserted in $\Psi^{4}$.
$\bullet$ Similar computations for $\varphi=Alert(303,high)$ lead to insert
$\langle Alert(303,high),{\tt t}\rangle$ in $\Psi^{4}$. We therefore obtain:

$\Psi^{4}=\Psi^{3}\cup\\{\langle Alert(202,low),{\tt t}\rangle,$ $\langle
Alert(303,high),{\tt t}\rangle\\}$.

(5) As no further computations can generate new elements based on $\Psi^{4}$
above, we obtain that $sem(\Delta)=\Psi^{4}$. $\Box$

The following proposition states basic properties of our database semantics.

###### Proposition 1

Given a database $\Delta=(E,R)$:

1\. $sem(\Delta)$ is a v-set such that $E\preceq_{k}sem(\Delta)$.
2\. For every rule $\rho$ in $inst(R)$ such that $v_{\Delta}(body(\rho))$ is
in $\\{{\tt t},{\tt b}\\}$, it holds that
$v_{\Delta}(body(\rho))\preceq_{k}v_{\Delta}(head(\rho))$.

###### Proof

1\. $sem(\Delta)$ is a v-set because the definition of $\Psi_{\Delta}$ implies
that it is not possible for a ground atom $\varphi$ to occur in two distinct
pairs in $sem(\Delta)$. Moreover,
$v_{E}(\varphi)\preceq_{k}v_{\Delta}(\varphi)$ also holds for every $\varphi$
as a consequence of the definition of $\Psi_{\Delta}$.

2\. Let $\rho$ be in $inst(R)$ such that $v_{\Delta}(body(\rho))$ is in
$\\{{\tt t},{\tt b}\\}$. Let $i_{0}$ be the least index such that the truth
value ${\tt v}_{b}$ of $body(\rho)$ in $\Psi^{i_{0}}$ is ${\tt t}$ or ${\tt
b}$ when computing $sem(\Delta)$. By Definition 3, if ${\tt v}_{h}$ denotes
the truth value of $head(\rho)$ in $\Psi^{i_{0}}$, we have ${\tt
v}_{b}\preceq_{k}{\tt v}_{h}$, and by monotonicity of $\Psi_{\Delta}$, this
holds in $sem(\Delta)$, which completes the proof. $\Box$

We emphasize that, by Proposition 1(1), we have $E\preceq_{k}sem(\Delta)$,
which intuitively means that the semantics extends the knowledge provided by
the database extension $E$. This also means that our semantics gives priority
to the rules over the extension. It should be noticed that such is not the
case in most approaches to deductive databases. Indeed, in standard deductive
approaches CeriGT90, as well as in Fitting90, the atoms in $E$ are restricted
to involve extensional predicate symbols, that is predicate symbols not
allowed to occur in the heads of the rules. On the other hand, although
extensional predicate symbols are not considered in Lau2019, priority is
nevertheless given to the database extension, because instantiated rules whose
head involves an atom occurring in $E$ are not ‘triggered’. Notice however
that considering such restrictions in the context of the present work is
possible and raises no difficulty.

###  3.3 Comparison with Fitting90; Fitting91 and with Arieli02

Considering first Fitting90; Fitting91, our approach is closely related to
what is called k-existential programs, where the rules are expressions of the
form $h(X)\leftarrow body(X,Y)$ such that:

  * •

The head $h(X)$ is a positive literal whose free variables in $X$ all occur in
$body(X,Y)$. It is also assumed that the variables in $X$ are the only free
variables in $body(X,Y)$.

  * •

The right hand-side $body(X,Y)$ is a well-formed formula involving $\neg$,
$\wedge$, $\vee$, $\otimes$, $\oplus$ and the quantifier $\sum$ (where the
truth value of $\left(\sum Y\right)(\Phi(Y))$ is defined as the least upper-
bound with respect to $\preceq_{k}$ of the truth values of all instances of
$\Phi(Y)$).

  * •

It is not allowed that the heads of two distinct rules in a given program
involve the same predicate symbol.

It turns out that, with respect to rules as defined in Definition 1, the main
differences are as follows:

  1. 1.

We allow positive and negative literals in the heads of the rules, whereas
negative literals are not allowed in the head of the rules in Fitting90.

  2. 2.

We do not restrict different rules to involve different predicate symbols in
their heads, as done in Fitting90.

  3. 3.

However, the quantifier $\sum$ is allowed in the bodies of the rules in
Fitting90, which is not the case in our approach. Notice in this respect that
our approach implicitly assumes that in a rule $h(X)\leftarrow body(X,Y)$, the
variables in $Y$ are bounded to a quantifier $\sum$. That is, according to
Fitting90, the rule would be written as $h(X)\leftarrow\left(\sum
Y\right)body(X,Y)$.

Additionally to these syntactical differences, rules are not processed in
Fitting90; Fitting91 as we do in our approach. Indeed, although database
semantics is defined as the least fixed point of a monotonic operator with
respect to $\preceq_{k}$, the two operators behave in different ways, given an
instantiated rule $\varphi\leftarrow\Phi$ and a v-set $V$:

  * •

According to Fitting90; Fitting91, the operator assigns $\varphi$ the truth
value in $V$ of $\Phi$.

  * •

In our approach, assuming that there is no other rule whose head is $\varphi$,
$\varphi$ is assigned the truth value in $V$ of $\Phi$ only if this truth
value is designated (i.e., ${\tt t}$ or ${\tt b}$). Otherwise the truth value
of $\phi$ is set to ${\tt n}$.

This difference in computing database semantics is very important because it
implies that the intuition behind the rules is different. Indeed, roughly
speaking, according to Fitting90; Fitting91, rules are seen as equivalences
since the head and the body are assigned the same truth value (assuming no
interaction between the rules), whereas in our approach, rules are considered
as implications, as will be discussed in the next section.

To illustrate the difference, let $Student(Bob)\leftarrow PhD\\_Student(Bob)$
be an instantiated rule whose intuition is obvious. If it is known in the
database that $PhD\\_Student(Bob)$ has truth value ${\tt f}$ then, according
to Fitting90; Fitting91, $Student(Bob)$ has also truth value ${\tt f}$, which
is counter intuitive. In our approach, the truth value of $Student(Bob)$ is
${\tt n}$, which better fits the intuition.

Comparing now our approach with that in Arieli02, we notice the following
syntactical similarities and differences:

  * •

According to Arieli02, rule heads may involve positive or negative literals,
as we do in our approach.

  * •

However, in Arieli02, rule bodies are restricted to only involve the
connectors $\neg$ and $\wedge$ as for Datalogneg rules CeriGT90, whereas in
our approach more connectors are allowed.

  * •

In Arieli02, as in our approach, but contrary to Fitting90; Fitting91, several
rules involving the same predicate are allowed.

Regarding semantics, rules are triggered in Arieli02 according to the same
policy as in our approach, but in the following different way: given an
instantiated rule $\varphi\leftarrow\Phi$ and a v-set $V$, if the truth value
in $V$ of $\Phi$ is designated (i.e., ${\tt t}$ or ${\tt b}$), then the truth
value of $\varphi$ is set to ${\tt t}$. Otherwise the truth value of $\varphi$
is set to ${\tt n}$.

To see the impact of the above way of handling rules, consider again the
instantiated rule $Student(Bob)\leftarrow PhD\\_Student(Bob)$. As above, if it
is known in the database that $PhD\\_Student(Bob)$ has truth value ${\tt f}$
then, according to Arieli02, the truth value of $Student(Bob)$ is ${\tt n}$,
as done in our approach.

On the other hand, assume that a problem regarding Bob’s status has lead to
assign $PhD\\_Student(Bob)$ the truth value ${\tt b}$. Then, according to
Arieli02, the truth value of $Student(Bob)$ is set to ${\tt t}$, whereas,
according to our approach, $Student(Bob)$ is assigned the truth value ${\tt
b}$, which we think, better fits the intuition.

To end the comparison with Arieli02, we note that Arieli02 addresses two
important issues not addressed in the present paper, namely $(i)$ the
semantics of negation as failure in the context of Four-valued logic, and
$(ii)$ prioritized logic programs. We do not discuss these issues any further
as they lie outside the scope of this paper.

We end the section by providing an example to illustrate the three approaches
more thoroughly than done above.

###### Example 3

We illustrate below the main differences between the three approaches using
very simple examples. In doing so we denote by $sem_{F}(\Delta)$ and
$sem_{A}(\Delta)$ the semantics of a database $\Delta$ according to Fitting’s
and Arieli’s semantics, respectively. The explanations on how the semantics is
obtained are omitted, since they are very easy.

Case 1.

Let $\Delta_{1}=(\\{\langle q,{\tt f}\rangle\\},\\{p\leftarrow q\\})$. In this
case, $sem_{F}(\Delta_{1})=\\{\langle q,{\tt f}\rangle,\langle p,{\tt
f}\rangle\\}$, $sem_{A}(\Delta_{1})=\\{\langle q,{\tt f}\rangle\\}$, and
$sem(\Delta_{1})=\\{\langle q,{\tt f}\rangle\\}$.

Case 2.

Let $\Delta_{2}=(\\{\langle q,{\tt b}\rangle\\},\\{p\leftarrow q\\})$. In this
case, $sem_{F}(\Delta_{2})=\\{\langle q,{\tt b}\rangle,\langle p,{\tt
b}\rangle\\}$, $sem_{A}(\Delta_{2})=\\{\langle q,{\tt b}\rangle,\langle p,{\tt
t}\rangle\\}$, and $sem(\Delta_{2})=\\{\langle q,{\tt b}\rangle,\langle p,{\tt
b}\rangle\\}$.

Case 3.

Let $\Delta_{3}=(\\{\langle q,{\tt t}\rangle\\},\\{\neg p\leftarrow q\\})$. In
this case, $sem_{F}(\Delta_{3})$ is undefined, $sem_{A}(\Delta_{3})=\\{\langle
q,{\tt t}\rangle,\langle p,{\tt f}\rangle\\}$, and $sem(\Delta_{3})=\\{\langle
q,{\tt t}\rangle,\langle p,{\tt f}\rangle\\}$.

Case 4.

Let $\Delta_{4}=(\\{\langle q,{\tt t}\rangle\\},\\{p\leftarrow\neg q\\})$. In
this case, $sem_{F}(\Delta_{4})=\\{\langle q,{\tt t}\rangle,\langle p,{\tt
f}\rangle\\}$, $sem_{A}(\Delta_{4})=\\{\langle q,{\tt t}\rangle\\}$, and
$sem(\Delta_{4})=\\{\langle q,{\tt t}\rangle\\}$.

Case 5.

Let $\Delta_{5}=(\\{\langle q,{\tt f}\rangle\\},\\{p\leftarrow q\oplus r\\})$.
In this case, $sem_{F}(\Delta_{5})=\\{\langle q,{\tt f}\rangle,\langle p,{\tt
f}\rangle\\}$, $sem_{A}(\Delta_{5})$ is undefined, and
$sem(\Delta_{5})=\\{\langle q,{\tt f}\rangle\\}$.

Case 6.

Let $\Delta_{6}=(\\{\langle q,{\tt t}\rangle,\langle r,{\tt
f}\rangle\\},\\{p\leftarrow q\oplus r\\})$. In this case,
$sem_{F}(\Delta_{6})=\\{\langle q,{\tt t}\rangle,$ $\langle r,{\tt f}\rangle,$
$\langle p,{\tt b}\rangle\\}$, $sem_{A}(\Delta_{6})$ is undefined, and
$sem(\Delta_{6})=\\{\langle q,{\tt t}\rangle,\langle r,{\tt f}\rangle,\langle
p,{\tt b}\rangle\\}$.

Case 7.

Let $\Delta_{7}=(\\{\langle q,{\tt t}\rangle,\langle r,{\tt
f}\rangle\\},\\{p\leftarrow q,p\leftarrow r\\})$. In this case,
$sem_{F}(\Delta_{7})$ is undefined, $sem_{A}(\Delta_{7})=\\{\langle q,{\tt
t}\rangle,\langle r,{\tt f}\rangle,\langle p,{\tt t}\rangle\\}$, and
$sem(\Delta_{7})=\\{\langle q,{\tt t}\rangle,\langle r,{\tt f}\rangle,\langle
p,{\tt t}\rangle\\}$.

Case 8.

Let $\Delta_{8}=(\\{\langle q,{\tt t}\rangle,\langle r,{\tt
f}\rangle\\},\\{p\leftarrow q\vee r\\})$. In this case,
$sem_{F}(\Delta_{8})=\\{\langle q,{\tt t}\rangle,$ $\langle r,{\tt f}\rangle,$
$\langle p,{\tt t}\rangle\\}$, $sem_{A}(\Delta_{8})$ is undefined, and
$sem(\Delta_{8})=\\{\langle q,{\tt t}\rangle,\langle r,{\tt f}\rangle,\langle
p,{\tt t}\rangle\\}$.

Case 9.

Let $\Delta_{9}=(\\{\langle q,{\tt t}\rangle,\langle r,{\tt
f}\rangle\\},\\{p\leftarrow q\vee r,p\leftarrow q\\})$. In this case,
$sem_{F}(\Delta_{9})$ is undefined, $sem_{A}(\Delta_{9})$ is undefined, and
$sem(\Delta_{9})=\\{\langle q,{\tt t}\rangle,\langle r,{\tt f}\rangle,\langle
p,{\tt t}\rangle\\}$.

To illustrate a case with a recursive set of rules with unstratified negation,
let $R=\\{p\leftarrow\neg p\\}$. First, if $\Delta=(\emptyset,R)$, it is easy
to see that $sem_{F}(\Delta)=sem_{A}(\Delta)=sem(\Delta)=\emptyset$, because
the rule is not triggered.

If $\Delta=(\\{\langle p,{\tt t}\rangle\\},R)$ then $sem_{F}(\Delta)$ is not
defined because according to Fitting90; Fitting91, $\Delta$ contains two rules
with head equal to $p$. On the other hand, we have
$sem_{A}(\Delta)=sem(\Delta)=\\{\langle p,{\tt t}\rangle\\}$. Simlarly, it is
easy to see that if $\Delta=(\\{\langle p,{\tt f}\rangle\\},R)$ then
$sem_{F}(\Delta)$ is not defined, whereas
$sem_{A}(\Delta)=sem(\Delta)=\\{\langle p,{\tt b}\rangle\\}$. $\Box$

##  4 Database Semantics vs. Database Models

###  4.1 Database Models

Based on the above discussion about $k$-existential clauses as defined in
Fitting90, every rule $\rho:h(X)\leftarrow B(X,Y)$ in our approach is
associated with the following formula in the Four-valued logic, denoted by
$\rho^{\to}$:

$\rho^{\to}:(\forall X)\left(\left(\sum Y\right)(B(X,Y)\to h(X))\right)$.

We recall that the implication $\to$ in $\rho^{\to}$ is generic, that is it
can be replaced by any of the three implications $\to_{1}$, $\to_{2}$ or
$\to_{3}$ (see our discussion at the end of Section 2). The notion of database
model is now defined as follows.

###### Definition 5

Given $\Delta=(E,R)$, a v-set $M$ is a model of $\Delta$ if:
$-$ $E\preceq_{k}M$, and
$-$ for every $\rho$ in $R$, $\rho^{\to}$ is valid in $M$ (i.e.,
$v_{M}(\rho^{\to})$ is ${\tt t}$ or ${\tt b}$).

A model $M$ is said to be $k$-minimal if there does not exist a model
$M^{\prime}$ such that $M^{\prime}\neq M$ and $M^{\prime}\preceq_{k}M$.

A model $M$ is said to be $k$-increasing if for every $\rho$ in $inst(R)$ such
that $v_{M}(body(\rho))$ is in $\\{{\tt t},{\tt b}\\}$,
$v_{M}(body(\rho))\preceq_{k}v_{M}(head(\rho))$. $\Box$

To state that $sem(\Delta)$ is the unique $k$-minimal and $k$-increasing model
of $\Delta$, we show the following lemma.

###### Lemma 2

If $M_{1}$ and $M_{2}$ are two v-sets, let us denote by $M_{1}\otimes M_{2}$
the v-set $M$ such that for every $\varphi$ in ${\cal HB}$,
$v_{M}(\varphi)=v_{M_{1}}(\varphi)\otimes v_{M_{2}}(\varphi)$.

Given $\Delta=(E,R)$, if $M_{1}$ and $M_{2}$ are $k$-increasing models of
$\Delta$ then $M=M_{1}\otimes M_{2}$ is also a $k$-increasing model of
$\Delta$.

###### Proof

For every $\langle\varphi,{\tt v}\rangle$ in $E$, we have
$v_{E}(\varphi)\preceq_{k}v_{M_{i}}(\varphi)$ for $i=1,2$. Thus,
$v_{E}(\varphi)\preceq_{k}v_{M_{1}}(\varphi)\otimes v_{M_{2}}(\varphi)$, that
is $v_{E}(\varphi)\preceq_{k}v_{M}(\varphi)$ holds. Therefore, $E\preceq_{k}M$
holds.

Let $\rho:h(X)\leftarrow B(X,Y)$ be in $R$ and $h(\alpha)\leftarrow
B(\alpha,\beta)$ an instance of $\rho$ such that $v_{M}(body(\rho))$ is in
$\\{{\tt t},{\tt b}\\}$. Since for $i=1,2$, $M\preceq_{k}M_{i}$,
$v_{M_{i}}(body(\rho))$ is in $\\{{\tt t},{\tt b}\\}$. Hence, for $i=1,2$,
$v_{M_{i}}(B(\alpha,\beta))\preceq_{k}v_{M_{i}}(h(\alpha))$ holds because
$M_{i}$ is $k$-increasing. On the other hand, since the connectors involved in
$B(\alpha,\beta)$ are monotonic with respect to $\preceq_{k}$,
$v_{M}(B(\alpha,\beta))\preceq_{k}v_{M_{i}}(B(\alpha,\beta))$ for $i=1,2$. We
thus obtain for $i=1,2$,
$v_{M}(B(\alpha,\beta))\preceq_{k}v_{M_{i}}(B(\alpha,\beta))\preceq_{k}v_{M_{i}}(h(\alpha))$,
hence that $v_{M}(B(\alpha,\beta))\preceq_{k}v_{M_{1}}(h(\alpha))\otimes
v_{M_{2}}(h(\alpha))$. That is
$v_{M}(B(\alpha,\beta))\preceq_{k}v_{M}(h(\alpha))$.

To show that $\rho^{\to}$ is valid in $M$, we notice that
$\phi_{1}\to\phi_{2}$ is valid in $M$ if either $\phi_{1}$ is not valid in
$M$, or otherwise, if $v_{M}(\phi_{1})\preceq_{k}v_{M}(\phi_{2})$ (this can be
seen from the truth tables of $\to_{i}$ for $i=1,2,3$, as shown in Figure 2).
Hence, for every $\rho$ in $R$, all instances of $\rho^{\to}$ are valid in
$M$, that is for all instances $\alpha$ and $\beta$ of $X$ and $Y$
respectively, $B(\alpha,\beta)\to h(\alpha)$ is valid in $M$. This implies
that $(\sum Y)(B(\alpha,Y))\to h(\alpha)$ is valid in $M$ (because by the
truth table of $\oplus$ in Figure 1, the ‘sum’ of valid formulas is a valid
formula). Since the truth table of $\wedge$ in Figure 1 shows that the
conjunction of valid formulas is valid, $(\forall X)((\sum Y)(B(X,Y)\to
h(X)))$, that is $\rho^{\to}$, is valid in $M$. Thus $M$ is a $k$-increasing
model of $\Delta$, and the proof is complete. $\Box$

###### Proposition 2

Given a database $\Delta=(E,R)$, $sem(\Delta)$ is the unique $k$-minimal and
$k$-increasing model of $\Delta$.

###### Proof

We first show that $sem(\Delta)$ is a $k$-increasing model of $\Delta$. First,
for every $\varphi$ occurring in $E$,
$v_{E}(\varphi)\preceq_{k}v_{\Delta}(\varphi)$ holds because of Proposition
1(1). For every $\rho:h(X)\leftarrow B(X,Y)$ in $R$, $\rho^{\to}$ is shown to
be valid in $sem(\Delta)$ in the same way as, in the previous proof,
$\rho^{\to}$ has been shown to be valid in $M$. Since Proposition 1(2) shows
that $sem(\Delta)$ is $k$-increasing, $sem(\Delta)$ is a $k$-increasing model
of $\Delta$.

Regarding $k$-minimality, let $M$ be a $k$-increasing model of $\Delta$ such
that $M\prec_{k}sem(\Delta)$. Then, for every ground atom $\varphi$,
$v_{M}(\varphi)\preceq_{k}v_{\Delta}(\varphi)$ and there exists at least one
ground atom $\varphi_{0}$ such that $v_{M}(\varphi_{0})\neq
v_{\Delta}(\varphi_{0})$. This implies that every such atom $\varphi_{0}$ is
such that $v_{\Delta}(\varphi_{0})\neq{\tt n}$, and so, that $\varphi_{0}$
occurs in $sem(\Delta)$.

We now argue that every such $\varphi_{0}$ occurs in the head of at least one
rule in $inst(R)$ such that $v_{\Delta}(body(\rho))$ is in $\\{{\tt t},{\tt
b}\\}$. Indeed, otherwise, $\varphi_{0}$ would occur in $E$ and we would have
$v_{\Delta}(\varphi_{0})=v_{E}(\varphi_{0})$. As $M$ is a model of $\Delta$,
we have $v_{E}(\varphi_{0})\preceq_{k}v_{M}(\varphi_{0})$, and so
$v_{\Delta}(\varphi_{0})\preceq_{k}v_{M}(\varphi_{0})$, which is a
contradiction.

Hence, given such an atom $\varphi_{0}$, let $i_{0}$ be the least index such
that $v_{M}(\varphi_{0})\prec_{k}v_{i_{0}}(\varphi_{0})$, where $v_{i_{0}}$
denotes the interpretation induced by $\Psi^{i_{0}}$. Since
$\Psi^{0}\preceq_{k}M$ (because $\Psi^{0}=\emptyset$), it must be that
$i_{0}>0$, meaning that $\Psi^{i_{0}}=\Psi_{\Delta}(\Psi^{i_{0}-1})$ and
$\Psi^{i_{0}-1}\preceq_{k}M$. Moreover, by definition of $\Psi_{\Delta}$,
$v_{i_{0}}(\varphi_{0})$ is written as:

$v_{i_{0}}(\varphi_{0})=v_{E}(\varphi_{0})$ | $\oplus\bigoplus_{\rho\in B^{+}(\Psi^{i_{0}-1},\varphi_{0})}(v_{i_{0}-1}(body(\rho)))$
---|---
| $\oplus\bigoplus_{\rho\in B^{-}(\Psi^{i_{0}-1},\varphi_{0})}(\neg
v_{i_{0}-1}(body(\rho)))$

where $v_{i_{0}-1}$ is the interpretation induced by $\Psi^{i_{0}-1}$. Since
for every $body(\rho)$ involved in the above expression we have
$v_{i_{0}-1}(body(\rho))\preceq_{k}v_{\Delta}(body(\rho))\preceq_{k}v_{M}(body(\rho))$
and since we assume that $M$ satisfies
$v_{M}(body(\rho))\preceq_{k}v_{M}(head(\rho))$, we obtain
$v_{i_{0}-1}(\varphi_{0})\preceq_{k}v_{M}(head(\rho))$. Since $head(\rho)$ is
either $\varphi_{0}$ (if $\rho\in B^{+}(\varphi_{0})$) or $\neg\varphi_{0}$
(if $\rho\in B^{-}(\varphi_{0})$), we have
$v_{i_{0}-1}(\varphi_{0})\preceq_{k}v_{M}(\varphi_{0})$ if $\rho\in
B^{+}(\varphi_{0})$ and, if $\rho\in B^{-}(\varphi_{0})$,
$v_{i_{0}-1}(\varphi_{0})\preceq_{k}v_{M}(\neg\varphi_{0})$, which is
equivalent to $\neg v_{i_{0}-1}(\varphi_{0})\preceq_{k}v_{M}(\varphi_{0})$
(since for all truth values ${\tt v}_{1}$ and ${\tt v}_{2}$, ${\tt
v}_{1}\preceq_{k}{\tt v}_{2}$ holds if and only if $\neg{\tt
v}_{1}\preceq_{k}\neg{\tt v}_{2}$ holds).

Therefore, $v_{i_{0}}(\varphi_{0})\preceq_{k}v_{E}(\varphi_{0})\oplus
v_{M}(\varphi_{0})$, and as $v_{E}(\varphi_{0})\preceq_{k}v_{M}(\varphi_{0})$
(because $M$ is a model of $\Delta$), it follows that
$v_{i_{0}}(\varphi_{0})\preceq_{k}v_{M}(\varphi_{0})$. This is a contradiction
with our assumption that $v_{M}(\varphi_{0})\prec_{k}v_{i_{0}}(\varphi_{0})$,
and so, $sem(\Delta)$ is $k$-minimal.

To show the unicity of $sem(\Delta)$, let $M$ be another $k$-minimal and
$k$-increasing model of $\Delta$. By Lemma 2, $M^{\prime}=sem(\Delta)\otimes
M$ is also a $k$-increasing model of $\Delta$, and moreover, we have
$M^{\prime}\preceq_{k}M$ and $M^{\prime}\preceq_{k}sem(\Delta)$. Since $M$ and
$sem(\Delta)$ are assumed to be $k$-minimal, we also have
$M\preceq_{k}M^{\prime}$ and $sem(\Delta)\preceq_{k}M^{\prime}$. Therefore,
$M=M^{\prime}=sem(\Delta)$, and the proof is complete. $\Box$

It turns out that Proposition 2 expresses properties of database semantics
similar to well-known properties of Datalog databases CeriGT90 whereby the
semantics of a Datalog database is its unique minimal (with respect to set-
inclusion) model, when rules $h(X)\leftarrow B(X,Y)$ are seen as formulas
$(\forall X)((\exists Y)(B(X,Y)\Rightarrow h(X)))$.

Regarding the comparison of the truth values of the body and the head of the
rules in the case of Datalog databases, when considering the ordering
$\preceq_{t}$, it is easy to see that for all instances $\alpha$ and $\beta$
of $X$ and $Y$, respectively,
$v_{I}(B(\alpha,\beta))\preceq_{t}v_{I}(h(\alpha))$ holds whenever
$B(\alpha,\beta)\Rightarrow h(\alpha)$ is valid in a two-valued interpretation
$I$.

The result in Proposition 2 shows that, as for $k$-existential program
semantics Fitting90 and paraconsistent logic programs semantics in Arieli02,
database semantics in our approach is minimal with respect to the knowledge
ordering. However, it should be noticed that:

  * •

In Fitting90 $k$-minimality is expressed with respect to the set of fix-points
of the associated consequence operator, with no consideration of the most
generic notion of database model.

  * •

In Arieli02, the results are shown only for the implication denoted here by
$\to_{1}$, whereas our results hold for $\to_{1}$ as well as for two other
implications, namely $\to_{2}$ and $\to_{3}$.

  * •

In Arieli02, the notion of model is similar to ours, but $k$-minimality is
shown in a context more restrictive than our context.

  * •

In Arieli02, the uniqueness of the $k$-minimal model is shown by minimizing
inconsistency, whereas in our approach, the uniqueness of the $k$-minimal
model is shown using a monotonic criterion involving the head and the body of
instantiated rules.

###  4.2 Finite Database Semantics

An important issue in rule based databases is that a database can have
infinite semantics when ${\cal HB}$ is infinite. This point is indeed
problematic because in such cases, answers to some queries can be infinite,
which is not acceptable in practice.

As a simple case, consider a database $\Delta=(E,R)$ where $E=\\{\langle
S(a),{\tt t}\rangle\\}$ and $R=\\{P(x,y)\leftarrow Q(x,y)\vee S(x)\\}$. Based
on the truth table of $\vee$ shown in Figure 1, for all $\alpha$ and $\beta$
in ${\cal H}$, $Q(\alpha,\beta)\vee S(\alpha)$ is true if so is $S(\alpha)$.
Hence, $sem(\Delta)=\\{\langle S(a),{\tt t}\rangle\\}\cup\\{\langle
P(a,\beta),{\tt t}\rangle~{}|~{}\beta\in{\cal H}\\}$, which is infinite when
${\cal H}$ is infinite.

To cope with this difficulty, we define the notion of safe rules, inspired by
the case of Datalogneg databases CeriGT90. To see how the two approaches are
related regarding this issue, let ${\cal
D}=(\\{S(a)\\},\\{P(x,y)\leftarrow\neg Q(x,y)\wedge S(x)\\})$ be a Datalogneg
database, whose semantics is $\\{S(a)\\}\cup\\{P(a,\beta)~{}|~{}\beta\in{\cal
H}\\}$. This result is somehow similar to that for $\Delta$ above, and the
rule in ${\cal D}$ is clearly not safe since the variable $y$ in $\neg Q(x,y)$
occurs in no positive literal in the body of the rule.

To define safe rules in our context, we need some preliminary definitions and
notation as detailed next. First, we adapt the notion of active domain in
relational databases Ullman to our approach as follows. Given a universe
${\cal H}$, its associated Herbrand base ${\cal HB}$ and a database
$\Delta=(E,R)$ over ${\cal HB}$, we call active domain of $\Delta$, denoted by
${\cal A}(\Delta)$, the subset of ${\cal H}$ containing all the constants
occurring in $\Delta$. Then the active Herbrand base of $\Delta$, denoted by
${\cal AB}(\Delta)$ is the set of all facts in ${\cal HB}$ that only involve
constants in ${\cal A}(\Delta)$. Notice that ${\cal A}(\Delta)$ and ${\cal
AB}(\Delta)$ are finite sets, even if ${\cal H}$ is infinite, because $E$ and
$R$ are assumed to be finite. We first define the notion of active domain
preserving rule as follows.

###### Definition 6

Given a Herbrand base ${\cal HB}$, a rule $\rho$ is said to be active domain
preserving if for every database $\Delta=(E,\\{\rho\\})$ where $E$ is an
arbitrary finite v-set involving facts in ${\cal HB}$, $sem(\Delta)$ involves
only facts in ${\cal AB}(\Delta)$. $\Box$

We also adapt the usual notion of disjunctive normal form of a formula to the
context of Four-valued logic. To this end, we recall from Fitting91; Tsoukias
the following standard properties of the connectors of the Four-valued logic:

$\bullet$ $\neg(\phi_{1}\vee\phi_{2})\equiv\neg\phi_{1}\wedge\neg\phi_{2}$ ;
$\neg(\phi_{1}\wedge\phi_{2})\equiv\neg\phi_{1}\vee\neg\phi_{2}$

$\bullet$ $\neg(\phi_{1}\oplus\phi_{2})\equiv\neg\phi_{1}\oplus\neg\phi_{2}$ ;
$\neg(\phi_{1}\otimes\phi_{2})\equiv\neg\phi_{1}\otimes\neg\phi_{2}$

$\bullet$ Distributivity: for all distinct binary connectors $\star$ and
$\bullet$ in $\\{\vee,\wedge,\oplus,\otimes\\}$

$\phi_{1}\star(\phi_{2}\bullet\phi_{3})\equiv(\phi_{1}\star\phi_{2})\bullet(\phi_{1}\star\phi_{3})$.

Using these properties, any quantifier free formula $\Phi$ can be transformed
into an equivalent formula according to the following steps:

  1. 1.

$\vee$-transformation: $\Phi\equiv\Phi_{1}\vee\Phi_{2}\vee\ldots\vee\Phi_{n}$
where, for every $i$ in $\\{1,2,\ldots,n\\}$, $\Phi_{i}$ does not involve the
connector $\vee$. Every $\Phi_{i}$ is called a $\vee$-component of $\Phi$.

  2. 2.

$\oplus$-transformation: For every $i$ in $\\{1,2,\ldots,n\\}$, $\Phi_{i}$ is
transformed into its equivalent $\oplus$-normal form
$\Phi_{i}^{1}\oplus\Phi_{i}^{2}\oplus\ldots\oplus\Phi_{i}^{p_{i}}$ where, for
$j$ in $\\{1,2,\ldots,p_{i}\\}$, $\Phi_{i}^{j}$ does not involve the connector
$\oplus$. Every $\Phi_{i}^{j}$ is called a $\oplus$-component of $\Phi_{i}$.

  3. 3.

$\wedge$-transformation: For every $i$ in $\\{1,2,\ldots,n\\}$ and every $j$
in $\\{1,2,\ldots,p_{i}\\}$, $\Phi_{i}^{j}$ is transformed into its
$\wedge$-form
$\Phi_{i}^{j}\equiv(\phi_{1}^{ij}\wedge\phi_{2}^{ij}\wedge\ldots\wedge\phi_{q_{ij}}^{ij})$
where, for $k$ in $\\{1,2,\ldots,q_{ij}\\}$, $\phi_{k}^{ij}$ does not involve
the connector $\wedge$. Every $\phi_{k}^{ij}$ is called a $\wedge$-component
of $\Phi_{i}^{j}$.

  4. 4.

$\otimes$-transformation: For every $i$ in $\\{1,2,\ldots,n\\}$, every $j$ in
$\\{1,2,\ldots,p_{i}\\}$, and every $k$ in $\\{1,2,\ldots,q_{ij}\\}$,
$\phi_{k}^{ij}$ is transformed into its $\otimes$-form
$\phi_{k}^{ij}\equiv(\lambda_{k}^{1}\otimes\lambda_{k}^{2}\otimes\ldots\otimes\lambda_{k}^{r_{k}})$
where, for every $l$ in $\\{1,2,\ldots,r_{k}\\}$, every $\lambda_{k}^{l}$ is a
literal, that is of the form $\varphi$ or $\neg\varphi$ where $\varphi$ is an
atom.

Combining these transformations yields a formula equivalent to $\Phi$, called
the Four-normal form of $\Phi$. Based on the truth tables of Figure 1, given a
formula $\Phi$ involving no variable, for every v-set $S$, $\Phi$ is valid in
$S$ if and only if there exist $i_{0}$ in $\\{1,2,\ldots,n\\}$ and $j_{0}$ in
$\\{1,2,\ldots,p_{i_{0}}\\}$ such that $\Phi_{i_{0}}^{j_{0}}$ is valid in $S$,
that is if and only if at least one $\oplus$-component of $\Phi$ is valid in
$S$.

Furthermore, every $\oplus$-component $\Phi_{i_{0}}^{j_{0}}$ is valid in $S$
if and only if each of its $\wedge$-component $\phi^{i_{0}j_{0}}_{k}$ is valid
in $S$, which holds if and only if every literal $\lambda$ occurring in one of
its $\otimes$-components is valid in $S$. It follows that, for every $\lambda$
in the $\otimes$-components of $\phi_{k}^{i_{0}j_{0}}$, $v_{S}(\lambda)$ is
${\tt t}$ or ${\tt b}$ if $\lambda=\varphi$, and $v_{S}(\lambda)$ is ${\tt f}$
or ${\tt b}$ if $\lambda=\neg\varphi$.

The syntactic notion of safe rule is defined based on Four-normal form as
follows.

###### Definition 7

Given a Herbrand base ${\cal HB}$, let $\rho:h(X)\leftarrow B(X,Y)$ be a rule
such that $B(X,Y)$ is written in its Four-normal form. Then $\rho$ is said to
be safe if every $\oplus$-component in $B(X,Y)$ involves at least all
variables in $X$. $\Box$

We notice that $\Phi$ is valid in $S$ if and only if there exists an
$\oplus$-component $\Phi_{i_{0}}^{j_{0}}$ in its Four-normal form, for which
all involved literals are valid in $S$, and thus occur in $S$ with an
appropriate truth value. Based on this important remark, the following
proposition provides a syntactic characterization of active domain preserving
rules as defined in Definition 6.

###### Proposition 3

Let $\rho:h(X)\leftarrow B(X,Y)$ be a rule such that $B(X,Y)$ is written in
its Four-normal form. Then $\rho$ is safe if and only if every $\rho$ is
active domain preserving.

###### Proof

Assume first that $\rho$ is not safe. By Definition 7, there exist $i_{0}$ in
$\\{1,2,\ldots,n\\}$ and $j_{0}$ in $\\{1,2,\ldots,p_{i_{0}}\\}$ such that
$\Phi_{i_{0}}^{j_{0}}$ does not involve all variables in $X$. We write $X$ as
$X_{1}X_{2}$ to mean that the variables in $X_{1}$ occur in
$\Phi_{i_{0}}^{j_{0}}$ whereas those in $X_{2}$ do not. Let $inst$ be an
instantiation of the variables in $X_{1}$ and $\Delta=(E,\\{\rho\\})$ where
$E$ is the set of all pairs $\langle\varphi,{\tt b}\rangle$ such that
$\varphi$ occurs in $inst(\Phi_{i_{0}}^{j_{0}})$. Then
$inst(\Phi_{i_{0}}^{j_{0}})$ is valid in $E$ and so, for every extension
$inst^{*}$ of $inst$ to the variables in $X_{2}$ or in $Y$,
$inst^{*}(body(\rho))$ is valid in $E$ but might involve facts not in ${\cal
AB}(\Delta)$. Hence, $inst^{*}(h(X_{1}X_{2}))$ belongs to the semantics of
$\Delta$, meaning that, according to Definition 6, $\rho$ is not active domain
preserving.

Conversely, assume that $\rho$ is safe. By Definition 7, for every $i$ in
$\\{1,2,\ldots,n\\}$ and every $j$ in $\\{1,2,\ldots,p_{i}\\}$, $\Phi_{i}^{j}$
involves at least all variables in $X$. Then, whatever the valid
$\oplus$-component $\phi_{i_{0}}^{j_{0}}$ to make $B(X,Y)$ valid in $S$, the
instantiation of the variables in $\phi_{i_{0}}^{j_{0}}$ assigns a value to
every variable in $X$ implying that the fact involved in $inst(h(X))$ is in
${\cal AB}(\Delta)$. Thus, according to Definition 6, $\rho$ is active domain
preserving, and the proof is complete. $\Box$

The following corollary holds as an immediate consequence of Proposition 3 and
of the fact that the cardinality of ${\cal AB}(\Delta)$ is finite.

###### Corollary 1

Given $\Delta=(E,R)$, if every rule in $R$ is safe, then $sem(\Delta)$ is
finite.

Corollary 1 shows that, if rules are safe then the v-set $sem(\Delta)$
provides a finite representation of the valuation $v_{\Delta}$, in much the
same way as the database extension $E$ provides a finite representation of the
valuation $v_{E}$.

###### Example 4

To illustrate Proposition 3 and Corollary 1 in the context of our running
example, consider the rule $\rho_{4}:Alert(x,z)\leftarrow\neg
Fit(x)\otimes(Species(x,y)\wedge Fragile(y,z))$ in Example 1. It is easy to
see that the Four-normal form of $body(\rho_{4})$, hereafter denoted by
$\Phi$, is $(\neg Fit(x)\otimes Species(x,y))\wedge(\neg Fit(x)\otimes
Fragile(y,z))$.

It is clear that $\Phi$ has one $\vee$-component and one $\oplus$-component,
namely itself. Thus, $\rho_{4}$ is safe, and by Proposition 3, $\rho_{4}$ is
active domain preserving. As it is easy to see that all other rules in $R$ are
safe, Corollary 1 ensures that, whatever the database extension $E$,
$sem(\Delta)$ is finite. $\Box$

##  5 Database Updating

In our approach to updating we follow standard approaches Lau1998; Lau1997 in
which updating concerns only the database extension and does not modify the
rule set. We note that, to the best of our knowledge, our work is the first to
address the issue of database updating in the context of Four-value logic.
Previous work has addressed a different but related topic, namely knowledge
revision Arieli02.

In the next section, we introduce the notion of basic update, that is how to
change the database extension so as to assign a desired truth value to a given
fact of ${\cal HB}$. Then in the following section, we introduce the concept
of update policy as a means to specify and enforce update properties.

###  5.1 Basic Updates

Let us first recall that the database extension is a finite v-set (see
Definition 1) and that a v-set is a means to store a valuation of ${\cal HB}$.
We also recall that storing a valuation of ${\cal HB}$ in a database extension
$E$ is done under two assumptions, namely $(1)$ $E$ is ‘functional’, that is
for all $\langle\varphi_{1},{\tt v}_{1}\rangle$ and $\langle\varphi_{2},{\tt
v}_{2}\rangle$ in $E$, if $\varphi_{1}=\varphi_{2}$ then ${\tt v}_{1}={\tt
v}_{2}$, and $(2)$ the Open World Assumption, meaning that a fact $\varphi$ in
${\cal HB}$ is known (i.e., $v_{E}(\varphi)$ is different than ${\tt n}$) if
and only if $\langle\varphi,v_{E}(\varphi)\rangle$ is $E$. Both these
assumptions must also hold in the updated extension and therefore, they work
as constraints that must be satisfied by the updated database.

###### Definition 8

Let $\Delta=(E,R)$ be a database, $\varphi$ a fact in ${\cal HB}$ and ${\tt
v}$ a truth value in $\\{{\tt t},{\tt b},{\tt n},{\tt f}\\}$. The basic update
of $\Delta$ by $\varphi$ and ${\tt v}$ is defined to be the database
$\Delta^{\prime}=(E^{\prime},R)$ such that $v_{E^{\prime}}(\varphi)={\tt v}$,
and $v_{E^{\prime}}(\varphi^{\prime})=v_{E}(\varphi^{\prime})$, for every
$\varphi^{\prime}\neq\varphi$. $\Box$

Algorithm 1 Basic update

0: $\Delta=(E,R)$, a fact $\varphi$ and a truth value ${\tt v}$.

0: The updated database extension $E^{\prime}$ such that
$v_{E^{\prime}}(\varphi)={\tt v}$.

1: $current\\_v:=v_{E}(\varphi)$

2: if ${\tt v}=current\\_v$ then

3: $E^{\prime}:=E$

4: else if $current\\_v={\tt n}$ then

5: $E^{\prime}:=E\cup\\{\langle\varphi,{\tt v}\rangle\\}$

6: else if ${\tt v}={\tt n}$ then

7: $E^{\prime}:=E\setminus\\{\langle\varphi,current\\_v\rangle\\}$

8: else

9:
$E^{\prime}:=(E\setminus\\{\langle\varphi,current\\_v\rangle\\})\cup\\{\langle\varphi,{\tt
v}\rangle\\}$

10: return $E^{\prime}$

It is easily seen that for all $\Delta=(E,R)$, $\varphi$ and ${\tt v}$, the
database $\Delta^{\prime}$ always exists and it is unique. Algorithm 1
provides an effective way of computing $E^{\prime}$. Indeed:

  * •

If the test on line 2 succeeds then the update requires no change, which is
achieved by letting $E^{\prime}$ to be $E$.

  * •

Otherwise, we have ${\tt v}\neq current\\_v$, and if the test on line 4
succeeds, $E$ contains no pair involving $\varphi$. As in this case we have
${\tt v}\neq{\tt n}$, $\langle\varphi,{\tt v}\rangle$ is inserted in $E$ so as
to take the update into account while generating a proper v-set $E^{\prime}$.

  * •

If the test on line 4 fails but the test on line 6 succeeds, then we have
${\tt v}\neq current\\_v$, $current\\_v\neq{\tt n}$ and ${\tt v}={\tt n}$. In
this case, $\langle\varphi,current\\_v\rangle$ is deleted from $E$ so as to
take the update into account.

  * •

The last case is that on line 8, where ${\tt v}\neq current\\_v$,
$current\\_v\neq{\tt n}$ and ${\tt v}\neq{\tt n}$. In this case, the pair
$\langle\varphi,current\\_v\rangle$ in $E$ is changed to $\langle\varphi,{\tt
v}\rangle$ so as to take the update into account while generating a proper
v-set $E^{\prime}$.

###### Example 5

In the context of our running example, due to the disagreement of the sensors
measuring the humidity of bag $202$, assume that new measurements have been
conducted for this bag and that the sensors now output the following: $\langle
H_{1}(202),{\tt t}\rangle$, $\langle H_{2}(202),{\tt t}\rangle$, $\langle
W_{1}(202),{\tt t}\rangle$ and $\langle W_{2}(202),{\tt n}\rangle$.

Applying Algorithm 1 successively to each of these pairs, the database
$\Delta$ of Example 1 is modified as follows:
$-$ The pair $\langle H_{1}(202),{\tt t}\rangle$ is inserted.
$-$ The pair $\langle H_{2}(202),{\tt t}\rangle$ is left unchanged.
$-$ The pair $\langle W_{1}(202),{\tt f}\rangle$ is changed to $\langle
W_{1}(202),{\tt t}\rangle$.
$-$ The pair $\langle W_{2}(202),{\tt t}\rangle$ is deleted.

The resulting database extension $E^{\prime}$ is thus the following v-set:

$E^{\prime}=\\{$ | $\langle W_{1}(101),{\tt t}\rangle,\langle W_{1}(202),{\tt t}\rangle,\langle W_{1}(303),{\tt f}\rangle,$
---|---
|  $\langle H_{1}(101),{\tt f}\rangle,\langle H_{2}(101),{\tt
f}\rangle,\langle H_{1}(202),{\tt t}\rangle,\langle H_{2}(202),{\tt
t}\rangle$,
| $\langle Species(101,s_{1}),{\tt t}\rangle,\langle Species(202,s_{1}),{\tt
t}\rangle,\langle Species(303,s_{2}),{\tt t}\rangle,$
|  $\langle Fragile(s_{1},low),{\tt t}\rangle,\langle Fragile(s_{2},high),{\tt
t}\rangle\hfill\\}$ $\Box$

###  5.2 Update Policies

Although basic updates as defined earlier allow to perform any modification of
the database extension, it is common practice to specify an update policy in
order to enforce given properties on the update processing or on the resulting
database.

The most typical situation is when constraints must be satisfied by the
database, in which case it is required that updates preserve constraint
satisfaction. In other words, assuming that the database satisfies the
constraints before the update, it is required that the updated database also
satisfies the constraints. This is for example very common when dealing with
relational databases whose relations have to satisfy functional dependencies
such as key or foreign key constraints Ullman. In this case, one of two
policies is adopted regarding acceptance of the update:

  1. 1.

Policy 1: If the updated database does not satisfy the constraints then reject
the update. Roughly speaking, this policy gives priority to ‘old’ knowledge
over ‘new’ knowledge (i.e., it privileges the knowledge already stored in the
database).

  2. 2.

Policy 2: Always accept the update and restore constraint satisfaction
accordingly by performing auxiliary updates. Roughly speaking, this policy
gives priority to ‘new’ knowledge (as expressed by the update) over ‘old’
knowledge.

In our case, as mentioned earlier, the database must satisfy two constraints,
namely the functionality of the database extension and the Open World
Assumption. Both these constraints must hold in the updated database and their
satisfaction can be enforced by applying one of the two policies above. Below,
we describe the update algorithm for each policy, recalling that each
algorithm takes as input a database $\Delta=(E,R)$, a fact $\varphi$ and a
truth value ${\tt v}$, and aims at returning a database
$\Delta=(E^{\prime},R)$ such that $v_{E^{\prime}}(\varphi)={\tt v}$.

  1. 1.

Algorithm for Policy 1 (give priority to old knowledge over new knowledge):
if $v_{E}(\varphi)={\tt n}$ and ${\tt v}\neq{\tt n}$ then
$E^{\prime}:=E\cup\\{\langle\varphi,{\tt v}\rangle\\}$ else if
$v_{E}(\varphi)\neq{\tt n}$ and ${\tt v}={\tt n}$ then
$E^{\prime}:=E\setminus\\{\langle\varphi,v_{E}(\varphi)\rangle\\}$ else
$E^{\prime}:=E$ return $E^{\prime}$

  2. 2.

Algorithm for Policy 2 (give priority to new knowledge over old knowledge):
if $v_{E}(\varphi)={\tt v}$ then $E^{\prime}:=E$ else if $v_{E}(\varphi)={\tt
n}$ and ${\tt v}\neq{\tt n}$ then $E^{\prime}:=E\cup\\{\langle\varphi,{\tt
v}\rangle\\}$ else if $v_{E}(\varphi)\neq{\tt n}$ and ${\tt v}={\tt n}$ then
$E^{\prime}:=E\setminus\\{\langle\varphi,v_{E}(\varphi)\rangle\\}$ else
$E^{\prime}:=(E\setminus\\{\langle\varphi,v_{E}(\varphi)\rangle\\})\cup\\{\langle\varphi,{\tt
v}\rangle\\}$ return $E^{\prime}$

It should be noticed that each of the above two algorithms (Algorithm for
Policy 1 and Algorithm for Policy 2) processes two truth values, namely ${\tt
v}$ and $v_{E}(\varphi)$, and computes a third truth value, namely
$v_{E^{\prime}}(\varphi)$ based on which it computes $E^{\prime}$.

Therefore each of these algorithms computes the values of a binary operator
over $\\{{\tt t},{\tt b},{\tt n},{\tt f}\\}$. We can view this operator as
‘defining’ the corresponding policy and the truth table of the operator as
‘implementing’ the policy.

For example, let $\pi_{old}$ be the operator defining Policy 1 and let its
truth table be as shown in Figure 4. Then for a pair $({\tt
v},v_{E}(\varphi))$ such that ${\tt v}={\tt t}$ and $v_{E}(\varphi)={\tt f}$,
the value of $\pi_{old}({\tt t},{\tt f})$ (i.e., the value found at row ${\tt
t}$ and column ${\tt f}$ of the truth table of $\pi_{old}$) is ${\tt f}$. As a
consequence, according to Policy 1, if the update aims at assigning truth
value ${\tt t}$ to $\varphi$ and if the current truth value of $\varphi$ is
${\tt f}$ (i.e., $v_{E}(\varphi)={\tt f}$), then in the updated database, the
truth value of $\varphi$ is not changed (as stated by the last ‘else’
statement of Algorithm for Policy 1 above).

$\pi_{old}$ | t | b | n | f
---|---|---|---|---
t | t | b | t | f
b | t | b | b | f
n | n | n | n | n
f | t | b | f | f

$\pi_{new}$ | t | b | n | f
---|---|---|---|---
t | t | t | t | t
b | b | b | b | b
n | n | n | n | n
f | f | f | f | f

Figure 4: The truth tables of the operators $\pi_{old}$ and $\pi_{new}$

Similarly, let $\pi_{new}$ be the operator defining Policy 2 and let its truth
table be as shown in Figure 4. Then for the same pair as above, that is the
pair $({\tt v},v_{E}(\varphi))$ such that ${\tt v}={\tt t}$ and
$v_{E}(\varphi)={\tt f}$, the value of $\pi_{new}({\tt t},{\tt f})$ is t.
Hence, according to Policy 2, if the update aims at assigning the truth value
${\tt t}$ to $\varphi$ and if the current truth value of $\varphi$ is ${\tt
f}$ (i.e., $v_{E}(\varphi)={\tt f}$), then in the updated database, the truth
value of $\varphi$ is changed from ${\tt f}$ to ${\tt t}$ (as stated by the
last ‘else’ statement of Algorithm for Policy 2 above).

Now, an important remark is in order here regarding binary connectors
implementing update policies. Indeed, since the Four-valued logic has been
shown to be functionally complete Arieli1998, it turns out that any binary
operator over $\\{{\tt t},{\tt b},{\tt n},{\tt f}\\}$ can be defined by an
expression whose operations are the basic connectors of Four-valued logic.
Thus, any update policy defined through a binary connector can also be defined
using a well-formed formula of the Four-valued logic.

For example, the expression $\Phi_{new}(\phi_{1},\phi_{2})$ defining the
operator $\pi_{new}$ is simply $\Phi_{new}(\phi_{1},\phi_{2})=\phi_{1}$. This
expression shows that, according to $\pi_{new}$, all updates are processed as
specified by the user. As another example, the expression
$\Phi_{reject}(\phi_{1},\phi_{2})=\phi_{2}$ defines the (useless) update
policy whereby all updates are rejected. On the other hand, the expression
$\Phi_{old}(\phi_{1},\phi_{2})$ defining $\pi_{old}$ is more involved, since
it follows from Lau-2108-02587 that

$\Phi_{old}(\phi_{1},\phi_{2})=((\Phi_{\tt t}\vee\neg\Phi_{\tt
f})\otimes\sim\not\sim\Phi_{\tt n})\oplus\not\sim\Phi_{\tt b}$

where111The expressions involving the basic connectors for the unary
connectors T, B, N and F used here, can be found in Section 2

$\Phi_{\tt t}=({\bf T}\phi_{1}\wedge{\bf T}\phi_{2})\vee({\bf
T}\phi_{1}\wedge{\bf N}\phi_{2})\vee({\bf B}\phi_{1}\wedge{\bf T}\phi_{2})$

$\Phi_{\tt f}=({\bf T}\phi_{1}\wedge{\bf F}\phi_{2})\vee({\bf
B}\phi_{1}\wedge{\bf F}\phi_{2})\vee({\bf F}\phi_{1}\wedge{\bf
N}\phi_{2})\vee({\bf F}\phi_{1}\wedge{\bf F}\phi_{2})$

$\Phi_{\tt n}=({\bf N}\phi_{1}\wedge{\bf T}\phi_{2})\vee({\bf
N}\phi_{1}\wedge{\bf B}\phi_{2})\vee({\bf N}\phi_{1}\wedge{\bf
N}\phi_{2})\vee({\bf N}\phi_{1}\wedge{\bf F}\phi_{2})$

$\Phi_{\tt b}=({\bf T}\phi_{1}\wedge{\bf B}\phi_{2})\vee({\bf
B}\phi_{1}\wedge{\bf B}\phi_{2})\vee({\bf B}\phi_{1}\wedge{\bf
N}\phi_{2})\vee({\bf F}\phi_{1}\wedge{\bf B}\phi_{2})$.

The technical details on how to obtain the above formula are omitted since
they lie outside the scope of the present paper. Whatever the way the update
policy is defined, whether through a binary operator or through an expression,
the notion of update policy is formally defined as follows.

###### Definition 9

Let $\Delta=(E,R)$ be a database and let $\pi$ be a binary operator over
$\\{{\tt t},{\tt b},{\tt n},{\tt f}\\}$ called an update policy. Then given a
fact $\varphi$ of $\cal HB$ and truth value ${\tt v}$, the update of $\Delta$
by $\varphi$ and ${\tt v}$, using policy $\pi$, is defined to be the database
$\Delta^{\prime}=(E^{\prime},R)$ such that $v_{E^{\prime}}(\varphi)=\pi({\tt
v},v_{E}(\varphi))$ and
$v_{E^{\prime}}(\varphi^{\prime})=v_{E}(\varphi^{\prime})$, for every
$\varphi^{\prime}\neq\varphi$. $\Box$

Based on Definition 8 and Definition 9, it is easy to see that, given
$\Delta$, $\varphi$ and ${\tt v}$, the basic update of $\Delta$ by $\varphi$
and ${\tt v}$ yields the same result as the update of $\Delta$ by $\varphi$
and ${\tt v}$, using policy $\pi_{new}$. As a consequence, basic updates can
be seen as particular updates using a policy, namely those updates using
policy $\pi_{new}$.

We end this section by giving further examples of update policies that might
be relevant in practice.

$\pi_{1}$ | t | b | n | f
---|---|---|---|---
t | t | b | t | f
b | t | b | n | f
n | t | b | n | f
f | t | b | f | f

$\pi_{2}$ | t | b | n | f
---|---|---|---|---
t | t | t | t | t
b | t | b | n | b
n | t | n | n | n
f | t | b | n | f

Figure 5: The truth tables of the connectors defining update policies
$\pi_{1}$ and $\pi_{2}$

The first update policy we would like to introduce is that of data
integration. According to this policy, updates are performed so as the truth
value ${\tt v}$ specified in the update be combined with the existing one,
$v_{E}(\varphi)$, through the connector $\oplus$, whose truth table is shown
in Figure 1. This update policy is used when integrating data from various
sources.

The data integration policy can be ‘smoothed’ by preventing new
inconsistencies from being introduced in a source from data coming from other
sources (through updates). More precisely, given $\varphi$ and ${\tt v}$, the
update involving $\varphi$ and ${\tt v}$ is performed as follows:
$-$ If $v_{E}(\varphi)\oplus{\tt v}\neq{\tt b}$ then set the truth value of
$\varphi$ to $v_{E}(\varphi)\oplus{\tt v}$;
$-$ Otherwise reject the update.
The truth table of the associated connector $\pi_{1}$ is shown in Figure 5. It
should be noticed from this truth table that, for instance, when ${\tt v}={\tt
t}$ and $v_{E}(\varphi)={\tt f}$, $v_{E}(\varphi)\oplus{\tt v}={\tt b}$, thus
implying that $\pi_{1}({\tt t},{\tt f})={\tt f}$. On the other hand, for ${\tt
v}={\tt f}$ and $v_{E}(\varphi)={\tt n}$, $v_{E}(\varphi)\oplus{\tt v}={\tt
f}$, and $\pi_{1}({\tt f},{\tt n})={\tt f}$.

As a last example of update policy consider what we could call truth
increasing policy. This policy states that an update involving $\varphi$ and
${\tt v}$ is processed only if it results in an increase with respect to the
truth ordering of the truth value of $\varphi$. In other words:
$-$ If $v_{E}(\varphi)\preceq_{t}{\tt v}$ then set the truth value of
$\varphi$ to ${\tt v}$;
$-$ Otherwise reject the update.
The truth table of the associated operator $\pi_{2}$ is shown in Figure 5. We
notice from this truth table that, for instance, $\pi_{2}({\tt t},{\tt
b})={\tt t}$ because ${\tt b}\preceq_{t}{\tt t}$ holds, and that $\pi_{2}({\tt
f},{\tt n})={\tt n}$ because ${\tt n}\preceq_{t}{\tt f}$ does not hold.

It should be clear by now that many other update policies could be defined.
However, considering every possible binary truth table as an update policy is
unrealistic. In any case, the examples presented in this section show that our
approach allows to specify various update policies in a way which is simple,
easy to implement and powerful as it allows to specify complex update
policies.

We recall in this respect that the notion of update policy was first
introduced in BancilhonS81 in the context of updating views in relational
databases. This work was thus the earliest one that provided a theoretical
insight in the difficult problem of specifying and implementing sophisticated
database updates.

##  6 Related Work

Comparing our approach with all related work in the literature is simply
impossible due to the huge number of papers published during the past four or
five decades on the topics addressed here. In what follows we focus mainly on
related work in three areas: logic and databases, inconsistent databases, and
multi-valued logic.

###  6.1 Logic and Databases

We refer to CeriGT90; Ullman; MinkerSZ14 for surveys of standard approaches to
Datalog databases, and to Bidoit91 for a more detailed survey of the problem
of negation. We note that all these works use the Closed World Assumption (CWA
Reiter77), which leads to difficulties when dealing with false facts - a
problem that does not arise in our framework, as we use the Open World
Assumption (OWA).

Working under OWA is not new Bergman and the need to do so emerged in problems
of data integration on the web. Indeed, when a piece of information is not
retrieved in the answer to a query, one cannot assume that this piece of
information is false, but rather that it has not been searched properly.
Therefore it is more appropriate to consider that this piece of information is
unknown.

On the other hand, as the examples in this paper suggest, when integrating
information from several sources, contradictions may occur, and this motivates
the introduction of inconsistent as a truth value. This point of view has also
been considered in AmoP07 but in a logical framework that differs from ours.
Indeed, in AmoP07, the underlying four valued logic is not the one in Belnap,
although the considered implication looks similar to implication denoted here
by $\to_{1}$. Moreover, in AmoP07, the authors consider two negations in the
context of CWA and propose an alternating strategy for computing the database
semantics, inspired from well-founded semantics GelderRS91.

The approach in Arieli02 also considers two negations as done in AmoP07. As
already discussed in much detail, this approach is closely related to ours
when not using negation as failure - although the semantics is slightly
different. However, our approach is more expressive than Arieli02 and AmoP07,
since we allow rules not allowed in Arieli02 and AmoP07. Investigating how to
express negation as failure in our approach is a topic of future work.

As seen earlier, the work in Fitting90; Fitting91 is closely related to our
approach because the underlying logic in Fitting90; Fitting91 is that of
Belnap, and also because the syntax of the rules in Fitting90 is similar to
ours - although not strictly comparable to ours. We recall again that the
semantics of $k$-existential programs defined in Fitting90 differs from ours,
because the rules in Fitting90 are seen as equivalences, which is not the case
in our approach.

In Grahne; Grahne-19, related work following similar semantics can be found in
the context of relational databases. In that work, reasoning with four truth
values is modeled in two distinct ways: one for deducing true information and
one for deducing false information, while inconsistency is considered as
information obtained by the ‘intersection’ of these two ways of reasoning.

The problem of updating deductive databases was first addressed in Reiter92.
Our work in Lau1998 was among the first to suggest storing false facts and
giving priority to most recent updates. The present work builds upon these
basic ideas in a much wider context, while the introduction of update policy
stems from the work in BancilhonS81. Moreover, and to the best of our
knowledge, this work is the first one to address the issue of updates in the
framework of Four-valued logic.

###  6.2 Inconsistent Databases

In this paper, in contrast to previous work on inconsistent databases, we
propose a radically different approach. Indeed, the goal of previous work
dealing with inconsistencies, is either to define and study ‘repairs’ so as to
make the database consistent (Afrati; Gianluigi), and/or to identify queries
whose answers are independent from any contradiction (Greco). Instead, we
propose an approach in which inconsistent information can be stored or deduced
through rules, and our goal is not to eliminate or avoid contradictions.

Our semantics allows for handling inconsistent information as such, thus
reflecting what happens in real world applications in which true, false,
inconsistent and unknown information have to be dealt with. This is
particularly true in data integration environments. In our work, we follow the
position in Gabbay, in that inconsistent information should not be avoided,
but treated as such by taking appropriate actions when necessary. The issue of
taking actions lies beyond the scope of this paper, because our rules cannot
express an information such as ‘If $\varphi$ is inconsistent then $\phi$’.
Indeed in our formalism such a rule would be expressed as $\phi\leftarrow{\bf
B}\varphi$, which is not allowed. We are currently studying this topic.

The approach in LoyerSS04 addresses the issue of data inconsistency due to
data integration according to a specific scenario: a central server collects
facts from autonomous sources and then tries to combine them using the syntax
and semantics of Fitting90; Fitting91, on the one hand, and a set of
hypotheses $H$, representing the server’s own estimates, on the other hand. In
this setting, the authors show how to compute what they call the support of
$H$, defined as the maximal part of $H$ that does not contradict the facts in
the database semantics. This notion of support is then shown to provide
hypothesis-based semantics for the class of programs defined in Fitting91; and
in the case of Datalogneg programs, these semantics have been shown to extend
well-founded semantics of GelderRS91 and Kripke Kleen semantics of Fitting85a.

###  6.3 Multi-valued Logic

The Four-valued logic that we consider in this work has been introduced in
Belnap and has since motivated several works in non standard logic. Again, our
aim here is not to review all these works, and we refer to OmoriW17 for a
survey of this topic. Here, we focus on works most closely related to ours. In
Arieli1998 the issue of the functional completeness has been addressed among
others and their results have inspired our concern on this issue. On the other
hand, the bi-lattice structure of this logic has been widely studied in
Fitting90; Fitting91, where the concept of logic programs in this framework
was first introduced. Rule semantics in Four-valued logic has been
investigated in Fitting90; Fitting91 and in Arieli02. As seen in sub-Section
3.3, these two approaches are related to ours although not always comparable.
We notice here that our approach offers a generic framework for expressing
rules in Four-valued context: as shown in Example 3, it happens that rules in
our approach might not be expressible in the approach of Fitting90; Fitting91
or in the approach of Arieli02. Moreover the notion of database model, as
considered in this work, has been investigated in Arieli02, but not in
Fitting90; Fitting91. As a final remark, we note that the work in Tsoukias
established a strong relationship between Four-valued logic and rough set
theory.

##  7 Concluding remarks

In this paper we have introduced a novel approach to deductive databases
dealing with contradictory information. We stress again that our work is
motivated by the facts that $(i)$ many contradictions occur in the real world
and these contradictions must be dealt with as such, and $(ii)$ data
integration is a field where such contradictions are common. To cope with
these issues we proposed a deductive database approach based on the Four-
valued logic initially introduced in Belnap. We have studied the strong
relationship between our approach and those in Fitting90; Fitting91 and
Arieli02. One of our main contributions is to have shown that database
semantics can be seen as the unique $k$-minimal and $k$-increasing database
model, and that this holds for three implications proposed so far in the
literature. Two other important contributions of our work are $(i)$ to
characterize safe rules, ensuring that the database semantics is finite, and
$(ii)$ to propose a new kind of update allowing to ‘combine’ the new truth
value of a fact with its current truth value in the database. As shown in
Section 5, this new way of updating is of particular interest when it comes to
enforcing updates satisfying properties of various kinds.

Based on these results, we are currently investigating the following issues.
First, as rules can contradict each other (something that happens frequently
in real life), it is important to characterize the exact situations when these
contradictions occur, so as to take appropriate actions, as suggested in
Gabbay. We approach this important issue by extending the form of the rules to
allow in their body additional connectors (such as connector ${\bf B}$
introduced in Tsoukias and recalled in Section 2). Another extension of our
work is to investigate negation as failure in our context, inspired by the
work in Arieli02; AmoP07. Last but not least, we conjecture that the Four-
valued framework provides the right context for defining new measures related
to data quality, a research topic that we also plan to investigate in the
future.

## Declarations

Author contributions: The two authors contributed to the study, conception and
design. Both read and approved the submitted manuscript.

Funding: No funds, grants, or other support was received for conducting this
study.

Financial interests: The authors declare they have no financial interests.

Non-financial interests: The authors declare they have no non-financial
interests.

Data availability: Data sharing is not applicable to this article as no data
sets were generated or analyzed during the current study.