for a large class of programs (cf. [Chen and Warren 1996]). At the same time it has motivated the design of modern tabling engines, and captures many aspects of their behavior. When SLG is extended with an oracle in SLG(O)**, several of** the definitions of SLG are affected. In this section we present the definitions of SLG(O)**, as well as defining when an oracle is suitable for use in an evaluation. As** the SLG(O) **definitions are presented, we make clear how they differ from those**
of SLG. For the definition of SLG(O)**, we follow and extend the model of [Swift**
1999].

Briefly, an SLG(O) **evaluation is a sequence of forests (sets) of program trees.**
Program trees themselves correspond to subgoals that have been encountered in an evaluation. The nodes in these trees contain sets of literals divided into those literals that have not been examined, and others that have been examined, but their resolution delayed (cf. Definition 4.2). The need to delay some literals **arises for the** following reason. Modern Prolog engines rely on a fixed order for selecting literals in a rule, e.g., always left-to-right. However, well-founded computations cannot be performed using a fixed-order literal selection function.9 Hence, in **SLG(**O)
the delay **operation may postpone evaluation of some literals, which may be later**
resolved through an operation called simplification**. In addition to modeling the**
operational behavior of Prolog, the use of delay and simplification supports the termination and complexity results of SLG(O) **discussed in Section 5, analogous** to those presented for SLG in [Chen and Warren 1996].

Example 4.1 To ease the understanding of SLG(O), we present a concrete example of an SLG(O) **evaluation that does not use an oracle. Consider the following**
Hybrid MKNF knowledge base K **with empty** O.

p(b) ← (2)

$\mathbf{p(c)\leftarrow not\,p(a)}$  $\mathbf{p(X)\leftarrow t(X,Y,Z),not\,p(Y),not\,p(Z)}$  $\mathbf{p(a)\leftarrow p(b),p(a)}$  $\mathbf{t(a,a,b)\leftarrow}$  $\mathbf{t(a,b,a)\leftarrow}$

$\pi$). 
We consider the query p(c) to K **in which none of the atoms is a DL-atom, i.e.,** no oracle needs to be used. The SLG(O) **forest at the end of this evaluation is**
shown in Figure 1 where each node is labeled with a number indicating the **order** in which it was created in the SLG(O) **evaluation. Nodes consist of either the**
symbol fail**, or of a head representing the bindings made to an atomic subgoal**
and a body with a set of Delays, followed by the | symbol, followed by Goals **that** are still to be examined. The evaluation begins by creating a tree for **the initial** query with root p(c)← |p(c) **in node 1. Children of root nodes are created via the**
operation Program Clause Resolution **just as in the SLD resolution of Prolog.**
9**A literal selection function is employed to choose the next literal to resolve in the body of a rule.**
In SLG(O)**, the only requirement for a selection function is that DL-atoms are not selected until** they are ground, which is always possible given DL-safety of **conjunctive queries and the rules** appearing in the knowledge base (cf. Definition 2.3).

ACM Transactions on Computational Logic, Vol. V, No. N, September 2018.