Jacques Chabin

Mirian Halfeld Ferrari

Nicolas Hiot

Dominique Laurent

Incremental Consistent Updating of Incomplete Databases (Extended Version -Technical Report)

Efficient consistency maintenance of incomplete and dynamic real-life databases is a quality label for further data analysis. In prior work, we tackled the generic problem of database updating in the presence of tuple generating constraints from a theoretical viewpoint. The current paper considers the usability of our approach by (a) introducing incremental update routines (instead of the previous from-scratch versions) and (b) removing the restriction that limits the contents of the database to fit in the main memory. In doing so, this paper offers new algorithms, proposes queries and data models inviting discussions on the representation of incompleteness on databases. We also propose implementations under a graph database model and the traditional relational database model. Our experiments show that computation times are similar globally but point to discrepancies in some steps.

Introduction

Incremental update algorithms are essential for incomplete real-life databases, often large and constantly updated. Modern applications usually involve the analysis of large amounts of data with missing and changing values. The quality of this analysis depends on the consistency of the data, the maintenance of which requires calculations whose cost needs to be reduced.

To address this problem, we build upon our prior work [START_REF] Chabin | Consistent updating of databases with marked nulls[END_REF] where the generic problem of database updating in the presence of constraints was tackled from a theoretical point of view, and under the restriction that the database content was meant to fit in main memory. Hence, for missing values, we follow Reiter [START_REF] Reiter | A sound and sometimes complete query evaluation algorithm for relational databases with null values[END_REF] who provides FOL (First-Order Logic) semantics to null values of type 'value exists but is currently unknown'. Constraints are expressed as tuple-generating dependencies (tgd), i.e., implications of the form (∀X, Y )(B(X, Y ) ⇒ (∃Z)L(X, Z)) where X, Y , Z are vectors of variables, B(X, Y ) is the conjunction of atoms of the form L i (X i , Y i ) where X i and Y i are sub-vectors of X and Y , respectively, and L(X, Z) is an atom.

In [START_REF] Chabin | Consistent updating of databases with marked nulls[END_REF], our purpose was to allow for the insertions or the deletions of sets of tuples under the following hypotheses:

• A fixed set C of constraints as specified just above is assumed over a given set of predicates.

• The database D to be updated is a set of instantiated atoms, in which marked nulls may occur.

Moreover, the database contains no redundancies caused by these nulls.

• D satisfies the constraints in C, meaning that, for every c in C, whenever there exists an instantiation h of X and Y such that D contains all atoms in h(B(X, Y )) then h can be extended to Z so as D also contains h(L(X, Z)).

• The updated database D ′ satisfies the constraints in C and is not redundant, while being such that the updates are performed, that is, all atoms to be inserted are present in D ′ and no atoms to be deleted is present in D ′ .

In this paper, we improve our work in [START_REF] Chabin | Consistent updating of databases with marked nulls[END_REF] in two main aspects: [START_REF] Abiteboul | Mise-à-jour des bases de données contenant de l'information incomplète[END_REF] we propose an incremental version of the approach and (2) we deal with data stored in database systems, contrary to the in-memory version of [START_REF] Chabin | Consistent updating of databases with marked nulls[END_REF].

Given an update u over a database instance D, our approach consists in generating (by the activation of constraints in C) a set of new updates, U ′ , as necessary side-effects to maintain the database consistent. Contrary to from scratch algorithms, whereby the whole database instance and the whole set C are involved in the generation of U ′ , incremental algorithms minimize the amount of data to be accessed and the constraints to be triggered.

Paper Organisation. We overview our approach and its evolution (from scratch towards an incremental approach) through a motivating example in Section 2. Section 3 provides some background. Section 4 introduces the operations over which the incremental core computation is built. Incremental update algorithms, their implementation aspects and experimental results are introduced, respectively in Sections 5, 6 and 7. After presenting related work in Section 8, Section 9 concludes the paper.

Motivating Example

Figure 1 shows a set of constraints in the context of a university, researchers and students. Although the intuitive meaning of these constraints should be clear, we point out that in the constraints c 6 , c 9 , c 10 , c 11 and c 12 , the right hand-side involves a variable not present in the left hand-side. Due to such contraints, known in the literature as tuple generating dependencies (tgd), nulls values may appear in the database instance, as explained below. Their intuitive meaning is as follows:

• the variable Z in P hDP aper(Y, P, Z) of c 6 stands for the year the paper has been published;

• the variable Y in Cites(X, Y ) of c 9 stands for a publication cited by publication X;

• the variable Y in Enrolled(X, Y ) of c 10 stands for a course student X is enrolled in;

• the variable Z in Degree(Y, Z) of c 11 stands for the degree course Y is part of;

• the variable Z in Language(X, Y, Z) of c 12 stands for the language in which is taught course X of degree Y . However, c 3 is not satisfied because Authors(Sten, P 269 ) is in D and Researcher(Sten) is not. Similarly, c 5 is not satisfied because Researcher(N ils) has no matching fact over Authors in D. Constraint satisfaction is obtained by adding facts, generated by a process called chase:

1. Researcher(Sten) is added to satisfy c 3 .

2. In order to satisfy c 5 one fact over Authors must be added, but the value of the second argument (i.e., the publication) is unknown. Despite that publications are present in D, those authored by N ils are unknown. Marked nulls are used to account for this situation: Authors(N ils, N 1 ) is added, which is read as 'N ils authored a publication, currently unknown but recognized as N 1 '. The atom P ublication(N 1 ) is then inserted in order to satisfy c 4 .

In this case, we obtain D ′ = D ∪ {Researcher(Sten), Authors(N ils, N 1 ), P ublication(N 1 ))}.

In the following items, we show differences between the from-scratch and incremental approaches to updates. From-scratch approach. To reinforce constraints, side-effects are computed through a process called chase, that applies the constraints in C 1 on D 1 ∪ iRequest, to generate a new set chase(D 1 ). In doing so, facts already in D 1 might be generated again.

Incremental approach. Side-effects for insertions are computed based on iRequest as follows. In our example, the only constraint to be triggered when inserting Authors(Sten, P 269 ) is c 6 because (i) a query on D 1 informs that the atoms Supervises(Elin, Sten) and Authors(Elin, P 269 ) already exist in D 1 , and (ii) c 6 is impacted by the insertion. Then, the result of the insertion is D ′ 1 = D 1 ∪ {Authors(Sten, P 269 ), P hDP aper(Sten, P 269 , N 2 )}.

(B.2) Deletions. Consider D ′ (from item (A) above) along with the constraints in C = {c 1 , . . . , c 6 }. From-scratch approach. After removing from D ′ a given set of facts dRequest, the deletion process includes the computation of chase(D ′ \ dRequest) to check constraint satisfaction. Then, if one atom to be deleted is re-generated (up to null renaming), a backward chase is activated to identify the side-effects of the deletion. This is illustrated through the following two cases. Case 2. Consider now dRequest = {P hDP aper(Sten, P 269 , N 2 )} on D ′′ . A processing similar to the previous one would first remove the atom from D ′′ and then, insert P hDP aper(Sten, P 269 , N 3 ) to restore consistency with respect to the constraints. This result is not acceptable because the generated set is equal to D ′′ (up to a null renaming), meaning that the deletion has not been implemented. In this case, the processing is carried on by deleting all atoms responsible of the generation of the atom to be deleted.

This amounts to apply the constraints backward (from the head to the body), removing one atom from the body, to prevent the constraint from being triggered. To this end, for every constraint c, a literal in its body is marked as the one to be deleted in such a situation (for the sake of simplicity, let the leftmost literal in be the marked one). Here, Authors(Elin, P 269 ) has to be deleted, due to c 6 . Then, we proceed following the ideas already presented: the latter deletion, because of c 5 , requires the insertion of Authors(Elin, N 4 ) which in turn, because of c 4 , requires the insertion P ublication(N 4 ), returning the database D 2 = (D ′′ \ {P hDP aper(Sten, P 269 , N 2 ), Authors(Elin, P 269 )}) ∪ {Authors(Elin, N 4 ), P ublication(N 4 )}.

Incremental approach. First, a backward chase is used to find the constraints impacted by the required update. In our example, constraint c 6 , and then c 5 are the only ones concerned by deletions. Second, the chase is applied only on the rules detected just above and its result is analyzed as done in the from-scratch approach. It is worth noting that, as data is stored in a database, queries are used to detect whether constraints can be applied for chasing (backward or forward).

(C) Avoiding too many nulls. An important issue regarding side effects is making sure that the processing terminates. Considering the set of constraints C 1 = C ∪ {c 7 , c 8 , c 9 } on D ′ , it is clear that D ′′ does not satisfy c 9 , because P ublication(P 269 ) and P ublication(P 235 ) belong to D ′′ with no associated citation. In order to satisfy c 9 , Cites(P 269 , N 6 ) and Cites(P 235 , N 7 ) must be inserted, which triggers the insertions of P ublication(N 6 ) and of P ublication(N 7 ), due to c 7 . Then, to satisfy c 9 , Cites(N 6 , N 8 ) and Cites(N 7 , N 9 ) have to be inserted, and we are clearly entering an infinite loop, which is not acceptable.

To cope with this difficulty, every null N is associated with an integer called the degree of N and denoted by δ(N ). At each insertion, the degree of all nulls occurring in D are set to 0, and when a constraint c is applied during the processing, all generated nulls are assigned a degree equal to δ + 1 where δ is the maximal degree of the nulls in the atoms of the constraint body, or 0 if no null occurs in the constraint body. Moreover, assuming a fixed maximal null degree δ max , insertion processing is stopped as soon as a null N is such that δ(N ) ≥ δ max , and the insertion is rejected, that is D is not changed.

For example, in the case just above, we have δ(N 6 ) = δ(N 7 ) = 0, δ(N 8 ) = δ(N 6 ) + 1 = 1 and δ(N 9 ) = δ(N 7 ) + 1 = 1, etc. If, for example δ max is set to 2, the generation of nulls will stop at the next round and the insertion will be rejected. The verification of null degree is similar in both From-scratch and incremental approaches (it was proven in [START_REF] Chabin | Consistent updating of databases with marked nulls[END_REF] that by using δ max we accept only consistent insertions).

(D) Avoiding redundancies (core). Side effects have to be computed in a minimal way to reflect as much as possible the so-called minimal change requirement. To illustrate this point consider the insertion in D ′ of Authors(N ils, P 235 ). Adding this fact in D ′ provokes redundancies, because the presence of Authors(N ils, N 1 ) and of P ublication(N 1 ) is no longer required to ensure constraint satisfaction. The result of this insertion is the set D ′′′ defined by: D ′′′ = (D ′ \ {Authors(N ils, N 1 ), P ublication(N 1 )}) ∪ {Authors(N ils, P 235 )} In our implementations, redundancies in D are eliminated through the computation of the core, seeking for mapping nulls to constants or nulls so as to detect redundant atoms. In our example, for h such that h(N 1 ) = P 235 , we have: h(Authors(N ils, N 1 )) = Authors(N ils, P 235 ) and h(P ublication(N 1 )) = P ublication(P 235 ), showing that Authors(N ils, N 1 ) and P ublication(N 1 ) are redundant. From-scratch approach. Once the updates are performed on the database, the whole instance is considered for simplifications. Incremental approach. This new proposal aims to retrieve only the facts involved in the update operation. For instance, for D ′ as in our example, in the incremental approach a query detects that N 1 is the only null value concerned by the update. No need to work with the whole instance D ′ .

From-scratch and incremental approaches at a glance. Consider the update process that includes the general ideas explained in items (B) and (C) above. Denote, respectively, by upd and upd |U , its from-scratch and incremental versions. More precisely, when using the upd |U policy, only the database portion impacted by U is concerned, while the whole database is concerned by upd policy. The expression D♦U indicates the insertion/deletion of the required updates U in/from D.

In the from-scratch approach the new instance is denoted by D ′ = core(upd(D♦U )), while in the incremental approach, the new instance is denoted by D ′ = core |N ullBucket (upd |U (D♦U )), where NullBucket, is the set of nulls impacted by the update policy (upd |U ) applied to D♦U .

Preliminaries

We recall some formal definitions already used in [START_REF] Chabin | Consistent updating of databases with marked nulls[END_REF]. We assume a standard FOL alphabet composed of three pairwise disjoint sets, namely: const, a set of constants, var, a set of variables and pred, a set of predicates, every predicate being associated with a positive integer called its arity. In this setting, a term is a constant or a variable and an atomic formula, or an atom, is a formula of the form P (t 1 , . . . , t n ) where P is a predicate of arity n and t 1 , . . . , t n are terms. Every atom in which no variables occur is called a fact.

A homomorphism from a set of atoms A 1 to a set of atoms A 2 is a mapping h from the terms of A 1 to the terms of A 2 such that: (i) if t ∈ const, then h(t) = t, and (ii) if P (t 1 , ..., t n ) is in A 1 , then P (h(t 1 ), ..., h(t n )) is in A 2 . The set A 1 is isomorphic to the set A 2 if there exists a homomorphism h 1 from A 1 to A 2 which admits an inverse homomorphism (from A 2 to A 1 ).

We denote by Φ the set of all formulas of the form (∃X)(ϕ 1 (X 1 ) ∧ . . . ∧ ϕ n (X n )) where X is a vector of variables made of all variables occurring in X i (i = 1, . . . , n), and where for every i = 1, . . . , n, ϕ i (X i ) is an atomic formula in which the free variables are those in X i . If φ denotes such a formula in Φ, the set {ϕ 1 (X 1 ), . . . , ϕ n (X n )} is denoted by atoms(φ).

Given φ in Φ, a model M of φ is a set of facts such that there exists a homomorphism from atoms(φ) to M . In such a setting, for all φ 1 and φ 2 in Φ, φ 1 ⇒ φ 2 holds if each model of φ 1 is a model of φ 2 , and as usual, φ 1 and φ 2 in Φ are said to be equivalent, denoted by φ 1 ⇔ φ 2 , if φ 1 ⇒ φ 2 and φ 2 ⇒ φ 1 both hold, that is if φ 1 and φ 2 have the same models.

For all φ 1 and φ 2 in Φ, φ 1 is said to be simpler than φ 2 , denoted by φ 1 φ 2 , if (i) φ 1 ⇔ φ 2 holds, and (ii) atoms(φ 1 ) ⊆ atoms(φ 2 ). φ 1 is also said to be a simplification of φ 2 . A simplification φ 1 of φ 2 is said to be minimal if φ 1 φ 2 and there is no φ ′ 1 such that φ ′ 1 ≺ φ 1 . For instance, let φ be the formula (∃x, y)(P (a, x) ∧ P (a, y)); then (∃x)(P (a, x)) and (∃y)(P (a, y)) are two distinct but equivalent simplifications of φ.

It is shown in [START_REF] Chabin | Consistent updating of databases with marked nulls[END_REF] that if φ is in Φ and φ 1 and φ 2 two minimal simplifications of φ, then atoms(φ 1 ) and atoms(φ 2 ) are isomorphic (in the literature, we find a similar result for graphs [START_REF] Hell | The core of a graph[END_REF]). Minimal simplifications are also called cores and the core of a given formula φ is denoted by core(φ).

Basically, a database instance is a formula φ in Φ that cannot be simplified, i.e., such that core(φ) = φ. Formulas in Φ are 'skolemized' by replacing the variables with specific constants referred to as Skolem constants or as (marked) nulls and by omitting the existential quantifier. We thus assume an additional set of symbols in our alphabet, denoted by null, disjoint from the sets const and var. Now a term can be of one of the following types: either a constant, or a null, or a variable. Any atom of the form P (t 1 , . . . , t n ) where for every i = 1, . . . , n, t i is in const ∪ null, is called an instantiated atom. Given an instantiated atom A, denote by null(A) the set of nulls appearing in A. Moreover, as usual, the transformed conjunctive formula is written as the set of its conjuncts. In other words, a database instance is a set of instantiated atoms that can be written as atoms(Sk(φ)) where Sk(φ) is the Skolem version of a formula φ in Φ such that core(φ) = φ.

Simplification with Respect to Nulls: a Basic Operation

In our approach, a database D is expected to be equal to its core to avoid data redundancy. It is thus of paramount importance to enforce this property when updating. To this end, we propose incremental algorithms, so as to deal with as few nulls as possible, based on those involved in the update processing.

More formally, given a set of atoms I and a set of nulls ν occurring in I, we look for a homomorphism h such that for every N not in ν, h(N ) = N and h(I) is minimal so as h(I) ⊆ I. However, the following example shows that the choice of ν cannot be arbitrary. Indeed, given a set of nulls ν 0 , with respect to which I is to be simplified, the set ν 0 has to be expanded to the set ν of all nulls 'linked' (directly or indirectly) to a null in ν 0 in some atom of I.

Example 1 Let ν 0 = {N 1 } and I defined by: I = { Student(Alice), Enrolled(Alice, N 1 ), Degree(N 1 , N 2 ), Enrolled(Alice, M ath), Degree(M ath, N 3 ), Degree(CS, N 4 ), Degree(CS, BSc) } To simplify I with respect to ν 0 , we should eliminate redundancies in I involving N 1 . As N 1 occurs in Degree(N 1 , N 2 ) with the other null N 2 , the simplification should deal with N 1 and N 2 . Since N 1 and N 2 are not linked with any other null in the atoms of I, we have ν = {N 1 , N 2 }. For h such that h 1 (N 1 ) = M ath and h 1 (N 2 ) = N 3 , we obtain a non-redundant instance I ′ = h(I) defined by I ′ = { Student(Alice), Enrolled(Alice, M ath), Degree(M ath, N 3 ), Degree(CS, N 4 ), Degree(CS, BSc) }.

Notice however that simplifications involving N 3 or N 4 have not to be considered.

As shown by the above example, given I and ν 0 , nulls 'linked' in I to nulls in ν 0 have to identified. We do so through the computation for every N in ν 0 , of the set LinkedNull I,N as explained next.

We first define the sequence LinkedNull k I,N k≥0 by:

(i) LinkedNull 0 I,N = {A i ∈ I | N ∈ null(A i )} (ii) LinkedNull k I,N = {A i ∈ I | (∃A j ∈ LinkedNull k-1 I,N )(null(A i ) ∩ null(A j ) = ∅)}.
It is easy to see that for every k ≥ 0, we have LinkedNull k I,N ⊆ LinkedNull k+1 I,N and LinkedNull k I,N ⊆ I. Thus, the sequence LinkedNull k I,N k≥0 is bounded by I and is monotonic. As I is finite, the sequence has a unique limit, which is precisely the sub-set of I denoted by LinkedNull I,N .

It therefore turns out that redundancy has only to be checked with respect to the atoms in N ∈ν0 LinkedNull I,N and the set ν of all nulls occurring in this set. Algorithm 1 shows how redundancies are dealt with in this context.

Algorithm 1: Simplif y(I, ν 0 )

1: P Set := {LinkedNull I,N | N ∈ ν 0 } 2: for all P ∈ P Set do 3:
Build the query q core and compute its answer q core (I)

4: if | (q core (I)) |> 1 then 5:
h m := ChooseMostSpec(q core (I))

6:

I := (I \ P ) ∪ h m (P ) 7: return I Algorithm 1 receives as input a set I of instantiated atoms, and a set of nulls ν 0 . For each N in ν 0 , the algorithm computes the set LinkedNull I,N (line 1), which is stored in a set called P Set. Therefore, the nulls occurring in P Set constitute the set ν with respect to which I is simplified.

On line 3, for each P in P Set, a query q core : ans(X) ← A 1 (X 1 ), . . . , A n (X n ) is built by replacing each occurrence of N i in P by x i . That is, A i (X i ) is obtained from A i in P by replacing the nulls in A i by the corresponding variables.

Thus, assuming that p nulls occur in P , when evaluating the answer q core (I) of q core , the tuple (N 1 , . . . , N p ) is obviously returned. However, it may happen that the answer contains other tuples, each of which define a possible instantiation of the nulls in P . In this case, some atoms in P are redundant, and thus can be removed. To implement these remarks, when the evaluation of q core over I returns more than one tuple (line 4), one most specific tuple is chosen (line 5), and denoting by h m the associated homomorphism, I is simplified (line 6) by replacing all atoms A in P by h m (A).

Example 2 Considering I as in Example 1 and ν 0 = {N 1 }, LinkedNull I,N1 consists of the atoms Enrolled(Alice, N 1 ) and Degree(N 1 , N 2 ). Thus, the query q core is defined by: ans(x 1 , x 2 ) ← Enrolled(Alice, x 1 ), Degree(x 1 , x 2 ) returning the answer {(N 1 , N 2 ), (M ath, N 3 )} with more than one tuple. Hence, h m such that h m (N 1 ) = M ath and h m (N 2 ) = N 3 is returned line 5, and I is simplified as illustrated in Example 1.

To explain our method for computing the most specific homomorphism h m we introduce the notion of P -homomorphism.

Definition 1 Given I a set of instantiated atoms and N a null occurring in I, let P = LinkedNull I,N . A P -homomorphism is a homomorphism h such that h(I) ⊆ I and for every null

N ′ in null(I) \ null(P ), h(N ′ ) = N ′ .
I is said to be P -reducible if there exists a P -homomorphism h such that h(I) is a strict subset of I.

In the following proposition, given a set I of instantiated atoms and a null N in ν 0 , we use the following notation:

• P denotes the set of atoms LinkedNull I,N , and null(P ) = {N 1 , . . . N p } denotes the set of nulls occurring in P ;

• q core (I) is the answer to q core computed against I. That is, q core (I) is the set {h 1 , . . . , h q } of all possible P -homomorphisms defined over null(P ). We suppose that h 1 is the identity, i.e., for every j = 1, . . . , p, h 1 (N j ) = N j ;

• H P denotes the table with p columns and q rows such that

H P [i, j] = h i (N j ).
• Given a set of atoms Q, we denote by cons null(Q) the set of all symbols σ such that σ is a constant or a null not in null(Q).

We recall that given two homomorphisms h 1 and h 2 over the same set of symbols Σ, h 1 is said to be less specific than h 2 , denoted by h 1 h 2 , if there exists a homomorphism h over Σ such that h • h 1 = h 2 . Using these notation, the following proposition holds.

Proposition 1 Given h i and h i ′ in q core (I), h i h i ′ holds if and only if, for every j = 1, . . . , p, we have:

1. If H P [i, j] is in cons null(P ), then H P [i, j] = H P [i ′ , j]; 2. If H P [i, j] is a null N in null(P ), then for every j ′ = j such that H P [i, j] = H P [i, j ′ ] it holds that H P [i ′ , j] = H P [i ′ , j ′ ].
Proof. Let us first assume that h i h i ′ holds. In this case, there exists h such that h

• h i = h i ′ . If N j is such that h i (N j
) is a constant or a null not in null(P ), then for every P -homomorphism h P ,

h P (h i (N j )) = h i (N j ). Hence, h i ′ (N j ) = h • h i (N j ) = h i (N j ), which shows item (1). If j and j ′ are such that h i (N j ) = h i (N j ′ ), then h i ′ (N j ) = h i ′ (N j ′ ) also holds, showing item (2).
Conversely, assume that for h i and h i ′ , items (1) and ( 2) hold. Let h be defined for every j = 1, . . . , p as follows: if there exists

N k such that h i (N k ) = N j then h(N j ) = h i ′ (N k ), otherwise h(N j ) = N j . We first notice that h is well defined. Indeed, if k and k ′ are such that h i (N k ) = h i (N k ′ ), then we have two expressions defining h(N j ), namely h(N j ) = h i ′ (N k ) and h(N j ) = h i ′ (N k ′ ). However, by item (2) we have h i ′ (N k ) = h i ′ (N k ′ ),
and thus, these two expressions yield the same value. We now prove that h i h i ′ , that is, that for every k = 1, . . . , p, then

h i ′ (N k ) = h(h i (N k )). If h i (N k ) is not in null(P ), then, we have h i (N k ) = h i ′ (N k ) = N k ,

and by construction of h we also have h(N

K ) = N k . Therefore h i ′ (N k ) = h(h i (N k )) = N k . On the other hand, if h i (N k ) = N j , by definition of h, we have h i ′ (N k ) = h(N j ). Hence, h i ′ (N k ) = h(N j ) = h(h i (N k )). Since for every k = 1, . . . , p, we have h i ′ (N k ) = h(N j ) = h(h i (N k )), it follows that h i h i ′
, and the proof is complete.

Example 3 Let I = {B(N 1 , N 2 ), B(N 2 , N 1 ), C(N 1 , a), C(N 2 , a), C(N 3 , a)} and ν 0 = {N 1 }.
In this case,

P = {{B(N 1 , N 2 ), B(N 2 , N 1 ), C(N 1 , a), C(N 2 , a
)}} and thus null(P ) = {N 1 , N 2 } and cons null(P ) = {a, N 3 }. This implies that P -homomorphisms should not change N 3 , or in other words, N 3 should be treated as constant. The query q core is thus written as follows:

q core : ans(x 1 , x 2 ) ← B(x 1 , x 2 ), B(x 2 , x 1 ), C(x 1 , a), C(x 2 , a)
and the table H P representing the answer q core (I) is shown below.

H P x 1 x 2 1 N 1 N 2 2 N 2 N 1
H P has 2 columns (because null(P ) contains two nulls), and 2 rows due to two answers in q core (I).

It is easy to see that h 1 h 2 , and h 2 h 1 meaning that there is no advantage in trying to simplify the database instance in this case. Indeed, we have h 1 (I) = I, where h 1 is the identity. We have h 2 (I) = I as well, although h 2 is not the identity. Remark that h 2 does not satisfy

h 2 = h 2 • h 2 (i.e., h 2 is not idempotent) because h 2 (h 2 (N 1 )) = h 2 (N 2 ) = N 1 , whereas h 2 (N 1 ) = N 2 .
As will be seen shortly, detecting such homomorphisms allows for computational optimizations.

The following corollary shows how to find one most specific homomorphism, based on Proposition 1.

To state the corollary, we use the following notation for i = 1, . . . , q:

• γ i is the number of nulls N in null(P ) such that h i (N ) is in cons null(P );

• µ i = {k ∈ {1, . . . , q} | (∀j = 1, . . . , p)(h i (N j ) ∈ cons null(P ) ⇒ h k (N j ) = h i (N j ))};
• π i is the number of distinct nulls in null(P ) in the set h i (null(P )).

Intuitively speaking, considering that H P is the tableau, then γ i is the number of columns that, at row i, contain a symbol in cons null(P ). On the other hand, µ i is the set of all rows in H P containing the same symbols of cons null(P ) in the same columns as row i does (i.e., if

h i (N j ) = c then h k (N j ) = c).
Then π i is the number of distinct nulls in nulls(P ) occurring in row i.

The corollary below formalizes the following informal remarks:

1. If h i = h i • h i , then h i cannot be one of the most specific homomorphisms, because in this case,

h i ≺ h i • h i . For instance, in Example 3, we have h 2 = h 2 • h 2 .
2. Most specific homomorphisms are among the rows of H P with the largest number of symbols in cons null(P ). Indeed, let h i and h j be such that row i contains strictly more symbols in cons null(P ) than row j and h i ≺ h j . Then, there exists h such that h • h i = h j , and so, if N in null(P ) is such that h i (N ) is in cons null(P ), we have h(h i (N )) = h i (N ), and so h i (N ) = h j (N ). Thus, row j has at least as many symbols in cons null(P ) as row i, which implies a contradiction. Hence, for every N in null(P ), h i (N ) is also in null(P ), in which case rows i and j have no symbols in cons null(P ), which is another contradiction.

3. Considering one of the rows defined just above, say row i, among all rows having the same symbols in cons null(P ) in the same columns as row i, we argue that a row with as few distinct nulls in null(P ) defines one most specific homomorphism.

Corollary 1 Given I and P as above, denoting by {h 1 , . . . , h q } the set q core (I), the following holds:

1. If h i is one of the most specific P -homomorphisms in q core (I) then h i is idempotent, that is,

h i • h i = h i .
2. h i is one of the most specific P -homomorphisms in q core (I) if (a) γ i = max 1≤j≤q (γ j ), and (b)

π i = min k∈µi (π k ).
Proof. First, Proposition 1 implies that h i h i • h i holds for every h i . Moreover, as h i is a P -homomorphism, we have h i (I) ⊆ I. Thus h i • h i (I) ⊆ I, which implies that h i • h i is a Phomomorphism as well. The proof of item ( 1) is therefore complete.

Assume that h i satisfies (2) and let h k be a P -homomorphism such that h i h k . By Proposition 1, if h i (N j ) is in cons null(P ), then h i (N j ) = h k (N j ). Therefore, γ i ≤ γ k , and as γ k ≤ γ i , this implies γ i = γ k . Thus, k is in µ i , which implies that h i (N j ) is in null(P ) if and only if so is h k (N j ). By Proposition 1, if j and j ′ are such that h i (N j ) = h i (N j ′ ) then we also have h k (N j ) = h k (N j ′ ). It therefore follows that less nulls in null(P ) occur for h k , that is π k ≤ π i . As π i ≤ π k must hold, we obtain that π i = π k , meaning that h i and h k are equal up to a null renaming. The proof is therefore complete.

Algorithm 2: ChooseM ostSpecif ic(q core (I))

1: Build H P as explained in Proposition 1

{H P has q rows and p columns} 2: row max := 1 ; count max := 0 ; i := 2 3: for all i = 2, . . . , q do 4:

idemP ot := true while idemP ot = true and j ≤ p do 7:

if H P [i, j] is in cons null(P ) then

Let N k = H P [i, j] {N k is in null(P )} 11: if H P [i, k] = N k then 12:
idemP ot := false {h i is not idem-potent} 13: As a consequence, finding a most specific P -homomorphism in q core (I) amounts to (i) discard any row not defining an idem-potent homomorphism and (ii) among the remaining rows, identify one homomorphism satisfying item 2 of Corollary 1. Algorithm 2 shows how to compute such a most specific homomorphism, and we notice that this does not require data access. To end the section, we illustrate Algorithm 2 as follows.

Mark row H P [i]

Example 4 We first consider the context of Example 3, where

I = {B(N 1 , N 2 ), B(N 2 , N 1 ), C(N 1 , a), C(N 2 , a), C(N 3 , a)} and P = {B(N 1 , N 2 ), B(N 2 , N 1 ), C(N 1 , a), C(N 2 , a)}.
In this case, null(P ) = {N 1 , N 2 }, cons null(P ) = {N 3 }, and the associated table H P has been shown already. Applying Algorithm 2 based on the table H P , the following computations are achieved.

The first loop line 3 aims at marking rows defining non idempotent P -homomorphisms (that is, such that h•h = h) and mean-while to find one unmarked row with as many symbols in cons null(P ) as possible, in reference to Corollary 1(2). These computations return the following:

• When processing row 2 of H P , we have H P [2, 1] = N 2 where N 2 is in null(P ), and

H P [i, 2] = N 1 . Since N 1 = N 2 ,
idemP ot is set to false and row 2 is marked on line 13.

• Since there is no other row to process, the loop line 3 returns row max = 1 and count curr = 0.

Hence, Algorithm 2 returns row spec = 1 and so, h m is defined by

h m (N 1 ) = N 1 and h m (N 2 ) = N 2 .
In other words, I is not simplified, which is indeed the expected result. We now illustrate further Algorithm 2, using two more sophisticated cases. First, let ν 0 = {N 1 } and

I 1 = {B(N 1 , N 2 ), B(a, N 2 ), B(a, N 3 ), B(N 4 , N 3 ), C(N 2 , N 2 ), C(N 3 , N 3 )}. In this case, LinkedNull I,N1 = {N 1 , N 2 } and thus, P Set = {P } where P = {B(N 1 , N 2 ), B(a, N 2 ), C(N 2 , N 2 )}.
Moreover, the query

q core : ans(x 1 , x 2 ) ← B(x 1 , x 2 ), B(a, x 2 ), C(x 2 , x 2 )
is generated and its answer against I 1 , q core (I 1 ), is defined in the following table H 1 P :

H 1 P x 1 x 2 1 N 1 N 2 2 a N 2 3 a N 3 4 N 4 N 3
H 1 P has 2 columns and 4 rows due to four possible answers in q core (I 1 ). Moreover, h 1 h 2 , h 2 h 3 and h 2 h 4 . Notice that h 3 and h 4 are not comparable because a, N 3 and N 4 are in cons null(P ). Applying Algorithm 2 based on the table H 1 P , the first loop line 3 achieves the following:

• No row is marked as non-idempotent on line 13. This is so because for every i = 1, . . . , 4, and every j = 1, 2, if

H 1 P [i, j] = N k where N k is N 1 or N 2 , H 1 P [i, k] = N k .
• Regarding the value of count curr, the computed value is 0 for the first row, 1 for row 2, and 2 for rows 3 and 4 (because a, N 3 and N 4 are in cons null(P )). Thus, applying the test line 16, count curr to set to 2, and on line 17, row max is set to 3. Indeed, although for row 4, we have count curr = 2, the test line 16 fails, and thus the value of row max is not changed. Then, row spec is set to 3 on line 19 and cont min is set to 0 on line 20.

Therefore, processing the loop line 21 yields no change and Algorithm 2 returns h m defined by h m (N 1 ) = a and h m (N 2 ) = N 3 , in which case, h m (I 1 ) = {B(a, N 3 ), B(N 4 , N 3 ), C(N 3 , N 3 )}, which is not redundant, when considering N 3 and N 4 as particular 'constants'.

As a more sophisticated illustration of Algorithm 2, let ν 0 = {N 1 } and

I 2 = {B(N 1 , N 2 ), B(a, N 2 ), C(N 2 , N 2 ), C(N 2 , N 3 )}.
Here, LinkedNull I,N1 = {N 1 , N 2 , N 3 } and thus, P Set = {P } where P = {B(N 1 , N 2 ), B(a, N 2 ), C(N 2 , N 2 ), C(N 2 , N 3 )}. Moreover, the query:

q core : ans(x 1 , x 2 , x 3 ) ← B(x 1 , x 2 ), B(a, x 2 ), C(x 2 , x 2 ), C(x 2 , x 3 )
is generated and q core (I 2 ), is defined in the following table H 2 P :

H 2 P x 1 x 2 x 3 1 N 1 N 2 N 3 2 N 1 N 2 N 2 3 a N 2 N 3 4 a N 2 N 2
H 2 P has 3 columns and 4 rows due to four possible answers in q core (I 2 ). Moreover,

h 1 ≺ h 2 , h 1 ≺ h 3 , h 2 ≺ h 4 and h 3 ≺ h 4 .
Applying Algorithm 2 based on the table H 2 P , the loop line 3 achieves the following:

• As above, no row is marked as non idempotent on line 13. This is so because for i = 1, . . . , 4, and j = 1, 2, 3, if

H 2 P [i, j] = N k where N k is N 1 , N 2 or N 3 , H 2 P [i, k] = N k .
• As above, on line 17, row max is set to 3 and thus, row spec is set to 3 on line 19. Here, count min is set to 2 on line 20 because N 2 and N 3 are in null(P ).

When processing the loop line 21, the only row to be considered is row 4, for which match is true, thus implying that the test on line 28 succeeds. Since for row 4, the value of count null is 1 (because row 4 contains the only null N 2 ), the value of row spec is set to 4, line 31. Hence, Algorithm 2 returns h m defined by

h m (N 1 ) = a, h m (N 2 ) = N 2 and h m (N 3 ) = N 2 . In this case, h m (I 2 ) = {B(a, N 2 ), C(N 2 , N 2 )}, which is not redundant.
Homomorphisms have been used in database theory during the last decades, in the field of query optimization [START_REF] Aho | Efficient optimization of a class of relational expressions[END_REF][START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF] (we refer to [START_REF] Abiteboul | Foundations of databases[END_REF] for an overview). We notice in this respect that, in [START_REF] Aho | Efficient optimization of a class of relational expressions[END_REF], a partial pre-ordering between homomorphisms is defined using the same criteria as in Proposition 1, showing that our approach to simplification is closely related to the field of query optimization. Roughly, in our approach, we compare all the answers (h 1 , . . . h q ) for q core and chose one (h m ) among the most specific ones (which are incomparable). From another point of view, if we consider queries Q 1 , Q 2 , . . . , Q q as the instantiations of q core by h 1 , . . . h q , respectively, then h m is a homomorphism such that h m (body(Q i )) = body(Q) for all Q ⊆ Q i . Actually, our simplification technique is based on tableau optimization, as done in [START_REF] Aho | Efficient optimization of a class of relational expressions[END_REF] for query optimization, where the sets of variables and of distinguished variables are, respectively, called, in our approach, the null(P ) and cons null. However, the contexts and the expectations in our approach are fundamentally different from those summarized in [START_REF] Abiteboul | Foundations of databases[END_REF]. Indeed:

• In [START_REF] Abiteboul | Foundations of databases[END_REF], the tableau is built up from the query body, whereas in our approach, the tableau is built up from the answer to a given query.

• Our approach generates one most specific homomorphism, where as the approach shown in [START_REF] Abiteboul | Foundations of databases[END_REF] aims at discarding all non most specific.

As a result, the problem we deal with can be seen as more specific than the general case considered in [START_REF] Abiteboul | Foundations of databases[END_REF][START_REF] Aho | Efficient optimization of a class of relational expressions[END_REF], thus resulting in a specific algorithm.

Query

Algo Purpose q bucket (I) [S] 3, 5 retrieves all nulls in I appearing in an atom p(...) such that p is a predicate in a given set S q degree (I) [S,δmax] 3 for each N in S, checks if N is in I and if δ(N ) < δ max q δ (I) [S,d] 3 for each N in S, if N is in I, sets δ(N ) to d q Iso (I) [S] 5 retrieves in I all atoms isomorphic to those in S Figure 2: Queries used in our algorithms

Incremental Updating

In [START_REF] Chabin | Consistent updating of databases with marked nulls[END_REF], update algorithms work on in-memory data, using no DataBase Management System (DBMS). This version considers a DBMS, based on which data access is implemented through queries. In this section, we show how to implement updates by restricting data access as much as possible.

Insertion

Algorithm 3 describes the insertion in D of the atoms in the set iRequest. On line 1, the side-effects of the insertion are computed and stored in the set ToIns, and then the instance D ′ = D ∪ T oIns is simplified on line 3 through the computation of its core. If all nulls in the simplified instance have a degree less than the specified maximal degree δ max (on line 4), null degrees are all set to 0 (on line 5) and D ′ is returned since, as shown in [START_REF] Chabin | Consistent updating of databases with marked nulls[END_REF], it is always consistent; otherwise, the database is not modified. return D Contrary to the algorithms in [START_REF] Chabin | Consistent updating of databases with marked nulls[END_REF], the main steps in Algorithm 3 are designed in an incremental manner. First, to avoid generating any non necessary side effect atoms, an incremental version of the chase procedure considered. According to this procedure, a constraint c is activated only when the following conditions hold:

