Cf. the computation in Example 3.13, p(a), Q(a), and R(a**) are true in the sequence**
Pdω **while** p d(a), Q
d(a**), and** R
d(a**) are false in the sequence** Ndω
. The same results are derivable with a complete oracle. Q(a**) is derivable from the corresponding fact.** From that ¬R(a) is derivable and therefore not R
d(a**) as well. This allows us to**
obtain R(a). Now, Q(a) and R(a) together with O **are inconsistent from which we** can derive p(a), but also ¬Q(a) and ¬p(a). Consequently, not p d(a) and not Q
d(a)
hold as well, i.e., everything is supposedly true and false at the same time.

If we limit ourselves to the partial (consistent) oracle, then we no longer derive p(a), not Q(a), or not p(a). In this case, R(a**) is still true and false (inconsistent),** but Q(a) is true, and p(a**) is undefined.**
Thus, the usage of such a partial oracle partially hides MKNF-inconsistencies and demonstrates a somewhat paraconsistent behavior instead.

This example also shows why correctness of a partial oracle is only defined w.r.t. MKNF-consistent knowledge bases. For MKNF-inconsistent knowledge bases the derivation relation is not identical in general.

By making assumptions on the complexity and number of results of an **oracle,**
complexity results of SLG(O) **are obtained.**
Theorem 5.7 Let Kdbe a doubled Hybrid MKNF knowledge base, and pTO a correct partial oracle for O, such that for every goal S, the cardinality of pTO(IF **, S, L**)
is bound by a polynomial on the number of program atoms. Moreover, assume that computing each element of pTO is decidable with data complexity C**. Then, the**
SLG(O) evaluation of a query in Kd**is decidable with data complexity** P
C.

Proof. **Decidability is guaranteed by Theorem 5.1. As for complexity, first**
note that, given the polynomial data complexity of SLG [Chen and Warren 1996],
SLG(O) **without calls to the oracle is of polynomial data complexity as well. Considering the oracle, since the cardinality of** pTO(IFn
, S, L**) is bound by a polynomial,**
and each of the calls to the oracle can be seen as adding a new program rule (the result of Oracle Resolution **operation), only polynomially many such rules are**
added. Hence, as such, the inclusion of oracle calls does not alter the the polynomial data complexity of SLG. Now, computing each such rule amounts **to a call**
to the oracle, which by hypothesis is decidable and with data complexity C**. So,**
the overall data complexity is PC**. Note that the doubling of the knowledge base**
does not affect that since the factor 2 is subsumed by the (at least) polynomial complexity.

In particular, Theorem 5.7 means that if the partial oracle is tractable, and produces only polynomial many results, then SLG(O) **is also tractable. Clearly,** for an ontology part of the knowledge base that is tractable, it is possible to come up with a correct partial oracle that is also tractable. Basically, all that needs to be done is to proceed with the usual entailment method, assuming **that all** program atoms hold, and collecting them for the oracle result. To guarantee that the number of solutions of the oracle is bound by a polynomial, and still **keeping** with correctness, might be a bit more difficult. It amounts to finding a **procedure** that returns less results, and at the same time does not damage the completeness proof (similar to that of Theorem 5.3). At least for the tractable case this is ACM Transactions on Computational Logic, Vol. V, No. N, September 2018.