Hybrid MKNF Knowledge Bases. A hybrid knowledge base is a pair hO,Pi where O is an ontology and P is a generalised logic program. The semantics is assigned to a hybrid knowledge base using a translation function π that translates both ontology axioms and rules into MKNF sentences. For any ontology O, ground atom p, set of literals B, rule r, program P and hybrid knowledge base K = hO,Pi, we define: π(O) =
{ K ζ (φ) | φ **∈ O }**, π(p) = K p, π(∼p) = not p, π(B) = { π(L) | L ∈ B }, π(r) =
(π(H(r)) ⊂Vπ(B(r))), π(P) = { π(r) | r **∈ P }** and π(K) = π(O)∪π(P). An MKNF
interpretation M is an *S5 (MKNF) model of* K if M is an S5 (MKNF) model of π(K).

As was shown in (Lifschitz 1991), the MKNF semantics generalises the stable model semantics for logic programs (Gelfond and Lifschitz 1988) - for every logic program P, the stable models of P directly correspond to MKNF models of π(P).

Classical Updates. As a basis for our update operator, we adopt an update semantics called the *minimal change update semantics* (Winslett 1990) for updating first-order theories. This update semantics offers a simple realisation of atom inertia, satisfies all Katsuno and Mendelzon's postulates for belief update (Katsuno and Mendelzon 1991), and it has successfully been used to deal with ABox updates (Liu et al. 2006; Giacomo et al. 2006).

A notion of closeness between interpretations w.r.t. a fixed interpretation I is used to determine the result of an update. This closeness is based on the set of ground atoms that are interpreted differently than in I. For a predicate symbol P and an interpretation I, we denote the set { p ∈ I | pr(p) = { P } } by I
[P ]. Given interpretations I, J, J
′, the difference in the interpretation of P between I and J, written diff (**P, I, J**), is the set
(I
[P ]\J
[P ])∪(J
[P ]\I
[P ]). We say that J is at least as close to I as J
′, denoted by J ≤I J
′,
if for every predicate symbol P it holds that diff (**P, I, J**) is a subset of diff (**P, I, J**′). We also say that J is closer to I *than* J
′, denoted by J <I J
′, if J ≤I J
′and not J
′ ≤I J.

The minimal change update semantics then keeps those models of the updating theory that are the closest w.r.t. the relation ≤I to some model I of the original theory. Given an interpretation I, sets of interpretations M, N, and first-order theories T , U, we define:
I ⊕ N = { J ∈ N | ¬(∃J
′ ∈ N)(J
′ <I J) }, M ⊕ N =SI∈M(I ⊕ N), and mod(T ⊕
U) = mod(T ) ⊕ mod(U). If mod(**T ⊕ U**) is nonempty, we say it is the minimal change update model of **T ⊕ U**. This notion can be naturally generalised to allow for sequences of updates. Formally, given a finite sequence of first-order theories U = hUiii<n, we define mod(U) = (**· · ·**((mod(U0) ⊕ mod(U1)) ⊕ mod(U2)) **⊕ · · ·**) ⊕ mod(Un−1). If mod(U) is nonempty, we say it is the *minimal change update model of* U.

Rule Updates. There exists a variety of different approaches to rule change (Leite and Pereira 1997; Alferes et al. 2000; Eiter et al. 2002; Sakama and Inoue 2003; Alferes et al. 2005; Zhang 2006; Osorio and Cuevas 2007; Delgrande et al. 2007; Delgrande et al. 2008; Slota and Leite 2010a).

The more recent, purely semantic approaches (Delgrande et al. 2008; Slota and Leite 2010a)
are closely related to classical update operators such as Winslett's operator presented above. However, as indicated in (Slota and Leite 2010a), their main disadvantage is that they violate the property of support that lies at the very heart of semantics of logic programs. Out of the approaches that do respect support, only the rule update semantics presented in (Alferes et al. 2005; Zhang 2006) possess another important property: immunity to tautological and cyclic updates. We henceforth adopt the approach taken in
(Alferes et al. 2005) because, unlike in (Zhang 2006), it can be applied to any initial pro-