(i) body(c) contains at least one atom that maps to one being inserted, and (ii) atoms in body(c) that do not respect (i) map to atoms in the database instance D. This new chase differs from the one in [START_REF] Chabin | Consistent updating of databases with marked nulls[END_REF] in the following aspects: (a) only the rules c concerned by insertions are triggered and (b) queries are built to find in D instantiations for atoms in body(c).

Algorithm 4, called on line 1, implements our incremental chase procedure. The set T oIns initially stores iRequest (line 1) and then, stores the generated side-effects (line 3) through the while loop on line 2, defined by the following conditions: T oIns := T oIns ∪ {h ′ (head(c))} {Degrees of new nulls in h ′ (head(c)) are set to d max + 1, where d max is the maximal degree in h(body(c)), or 0 if h(body(c)) contains no null} 4: return T oIns

• A constraint c is triggered only if at least one atom in body(c) is instantiated to an atom in T oIns.

• The condition δ(h ′ (head(c)) ≤ δ max ensures that only (side-effect) atoms whose degree is less than the maximum null degree are kept. The instantiation h ′ extends h by assigning new null values to existential variables in head(c). When performing a chase step, the degree of new nulls are also computed.

• The last condition ensures termination along with a simplification. Indeed, if an instantiation of h ′ (head(c)), referred to as h ′′ (h ′ (head(c))), exists in D ∪ T oIns, the constraint is satisfied, and no atom is inserted in T oIns. For instance, suppose D 1 = {Authors(Elin, P 2 )}, C = {c 5 } (Figure 1) and iRequest = {Researcher(Elin)}. The atom Authors(Elin, N 1 ), generated by c 5 , is not inserted since it maps to Authors(Elin, P 2 ).

Another difference between the algorithm in [START_REF] Chabin | Consistent updating of databases with marked nulls[END_REF] and Algorithm 3, is the simplification step on line 3 to maintain the database instance irredundant. Indeed, based on our earlier discussion in Section 4, D ∪ T oIns is simplified with respect to the nulls in NullBucket, computed through the query q bucket on line 2. Thus, only the nulls in NullBucket and their 'linked' nulls are considered, thus optimizing the computation of the core of D ∪ T oIns. 14 Notice also that, since the degree of nulls is checked only during the chase, before returning the updated instance, the degrees of all nulls are set to 0 on line 5 of Algorithm 3. Our incremental algorithm for the deletion from D of atoms in dRequest is displayed as Algorithm 5. On line 1, all atoms in D isomorphic to one in the set dRequest are retrieved through the query q iso . For instance, if dRequest = {P (a, N 1 )} and D 1 = {P (a, N 5 )}, then query q iso returns {P (a, N 5 )}. The side-effects are then computed on line 6, recalling from Section 2 that the side effects involve not only atoms to be deleted, but also atoms to be inserted as side-effects. In Algorithm 5, the corresponding sets are respectively denoted by T oDel and T oIns.

Deletion

Once these side-effects have been incorporated in D to produce D ′ (line 3), this new instance is simplified as in the case of insertion: impacted nulls are generated on line 4 and the simplified instance is computed on line 5. We notice that, contrary to insertions, deletions are never rejected.

As for insertions, side effects are computed incrementally through Algorithm 6. First, it may happen that the deletion of an instantiated atom A makes the database inconsistent when it is a consequence of a constraint c. To find all such constraints c, we reason backward on C to find an instantiation h such that h(head(c)) = A. Then h is extended to verify, in a forward reasoning, whether body(c) can be triggered and generate A again.

The idea is to check whether c generates an atom isomorphic to an atom being deleted (Algorithm 6, line 3). If so, at least one atom in h(body(c)) should be deleted in order to prevent c from being triggered. This atom is then inserted in T oDel (line 4). Notice that, to avoid non-determinism, it is assumed that the atom to be deleted has been marked as '-' during rule design.

If no atom isomorphic to an atom to be deleted is generated, a new set called N ewT oIns is generated as the side-effects of inserting the new instance of head(c) and all atoms in T oIns (line 6). If no atom in N ewT oIns meets an atom to be deleted and if the degrees of the involved nulls are less that δ max , then these atoms are inserted in T oIns (line 8). Otherwise, the marked atom from h(body(c)) is inserted in T oDel (line 10). if ∃h ′ such that h ′ (body(c)) = h(body(c)) and h ′ (head(c)) is isomorphic to h(head(c)) then if N ewT oIns = Del = ∅ and δ(N ) < δ max for all nulls N in N ewT oIns then 8:

T oIns = T oIns ∪ N ewT oIns 9:

else 10:

T oDel := T oDel ∪ {h ′ (body -(c))} 11: return T oDel, T oIns is not isomorphic to Enrolled(Sten, CS) (line 3). The next step consists in testing whether the atom Enrolled(Sten, N 1 ) should be added to T oIns. To this end, Algorithm 6 chases forward, starting with Enrolled(Sten, N 1 ) (line 6) to generate GrantEligible(Sten). This atom being in T oDel (line 7), Student(Sten) is added to T oDel, and nothing is added in T oIns. Algorithm 6 returns T oDel = {Student(Sten), GrantEligible(Sten), Enrolled(Stem, CS), Enrolled(Sten, N 1 )}, and T oIns = ∅. Algorithm 5 then performs the deletions and the resulting database instance is empty.

Queries for Incremental Processing

By implementing our method using graph and relational database models, our goal is to study performance aspects, and to raise issues concerning the database design regarding queries.

Graph Data Model

The DBMS considered in this work is Neo4J, which deals with attributed graphs. Cypher is a wellestablished language for querying and updating property graph databases. As explained in [START_REF] Francis | Cypher: An evolving query language for property graphs[END_REF], 'a Cypher query takes as input a property graph and outputs a table. These tables can be thought of as providing bindings for parameters that witness some patterns in a graph, with some additional processing done on them'. The central concept in Cypher queries is pattern matching. The MATCH clause searches for homomorphisms identifying a given pattern in the queried graph. The returned result is an instance over a table where attributes correspond to the variables in the Cypher query.

Our approach involves managing null values that have to be retrieved based on their co-occurrences as arguments of atoms (Section 4). Given a null N 1 we need to efficiently detect atoms having N 1 as one of its arguments, and then for every N occurring with N 1 , to recursively access the atoms having N as argument. In doing so, the set of nulls is partitioned into blocks whose elements are those nulls that have to be considered in the simplification steps. To make such retrieval efficient, we adopt a model close to the logical formalism used in our previous explanations, composed of three types of nodes. Given an atom P (t 1 , . . . , t n ) our graph database represents P as a node, linked to other nodes representing the terms t 1 , . . . , t n . In this context, nodes in our graph database are of three possible types distinguished by labels, and all nodes have properties, among which one is symbol. More precisely:

• Nodes of type Atom have one label :Atom representing the predicate symbol in an atom. This predicate symbol is the value of property symbol of such a node.

• Nodes of type Constant representing constant values. Such nodes have two labels, :Element and :Constant, and the value of their property symbol is the constant itself.

• Nodes of type Null reprensenting nulls. Such nodes have two labels, :Element and :Null, and the value of their property symbol is the name of the null prefixed with ' '.

An edge links nodes with label :Atom to nodes with label :Element. Moreover, an edge has the property rank, allowing to refer to the terms of an atom by their positions. Figure 3 illustrates the schema of the atom P (t 1 , . . . , t n ) by representing constant terms by t i and nulls by t j . Notation below edges indicates the cardinality of the relationship between an atom and its terms: an element is connected to at least one atom and atoms may have no terms.

Figure 4 illustrates part of our database instance (rectangular nodes are atoms and circular nodes are elements). As explained before, our model benefits certain operations. However, it increases the cost of conversions between the graph-format and the logic-format for an atom. Such conversions are essential for the communication between the database and the procedures performing some computations locally. To optimize these conversions and graph traversals, we introduce the following redundancies in our database model, which have significantly improved our implementation (see Section 7).

• To avoid edge traversal.

For each node :Atom, we store, as its attribute, an ordered list containing all its terms. In Figure 3, the rectangular node shows this new attribute: terms. For example, to obtain atom Authors(Elin, P 269 ) from the instance in Figure 4 starting with the node n 117 , instead of traversing edges r 19 and r 20 , we just have to retrieve the attributes terms of node n 117 .

• To allow efficient access to nodes.

(a) A uniqueness constraint is added on the Element symbol (implying, e.g., that there is a unique node in the database to represent Elin). (b) An index is built on the symbol of each atom, and a uniqueness constraint is defined on the couple symbol/terms (implying, e.g., that there is a unique node in the database to represent atom Authors(Elin, P 269 ).

The algorithms presented in the previous sections involve the construction of queries in Cypher to be evaluated on our Neo4J database. We now focus on two of them: one needed when chasing and one that computes the set LinkedNull. Query for chasing. Chasing means applying constraints. The application of a constraint happens when its body can be instantiated by facts in the database. Thus, to decide on the application of a constraint c, we need a query capable of :

n
(1) Verifying whether the database instance contains the facts necessary for the instantiation of body(c) and

(2) returning a non-empty answer only if a corresponding instantiation for head(c) does not already exist in the database.

In a logic formalism, if c is of the form c : L 1 (α 1 ), . . . , L m (α m ) → L 0 (α 0 ), we should write the query

q ch : Q(α) ← L 1 (α 1 ), . . . , L m (α m ), not L 0 (α 0 )
, where α is the list of variables corresponding to variables in body(c), that is, variables universally quantified variables of c. The idea here is: if h t is an instantiation such that h t (body(c)) ⊆ D, the query q ch has a non empty answer only if h ′ t (L 0 (α 0 )) ∈ D for any extension h ′ t of h t . Figure 5 shows the Cypher template of query q ch . We first look for atoms that match body(c). On the line 3 in Figure 5, the WHERE NOT EXISTS clause is used to check that no instance of the head(c) exists. Two expressions are built (expr1 and expr2). Terms in α are treated orderly. Notice that expr1 is built for dealing with atoms in body(c) and expr2 is built for dealing with the atom in head(c). The first MATCH acts as a starting point of the graph traversal. It is built with constants or nulls (e.g., (x k :Element:Constant {symbol:t i })) as we usually consider constraints instantiated by insertions. Then the pattern, built with the second MATCH and the WHERE clause, links the constants to the positions in the atoms of the body.

Separating the two MATCH allows us to guide the query planner to first search the constants (called node seeking) and then look for the connected nodes to find the atoms. This is important because, in doing so we drastically reduce the search space, because constants are unique values retrieved in O(1), and only :Atom connected nodes are searched, thus avoiding to visit all instance nodes of the predicate.

Example 7 Considering the insertion of Authors(Bob, P 1 ) in the database instance D = {Supervises(Alice, Bob), Authors(Alice, P 1 )} with the only constraint c 6 defined by: c 6 : Authors(X, P ), Authors(Y, P ), Supervises(X, Y ) → P hDP aper(Y, P, Z) Two instantiations h and h ′ should be checked: one on the first atom Authors (h(X) = Bob, h(P ) = P 1 ) and one for the second atom Authors (h ′ (Y ) = Bob, h ′ (P ) = P 1 ). Figure 6 shows the chase query for the instantiation h ′ of the constraint c 6 .

Query to find LinkedNull sets. Figure 7 presents the Cypher query that implements the Linked-Null definition (Section 4) for building partitions of atoms. The clause UNWIND can transform any list into individual rows. For instance, if we consider a list ['Elin', 'Sten'] of constant symbols, the clause UNWIND over such a list gives a table with one column c and two rows whose values are 'Elin' and 'Sten'. In Figure 7, the clause UNWIND (line 1) is used to set nulls from a given list to our initial table with one row for each null. The goal of the first MATCH (line 2) is to select sub-graphs with atoms sharing the same null. On the line 3, the range of the relationship (*1..) indicates that node nullValueNode can be connected to a node endNode by a path pathP of arbitrary length. Moreover, the direction is ↔ indicates that pathP can be composed by edges having any orientation.

The MATCH clause looks for paths starting with the null of the nullValueNode to any other node representing an atom which is not nullValueNode itself (condition imposed by the WHERE clause). On the line 6, the WITH clause performs a 'group by'. It allows to structure our working table with tuples where each null nullValueNode is associated to a list of endNodes (the nodes reached by paths pathP). On the line 7 a new organisation is built: linkedNodes is divided into two lists, one containing nodes that represent predicate symbols (linkedAtoms) and one for those representing nulls (linkedNulls). Notice that we place the initial node nullValueNode in the first position of the latter. The resulting table partitions the atoms: each atom is associated to a list of nulls (those it is concerned by). In the worst case, the former list contains all atoms having a null in the database.

Relational Data Model

Given an instantiated atom P (t 1 , . . . , t n ) in the logical representation oinf a database, our relational model consists in defining a table whose schema is R P [A 1 , . . . A n ] where all attributes are of type text. Notice that P (t 1 , . . . , t n ) represents a tuple on R P and, thus, (t 1 , . . . , t n ) are values that can be constants or nulls (nulls have the symbol as a prefix). The translation of logical queries into SQL is straightforward. However, some operations require the construction of procedures to implement recursive queries. Algorithm 7 shows the implementation of LinkedNull in the relational context.

We argue in this respect that implementing Algorithm 7 using a recursive SQL query is not efficient. Indeed, to do so an additional table for storing the pairs of linked nulls is needed, and the following steps are necessary: (a) a recursive SQL query to compute the transitive closure and (b) a scan of the whole database to retrieve all corresponding atoms. Moreover, the additional table needs to be maintained up to date after each update, which requires further processing. for all table R P in the database schema do We also notice that the implementation of an incremental chase in the relational model follows the idea of setting up query q ch (as explained in Section 6.1) which can be written as an SQL query involving a NOT EXISTS clause.

Discussion

Querying graph database is significantly impacted by graph schema design. The schema we have chosen transforms nulls into first-citizen elements and facilitates operations where, by 'picking' a null, we can easily detect all atoms connected (directly or indirectly) to it. For instance, in Figure 4, if we 'pick' the null N 1 (the gray node n 11 ), we detect the atoms connected to it together with other nulls (i.e., N 2 , the blue node n 12 ). In other words, this model optimizes queries looking for linked nulls. However, it may not be appropriate for other kinds of queries. For instance, in the chase query, our model generates complex patterns that can be costly. The relational model is less flexible than graph models, and thus its impact on querying is weaker. However, relational model is not appropriate for the implementation of recursion, and nulls cannot be set as first-citizen element (identical null values appear repeatedly in the database instance). Algorithm 7 shows that to implement LinkedNull we have to check null values for each table, compromising the idea of an incremental approach. On the other hand, the graph model is well suited for implementing incremental algorithms, because as seen in Section 6.1, this model allows implementing LinkedNull by visiting only the atoms linked to nulls in N ullBucket, as expected when considering an incremental computation.

Experimental Results

We gauge the performance of our incremental updating approach by analysing experiment results over a benchmark working on a graph (Neo4J) and a relational (MySQL) DBMS. A benchmark run executes an update on a database instance.

To build our database instances, we firstly view the original data sets from a FOL point of view. Roughly speaking, a node or a relationship in the original data sets corresponds to a predicate symbol, while their properties are the terms. The conversion to our database models is straightforward, as presented in Section 6. Nulls are inferred from already missing properties. Constraints are handcrafted, created from data observation and added to the databases we use for experiments. The following three data sets are the basis of our instances:

• Movie1 , available as a Neo4J instance, is a collection of data concerning movies, actors, directors.

This data set contains 7 predicate symbols (with arity 2-4).

• GOT2 , available as a Neo4J instance, deals with the interactions between different characters in the book Game of Throne. This data set contains 19 predicate symbols (artiy 2-14).

• LDBC3 , available as a data set of the Linked Data Benchmark Council, offers synthetic data sets for benchmarking. This data set contains 23 predicate symbols (artiy 1-2).

From the LDBC data sets we build several instances, by varying their size or the number of nulls. To control the size of instances, their construction is the result of: (i) randomly selecting k facts, respecting the distribution of the original data set and, then, (ii) applying the 39 hand-made constraints on them. The result is a consistent database instance with nulls. Figure 8 presents a summary of our database instances (or samples). It is worth noting that, for example, an instance denoted as LDBC 1K, comes from a random selection of 1000 facts which evolves to 2248 after the chase and core processing. To control the number of nulls, we proceed as follows: we take the largest LDBC instance, i.e., with 10 000 facts, and replace all nulls with constants. Then, we choose, randomly, some constants that are replaced by linked nulls. Figure 8 Runs are built from instances in Figure 8 by (i) varying the update type (insertion or deletion); (ii) altering the size of the update (1, 5, 10 and 20 atoms) and (iii) augmenting artificially the number of facts in an instance. This latter step is done through the duplication of data n-times (1, 2 and 5), together with the renaming of the constants and the null names at each copy.

Each run performs 10 iterations plus 3 warm-up iterations (i.e., an ordinary iteration used to preload the system and database cache) not counted in the execution time. Between each iteration, the original database instance is restored, and the Java garbage collector is triggered for consistent time measuring. The benchmarks are implemented in Java 16 with MySQL 8 and Neo4J 4.1 and executed on a Rocky Linux 8.7 virtual server with 4 vCPU and 16 GB of memory (8 reserved for the database and 5 for the Java program) through docker 20.10.21. In the docker container of a database instance, the average of read/write on disk is 1 GB s -1 The same server hosts: (i) one database server at the time and (ii) the benchmarks with only 4 vCPU.

Notice that, even if this configuration allows us to assess our implementations over different DBMS, our experiment performances are not representative of real world situations, where more powerful and dedicated hardware is available.

We first compare the incremental approach presented in this paper to the from-scratch in-memory approach in [START_REF] Chabin | Consistent updating of databases with marked nulls[END_REF]. For this aspect, comparisons are performed only on the database Movie because the from-scratch in-memory version requires a huge amount of memory for its computation. We have an average of 9017 ms for an update with the in-memory version and scale of 1 (initial size of the instance). MySQL has an average of 151 ms and Neo4J has 2380 ms. For this small instance, the incremental approach is comparable with the from-scratch approach. Considering an instance five times larger, we get an average of 888 966 ms for the in-memory version, 595 ms for MySQL and 2706 ms for Neo4J. Thus, it should be clear that using a DBMS in which an incremental version of update processing is implemented, allows for efficiently updating large databases that do not fit in main memory.

Next, we analyse the performance of incremental updating with respect to the number of atoms (database size) and nulls of an instance. We denote by incompleteness degree the number of distinct LinkedNull sets on a database. We also investigate the number of queries generated to interact with the DBMS. Figure 10 presents our experiment results. On each plot, the right axis, indicates the total number of facts in the instance. The curves show the average of resulting values for all runs corresponding to the displayed abscissa.

We first note that the update type (insertion or deletion) has no real impact on the performance of our approach. Figure 10a shows that the number of queries is linear on the number of nulls, except for three down spikes when the degree of incompleteness of the database instance is low. This is the case for the database Movies, and the down spikes coincide to a situation where only this database is concerned. Indeed, thanks to the use of multiple data sets, we observe here that the predicate arity (i.e., the number of edges per node or the number of columns in a table) may have an impact on our results. Linearity with respect to the number of nulls is explained by the fact that consistency preservation implies the generation of new data linked by their nulls. Thus, due to our construction method, bigger databases imply more linked nulls (i.e., bigger LinkedNull sets). Incremental updates generate q Bucket to retrieve impacted nulls. Bigger databases likely have more impacted nulls willing to be simplified during the core computation, increasing the number of necessary q core queries.

Consequences of bigger LinkedNull sets are:

(i) in MySQL, Algorithm 7 generates a large amount of queries and (ii) in Neo4J, the unique query needed to retrieve a LinkedNull set is more complex and, thus, more time-consuming. 10d).

MySQL

Experimental results in terms of execution time of our updating approach is shown in Figures 10b and10c. In MySQL (Figure 10b), update execution time is linear in the number of nulls while the database size has little impact. Indeed, as the number of queries increases with the number of nulls, update execution time in MySQL increases accordingly. In Neo4J (Figure 10c), update execution time is more significantly impacted by the size of the instance.

The explanation of this discrepancy comes from the separate analysis of the performance of the main operations of our approach (Figures 9 and10d). The data model chosen in the Neo4J version optimizes the retrieval of LinkedNull, but is not appropriate to operations involving simplification (Section 4). Such operations involve complex pattern matching which are known to be expensive. The chase (Figure 9) is the most expensive operation for Neo4J, mainly due to the fact that it includes a simplification step (e.g., if A(a, b) ∈ D and A(a, N 1 ) is generated by a constraint, then the insertion of A(a, N 1 ) is canceled).

For the sake of readability, plots do not show results on GOT instances with more than 17 000 nulls. The results on this data set are similar: execution time evolves linearly with respect to nulls in MySQL and follows the size of the database in Neo4J. With the GOT runs, we achieve a mean execution time of [START_REF] Fan | Incrementalizing graph algorithms[END_REF]

Related Works

Our work goals include four important features of modern applications: incompleteness, consistency as a measure of quality, incremental tools for efficient data processing and adaptability to graph data models. Solid basis have been established for treating incompleteness of relational databases [START_REF] Fagin | Updating logical databases[END_REF][START_REF] Grahne | The Problem of Incomplete Information in Relational Databases[END_REF][START_REF] Imielinski | information in relational databases[END_REF][START_REF] Reiter | A sound and sometimes complete query evaluation algorithm for relational databases with null values[END_REF][START_REF] Zaniolo | Database relations with null values[END_REF], particularly for querying. Much less attention has been given to updates on incomplete databases, although important work, such as [START_REF] Abiteboul | Mise-à-jour des bases de données contenant de l'information incomplète[END_REF][START_REF] Fagin | On the semantics of updates in databases[END_REF][START_REF] Winslett | Updating Logical Databases[END_REF]] can be cited. Today, integrating and exchanging data are very common, leading to the proliferation of applications involving dynamic incomplete data on emerging data models that deal with more general graph-structured data. Incompleteness beyond the relational data model has received much less attention [START_REF] Sirangelo | Representing and Querying Incomplete Information: a Data Interoperability Perspective[END_REF], and, in this context, updating with respect to constraints is rarely considered. Indeed, consistency maintenance is usually left aside in favour of efficiency, which can prove costly when we are concerned with the quality of analytical results. Work such as [START_REF] Ferrari Alves | Update rules in datalog programs[END_REF][START_REF] Link | An arithmetic theory of consistency enforcement[END_REF]29] witnesses the complexity of the problem of keeping a database consistent with respect to constraints in a dynamic environment. In [START_REF] Flouris | Formal foundations for RDF/S KB evolution[END_REF][START_REF] Ferrari | RDF updates with constraints[END_REF][START_REF] Ferrari | Updating RDF/S databases under constraints[END_REF] we find newer proposals, adapted to the RDF world, that considers constraints in our traditional database viewpoint (i.e., not in the web semantic standard way, where constraints are just inference rules [START_REF] Gottlob | Ontological queries: Rewriting and optimization[END_REF][START_REF] Lausen | Sparqling constraints for RDF[END_REF][START_REF] Patel-Schneider | Using description logics for RDF constraint checking and closedworld recognition[END_REF]). It is worth noting that the use of tuple generating constraints (TGD) increases expressiveness at the cost of difficulties that involve a chase procedure (cf. a survey in [START_REF] Onet | The chase procedure and its applications in data exchange[END_REF], a benchmark in [START_REF] Benedikt | Benchmarking the chase[END_REF]) to compute semantics and the generation of side effects in an update context -imposing extra insertions or deletions (with respect to those required by the user) to preserve consistency. The literature offers sufficient conditions to avoid a non-terminating chase which consist in limiting the format of constraints. We instead introduce δ max , keeping the possibility of dealing with any kind of constraints while avoiding infinite processing. Furthermore, use simplifications to keep the database instance as small as possible and to avoid the presence of useless nulls, i.e., database maintenance consists in keeping its core (which follows the ideas in [START_REF] Fagin | Data exchange: getting to the core[END_REF]) whose implementation is ensured by a simplification routine performed in association to update routines.

In brief, data analytic tools become essential in different application domains and their quality relies on data consistency. But in order to deal with huge scale applications, we must aim at efficient data processing solutions [START_REF] Sirangelo | Representing and Querying Incomplete Information: a Data Interoperability Perspective[END_REF], bringing incremental solutions to the front of the stage, particularly when working with new data models (as done in the XML context [START_REF] Abrão | Incremental constraint checking for XML documents[END_REF][START_REF] Balmin | Incremental validation of xml documents[END_REF][START_REF] Bouchou | Updates and incremental validation of XML documents[END_REF]). In the context of graph databases, the approach in [START_REF] Fan | Incrementalizing graph algorithms[END_REF] proposes a method for 'incrementalizing' graph algorithms abstracted in a fix-point model. Our approach cannot be summarized by that proposal. As seen before, we can outline our method in the expression D ′ = core |N ullBucket (upd |U ((D♦U )) where U is the set of user's required updates -this set is increased through an inference process that generates side-effects. The proposal in [START_REF] Fan | Incrementalizing graph algorithms[END_REF] needs a 'complete' set of updates as input. In other words, our fix-point operation involves changes on the update set while in [START_REF] Fan | Incrementalizing graph algorithms[END_REF] the update set is fixed. Their goal is to incrementally compute new answers on an updated graph and not to incrementally update the graph. As the core computation is not a fix-point one, it is not in the scope of [START_REF] Fan | Incrementalizing graph algorithms[END_REF].

Finally, our experiments reinforce the idea that graph schema design has a significant impact on query performance. Our graph schema is designed to optimize one type of query and performs badly to those that differ widely. Schema optimization may be a solution: as in [START_REF] Alotaibi | Property graph schema optimization for domain-specific knowledge graphs[END_REF], in this paper, it is done through techniques that reduce edge transversal.

Conclusions

This paper contributes to improve the maintenance of consistent incomplete databases by proposing incremental routines that interact with database systems. It extends prior work in [START_REF] Chabin | Consistent updating of databases with marked nulls[END_REF] where a from-scratch in-memory method was proposed. Two implementations of our approach, one under a graph database model and one under the traditional relational database model, are presented. Experiment results raise questions about the representation of nulls in a graph database. Indeed, this work is also a step towards incremental updating attributed graphs with incomplete data. It illustrates the impact of schema graph design in querying and, consequently, in the performance of an incremental updating approach that relies on two main queries: one that looks for linked nulls and another that looks for redundant atoms willing to be simplified. Property graph model has an increasingly important role today, the handling of nulls in such a model is related to schema definition and query optimization issues that need to be further explored.

c1:Figure 1 :

 1 Figure 1: Set of (general) constraints

(

  B) Updates. Updates are insertions or deletions. (B.1) Insertions. Given a database instance D satisfying a set of constraints C, an updated database is the result of inserting facts in D while maintaining constraint satisfaction. Let C 1 = {c 1 , c 6 , c 7 , c 8 }, D 1 = {Researcher(Elin), Supervises(Elin, Sten), Authors(Elin, P 269 )}, and the set of required insertions iRequest = {Authors(Sten, P 269 )}.

Case 1 .

 1 Let dRequest = {P hDP aper(Sten, P 269 , 2022)}. First the fact P hDP aper(Sten, P 269 , 2022) is removed from D ′ and then, constraint satisfaction is checked as done for insertions. Here, D ′ \ {P hDP aper(Sten, P 269 , 2022)} does not satisfy c 6 because Sten is still present as an author of paper P 269 . As above, consistency is restored by inserting P hDP aper(Sten, P 269 , N 2 ). The resulting database D ′′ = (D ′ \ {P hDP aper(Sten, P 269 , 2022)}) ∪ {P hDP aper(Sten, P 269 , N 2 )} is consistent and implements the deletion because it does not contain the atom to be deleted.

5 :

 5 count curr := 0 ; j := 1 6:

  if idemP ot = true then16: if count curr > count max then 17: row max := i 18: count max := count curr 19: row spec := row max 20: Let count min be the number of distinct nulls in null(P ) occurring in H P [row max] 21: for all i = 2, . . . , q do 22: if row H P [i] is not marked and i = row max then 23: match := true ; j := 1 24: while match = true and j ≤ p do 25: if H P [row max, j] is in cons null(P ) and H P [row max, j] = H P [i, j] then 26: match := false 27: j := j + 1 28: if match = true then 29: Let count null be the number of distinct nulls in null(P ) occurring in H P [i] 30: if count null < count min then 31: row spec := i 32: count min := count null 33: return h m , the homomorphism defined by H P [row spec]

Algorithm 3 :

 3 Insert(D, C, δ max , iRequest) 1: T oIns := Chase4Insert(D, C, δ max , iRequest) 2: N ullBucket := {N j | N j is a null obtained by q bucket (D ∪ T oIns) [T oIns] } 3: D ′ := Simplif y(D ∪ T oIns, N ullBucket) 4: if q degree (D ′ ) [N ullBucket,δmax ] then 5: q δ (D ′ ) [N ullBucket,0]

Algorithm 4 :

 4 Chase4Insert(D, C, δ max , iRequest) 1: T oIns := iRequest 2: while ∃c ∈ C and ∃h such that h(body(c)) ⊆ D ∪ T oIns and h(body(c)) ∩ T oIns = ∅ and δ(h ′ (head(c)) ≤ δ max , where h ′ ⊇ h maps to new nulls all existential variables in head(c), and there does not exist h ′′ such that h ′′ (h ′ (head(c)) ∈ D ∪ T oIns do 3:

Example 5

 5 Let C = {c 1 , c 3 , c 4 , c 10 , c 11 , c 12 }, δ max = 3 and the following database instance: D = { Authors(N 1 , P 2 ), Authors(Alice, N 2 ), P ublication(P 2 ), P ublication(N 2 ), Researcher(N 1 ), Researcher(Alice), Supervises(N 1 , N 3 ) } Let iRequest = {Authors(Alice, P 5 ), Student(Bob)}. Running Algorithm 3 in this case is as follows. Constraint c 4 is triggered due to the insertion of Authors(Alice, P 5 ) and constraints c 10 , c 11 , c 12 are triggered due to the insertion of Student(Bob). Line 1 returns the following set T oIns, where null degrees are shown as exponents: T oIns = { Authors(Alice, P 5 ), P ublication(P 5 ), Student(Bob), Enrolled(Bob, N 0 To simplify D ∪ T oIns, the query q Bucket retrieves in D the nulls concerning Authors (i.e., N 1 and N 2 ), P ublication (i.e., N 2 ), Enrolled (i.e., N 4 ), Degree (i.e., N 4 , N 5 ) and Language (i.e., N 4 , N 5 , N 6 ). Therefore, N ullBucket = {N 1 , N 2 , N 4 , N 5 , N 6 }, and by Algorithm 1, we obtain that LinkedNulls D,N1 = {N 1 , N 3 }, LinkedNulls D,N2 = {N 2 }, and for i = 4, 5, 6, LinkedNulls D,Ni = {N 4 , N 5 , N 6 }. The simplification of D ∪ T oIns (line 3 of Algorithm 3) results in: D ′ = { Authors(N 1 , P 2 ), Authors(Alice, P 5 ), P ublication(P 2 ), P ublication(P 5 ), Researcher(N 1 ), Researcher(Alice), Supervises(N 1 , N 3 ), Student(Bob), Enrolled(Bob, N 4 ), Degree(N 4 , N 5 ), Language(N 4 , N 5 , N 6 ) }.

Algorithm 5 :

 5 Delete(D, C, δ max , dRequest) 1: isoDel := q Iso (D) [dRequest] {isoDel contains atoms in D that have to be deleted} 2: T oDel, T oIns := Chase4Delete(D, C, δ max , isoDel) 3: D ′ := (D ∪ T oIns) \ T oDel 4: N ullBucket := {N j | N j is a null obtained by q bucket (D ′ ) [T oIns∪T oDel] } 5: D ′ := Simplif y(D ′ , N ullBucket) 6: return D ′

Example 6

 6 Let D 0 = {GrantEligible(Sten), Student(Sten), Enrolled(Sten, CS)}, C = {c 10 , c 13 } and dRequest = {GrantEligible(Sten)}.On line 2, Algorithm 5 calls Algorithm 6 to perform an incremental chase. T oIns and T oDel are respectively initialized to ∅ and {GrantEligible(Sten)}, and a first iteration of the loop on line 2 is run. Constraint c 13 is concerned by the deletion, because for h such that h(head(c 13 )) = GrantEligible(Sten), as Enrolled(Sten, CS) is in D, c 13 generates GrantEligible(Sten) (line 3). Therefore, T oDel is set to {GrantEligible(Sten), Enrolled (Sten, CS)} and T oIns remains empty.In the second iteration of the loop, c 10 is detected to be concerned by the deletion of the atom Enrolled(Sten, CS). With Student(Sten) in D, c 10 generates Enrolled(Sten, N 1 ), which Algorithm 6: Chase4Delete(D, C, δ max , isoDel) 1: T oIns := ∅ and T oDel := isoDel 2: while there exist c ∈ C and h such that h(head(c)) ∈ T oDel and h(body(c)) ⊂ (D \ T oDel) ∪ T oIns do 3:

4 :: else 6 :

 46 T oDel := T oDel ∪ {h ′ (body -(c))} 5N ewT oIns := Chase4Insert(D, C, δ max , T oIns ∪ {h ′ (head(c))}) 7:

Figure 3 :

 3 Figure 3: Graph database schema.

Figure 4 :

 4 Figure 4: Graph database instance (extract). Optimization labels and attributes are omitted.

Figure 6 :

 6 Figure 6: Cypher template for Example 7

1

  UNWIND $ n u l l s AS nullPredName 2 MATCH ( n u l l V a l u e N o d e : Element : N u l l { v a l u e : nullPredName } ) , 3 pathP = ( n u l l V a l u e N o d e ) -[ * 1 . . maxPathLength] -( endNode ) 4 WHERE endNode <> n u l l V a l u e N o d e AND 5 ALL( n IN n o d e s ( pathP ) WHERE NOT ( n : Co n st a n t ) ) 6 WITH COLLECT( DISTINCT endNode ) AS l i n k e d N o d e s , n u l l V a l u e N o d e 7 WITH 8 [ n IN l i n k e d N o d e s WHERE ( n : Atom ) ] AS l i n k e d A t o m s , 9 [ n u l l V a l u e N o d e ] + [ n IN l i n k e d N o d e s WHERE ( n : N u l l ) ] AS l i n k e d N u l l s 10 UNWIND l i n k e d A t o m s AS a 11 RETURN a . symbol a s a , a . t e r m s a s e , l i n k e d N u l l s

Figure 7 :

 7 Figure 7: Cypher template to find LinkedNull sets

Algorithm 7 :

 7 FindLinkedNull(D, N ullBucket) 1: newN ull := ∅, allN ulls := ∅, linkedN ullSet := ∅ 2: while N ullBucket = ∅ do 3: allN ulls := allN ulls ∪ N ullBucket 4:

5 :

 5 for all tuple u in (select * f rom R P where (A 1 in N ullBucket) or . . . or (A n in N ullBucket)) do 6: build atom P (u); add P (u) in linkedN ullSet 7: for all null value N ∈ null(u) do 8: if N ∈ allN ulls then 9: add N in newN ull 10: N ullBucket := newN ull 11: newN ull := ∅ 12: return linkedN ullSet

Figure 8 :

 8 Figure 8: Database instances (our samples).

2 • 10 5 3 • 10 5 4 • 10 5 5 • 10 5 6 • 10 5

 55555 Nb

Figure 10 :

 10 Figure 10: Benchmarks results of 540 scenarios, average over 10 runs

  nullValueNode endNode pathP n 11 n 111 [n 11 , r 11 , n 111 ] n 11 n 118 [n 11 , r 22 , n 118 ] n 11 n 124 [n 11 , r 33 , n 124 ] n 11 n 12 [n 11 , r 33 , n 124 , r 34 , n 12 ] n 11 n 112 [n 11 , r 33 , n 124 , r 34 , n 12 , r 12 , n 112 ] 111 , n 118 , n 124 , n 112 ] [n 11 , n 12 ]

	After the first WITH line 6, we have:
	nullValueNode		linkedNodes
	n 11	[n 111 , n 118 , n 124 , n 12 , n 112 ]
	After the second WITH line 7, we have:
	linkedAtoms	linkedNulls
	[n

  presents database instances used in our runs, eight having nulls, and one non-null instance. All the database instances are generated just once. By following this creation process, they are consistent and minimal.

	Database	Nb of facts Nb of nulls Nb of rules Null/Facts (τ )
	Movie	604	340	12	0.56
	GameOfThrone	24818	17232	32	0.69
	LDBC 1K	2248	190	39	0.08
	LDBC 10K	16559	1183	39	0.07
	LDBC 10K 0N	16559	0	39	0.00
	LDBC 10K 50N	16559	50	39	0.00
	LDBC 10K 100N	16559	100	39	0.01
	LDBC 10K 500N	16559	500	39	0.03
	LDBC 10K 1000N	16559	1000	39	0.06

  634 ms with MySQL and 5216 ms with Neo4J for 24 818 facts and 17 232 nulls. Increasing the size to 124 090 facts and 86 160 nulls rises run time to 156 132 ms with MySQL and to 203 140 ms with Neo4J.Reproducibility. Results obtained by our experiments are reproducible through the use of the benchmarks and implementation available in https://gitlab.com/jacques-chabin/UpdateChase.

		6,000													80,000
		5,000
															60,000
	Nb of queries	3,000 4,000													40,000	Nb of facts
		2,000
		1 • 10 5													20,000
		1,000
		0	0	500	1,000	1,500	2,000	2,500	3,000	3,500	4,000	4,500	5,000	5,500
		0	0	500	1,000	1,500	2,000	2,500	3,000	3,500	4,000	4,500	5,000	5,500	0
								Nb of nulls
				MySQL (INS)	MySQL (DEL)	Neo4J (INS)	Neo4J (DEL)	Number of facts
							(a) Number of queries per null
		14,000
															80,000
		12,000
		10,000													60,000
	Time [ms]	6,000 8,000													40,000	Nb of facts
		4,000
															20,000
		2,000
		0	0	500	1,000	1,500	2,000	2,500	3,000	3,500	4,000	4,500	5,000	5,500	0
								Nb of nulls
							Insert		Delete	Number of facts
							(b) Time per null for MySQL
				Figure 10: Benchmarks results of 540 scenarios, average over 10 runs

https://github.com/neo4j-graph-examples/movies

https://github.com/neo4j-graph-examples/graph-data-science

https://ldbcouncil.org/benchmarks/graphalytics/