Two remarks regarding the expressivity of EL+ **are in order. First, RIs allow**
expression of role hierarchies R ⊑ S, transitive roles using R ◦ R ⊑ R, rightidentity rules R ◦ S ⊑ S, and left-identity rules S ◦ R ⊑ S. Second, **disjointness**
of complex concept descriptions C, D (and unsatisfiability of a concept C**), can be** expressed by C ⊓ D ⊑⊥ **(resp.** C ⊑⊥).

## 2.2 Syntax Of Hybrid Mknf Knowledge Bases

Hybrid MKNF knowledge bases, as introduced in [Motik and Rosati 2010], are essentially formulas in the logics of minimal knowledge and negation as failure [Lifschitz 1991], i.e., first-order logics with equality and two modal operators, K and not**, allowing inspection of the knowledge base. At an intuitive level, given a** first-order formula ϕ, K ϕ asks whether ϕ **is known, i.e., true in all models of the**
related Hybrid MKNF knowledge base K, while notϕ **is used to check whether** ϕ is not known. Hybrid MKNF knowledge bases consist of two components, a decidable DL knowledge base translatable into a first-order logic, and a finite set of rules.

Definition 2.2 Let O be a DL knowledge base built over a language L with distinguished sets of countably infinitely many variables NV**, and finitely many individuals**
NI and predicates NP, where NC ∪ NR ⊆ NP. An atom P(t1, . . . , tn**), where** P ∈ NP
and ti ∈ NV ∪ NI, is called a DL-atom if P occurs in O, otherwise it is called nonDL-atom. An MKNF rule r has the following form where, for all i and j, H, Ai, and Bj **are atoms:**

## H ← A1, . . . , An, Not B1, . . . , Not Bm. (1)

H is called the (rule) head, and the sets {A1, . . . , An} and {not B1, . . .not Bm}
form the body of the rule. Literals are positive literals A or negative literals not B.

We abbreviate rules by H ← B, splitting B **into two sets** B
+ **(positive literals) and**
B
− (negative literals). A rule r is positive if m = 0 and a fact if n = m **= 0. A**
program P is a finite set of MKNF rules and called positive **if all its rules are positive.** A Hybrid MKNF knowledge base K is a pair (O,P). The **ground instantiation** of K is the KB KG = (O,PG) where PG is obtained from P **by replacing each rule** r of P with a set of rules substituting each variable in r with constants from K **in all**
possible ways.

In this definition and in the rest of the paper, we omit the modal operator K in rule heads and bodies.6 To ensure decidability, DL-safety is applied [Motik and Rosati 2010; Knorr et al.

2011]. Intuitively, DL-safety constrains the use of rules to individuals actually appearing in the knowledge base under consideration. Since, as indicated in the introduction, we are especially interested in querying the knowledge **base, care also** must be taken to impose DL-safety on (conjunctive) queries: