viewed in SLG(O) as an oracle. In fact, every time SLG(O) **selects an atom, the**
oracle's inference engine may be called, in case the atom is not provable by the rules alone. Such a queried atom, say P(a**), might thus be provable in the ontology but** only if a certain set of atoms in turn is provable via rules. Our approach captures this by allowing the oracle to return a new rule, say P(a) ← Goals**, which has** the property that a (possibly empty) set Goals**, in addition to the axioms in the** ontology and the atoms already derived from the combined knowledge base, would be sufficient to prove P(a). SLG(O) **then treats these new rules just as if they were**
part of the knowledge base.

Note that getting these conditional answers does not endanger decidability (or tractability, if it is the case) of reasoning in the ontology alone. In fact, it is easy to conceive of a modification of a tableau-based inference engine for an ontology that is capable of returning these conditional answers and is decidable if the tableau algorithm is. Simply add all the atoms that are defined in the rules to the ontology, then proceed with the tableau as usual, but collect all those added facts that have been used in the proof. Under some assumptions on the complexity of the oracle, it is shown (in Section 5 along with some other properties) that SLG(O) **also retains**
the data complexity of MKNFW F .

The second element of our approach arises from the need to properly combine the classical negation usually appearing in the ontology language with **the nonmonotonic negation of rules. This problem, which is solved by the semantics**
of [Knorr et al. 2011], is similar to the issue of coherence **that arises when adding** classical (or strong) negation to logic programs [Gelfond and Lifschitz 1991; Pearce and Wagner 1990; Pereira and Alferes 1992]: the classical negation **must imply** negation by default. In our case, if the ontology entails that some atom A **is false,** then perforce the default negation not A **must hold as well. The derivation must**
accordingly be modified since the proof of not A **cannot simply rely on the failure**
of the proof of A **as it is usual in Logic Programming. For that purpose, an alternating fixpoint approach is used in the bottom-up construction defined in [Knorr**
et al. 2011], where two alternating fixpoint operators are applied to **two different** sets of rules. In each iteration step, the fixpoint construction alternates between deriving more true atoms, and more (default) false atoms; when deriving more true atoms, the original set of rules is used; when deriving more default false atoms, a transformed set of rules is used so that rules with head A are removed if ¬A **holds.** This ensures that not A **is derived (see Section 2.3 for details).**
Adapting the alternating fixpoint for the top-down derivation would **result in a**
procedure significantly different from the original SLG. So instead, **we transform** the original knowledge base to ensure coherence without the need **for alternating** between two sets of rules. This approach is simpler to understand as it is a more direct extension of SLG and separates the concerns of coherence from those of topdown derivation; in addition the transformational approach should **also facilitate**
implementations of SLG(O)**. Indeed, one can rely more directly on the existing**
implementations that follow closely SLG.3 **Accordingly, Section 3 defines the above**