Splitting and Updating Hybrid Knowledge Bases (Extended Version) 29 We will first prove the following claim: For evey I ∈ M and every J ∈ N there exists some K ∈ M ∩ N such that K[U] = I
[U]and K[P\U] = J
[P\U]. The reason this holds is that the sets U and (P \ U) are disjoint. Let's take some I ∈ M and some J ∈ N and let K = I
[U] ∪ J
[P\U] = { p ∈ I | pr(p) ⊆ U **} ∪ {** p ∈ J | pr(p) ⊆ P \ U } .

The following can now be derived:
K[U] = { p ∈ K | pr(p) ⊆ U }
= { p ∈ I | pr(p) ⊆ U **} ∪ {** p ∈ J | pr(p) ⊆ U ∩ (P \ U) }
= { p ∈ I | pr(p) ⊆ U } = I
[U]
K[P\U] = { p ∈ K | pr(p) ⊆ P \ U }
= { p ∈ I | pr(p) ⊆ U ∩ (P \ U) **} ∪ {** p ∈ J | pr(p) ⊆ P \ U } = { p ∈ J | pr(p) ⊆ P \ U } = J
[P\U].

Consequently, K must belong to M and also to N (because they are saturated relative to U and P \ U, respectively), so K also belongs to M ∩ N.

From the above it easily follows that M ∩ N is nonempty and that both (M ∩ N)
[U] =
M[U]and (M ∩ N)
[P\U] = N[P\U] hold as well.

It remains to show that M ∩ N is semi-saturated relative to U. Let I ∈ I be such that I
[U] belongs to (M ∩ N)
[U]and I
[P\U] belongs to (M ∩ N)
[P\U]. We need to prove that I
belongs to M ∩N. We know that (M ∩N)
[U]is a subset of M[U]and since M is saturated relative to U, we conclude that I belongs to M. Similarly, (M ∩ N)
[P\U]is a subset of N[P\U]and since N is saturated relative to P\U, we conclude that I belongs to N. Hence, I belongs to M ∩ N.

## Proposition 41

Let U be a set of predicate symbols and M, N ∈ M be such that M is semi-saturated relative to U. Then the following equivalences hold:
(1) M = N if and only if M ⊆ N and M[U] ⊇ N[U]and M[P\U] ⊇ N[P\U].

(2) M ( N if and only if M ⊆ N and either M[U] ( N[U] or M[P\U] ( N[P\U].

Proof

(1) The direct implication follows from Proposition 27(1). We will prove the converse implication. Suppose M[U] ⊇ N[U], M[P\U] ⊇ N[P\U]and I ∈ N. We immediately obtain I
[U] ∈ M[U]and I
[P\U] ∈ M[P\U]and since M is semi-saturated relative to U, we can conclude that I ∈ M.

(2) For the direct implication suppose that M ( N. Then there is some I ∈ N such that I /∈ M. Since M is semi-saturated relative to U, we obtain that I
[U] ∈/ M[U] or I
[P\U] ∈/ M[P\U]. Consequently, either M[U]is a proper subset of N[U] or M[P\U]
is a proper subset of N[P\U]. The converse implication is a cosequence of Proposition 27(3).
Proposition 42 Let U be a set of predicate symbols and M, N ∈ M be such that N is semi-saturated relative to U. Then: