
| Name                         | Syntax                                    | Semantics                                        |
|------------------------------|-------------------------------------------|--------------------------------------------------|
| top                          | ⊤                                         | ∆I                                               |
| bottom                       | ⊥                                         | ∅                                                |
| negation                     | ¬C                                        | ∆I \ CI                                          |
| conjunction                  | C ⊓ D                                     | CI ∩ DI                                          |
| disjunction                  | C ⊔ D                                     | CI ∪ DI                                          |
| existential restriction ∃R.C | {x ∈ ∆I | ∃y ∈ ∆I : (x, y) ∈ RI ∧ y ∈ CI} |                                                  |
| value restriction            | ∀R.C                                      | {x ∈ ∆I | ∀y ∈ ∆I : (x, y) ∈ RI implies y ∈ CI } |
| GCI                          | C ⊑ D                                     | CI ⊆ DI                                          |
| RI                           | R1 ◦ · · · ◦ Rk ⊑ R                       | RI ◦ · · · ◦ RI k ⊑ RI 1                         |
| concept assertion            | C(a)                                      | a I ∈ CI I , bI ) ∈ RI                           |
| role assertion               | R(a, b)                                   | (a                                               |

Table I. Syntax and semantics of ALC **with role inclusions.**
A DL ABox A is a finite set of concept assertions **for concept descriptions** C
and role assertions for role names R **whose syntax can be found in the lower part**
of Table I. ABoxes are used to describe a snapshot or state of the **world. An**
interpretation I is a model of an ABox A **if, for each concept assertion and role** assertion in A**, the conditions given in the third column of Table I are satisfied.**
A DL knowledge base O consists of a DL TBox T and a DL ABox A**, and** I is a model of O if it is a model of both T and A.

One of the main inference problems in DLs, actually the one considered in [Baader et al. 2005] for EL++, is subsumption. Given two DL**-concept descriptions** C, D
we say that C is subsumed by D w.r.t. the TBox T (C ⊑T D**) iff** C
I ⊆ DIfor all models I of T . In addition, we recall the instance problem **since, as we will** see below, it is the reasoning task we are interested in when answering top-down queries in our system combining rules and an oracle to an ontology. An **individual** name a is an instance of a concept C in ABox A **w.r.t. a TBox** T if a I ∈ C
Ifor every common model I of A and T **. Definition 2.1 extends the instance problem** to instances of roles, a non-standard reasoning task.

Definition 2.1 A pair of individuals (a, b) is an instance of a role R **in ABox** A
w.r.t. a TBox T **if (**a I, bI) ∈ RIfor every common model I of A and T .

The above definition will be useful, since in the oracle we define queries **for instances** of roles, i.e., binary predicates, as well as concepts.

2.1.1 EL+. The tractable DL EL+ is a large fragment5 of the DL EL++ **[Baader**
et al. 2005]. It is obtained by restricting the allowed concept constructors to ⊤, ⊥,
¬, ⊓, and ∃**, i.e., negations, disjunctions, and value restrictions are not allowed. All**
the remaining notions, in particular the semantics, carries over from the general case.