## 2 Related Work  
Prolog is based on first-order logic, which is a formalism to represent knowledge by logic formulas. The syntax of first-order logic includes logical symbols such as universal and existential quantifiers, variables, predicates, conjunctions, disjunctions and implications [13]. For example, the following first-order logic modeling represents that several humans are drivers: \(\exists\)X (human(X) \(\wedge\) driver(X)). The following expression models that in every country X, there is an inhabitant Y who lives in X: \(\forall\)X((\(\exists\)Y human(Y) \(\wedge\) live_in(Y, X)) \(\leftarrow\) country(X)). To make a parallel with the field of databases, Prolog can be used to model both data and the rules to reason with them. As with relational databases, it is based on the closed-world assumption that draws negative conclusions in the case of a lack of positive information [14]. The absence of information in a logic program implies that this information is false. Prolog allows a logic program to be defined by one or several rules, e.g., a0 \(\leftarrow\) a1 \(\wedge\)... \(\wedge\) an. As reminded in [14], this type of rule is equivalent to a0 \(\vee\) -a1 \(\vee\)... \(\vee\) -an, where a0,..., an are formulas. All variables in a formula are universally quantified over the whole formula; the atomic formula a0 is the head of the clause. For example, in the context of databases, ai can be _relation_(t1,..., t\(\
eq\)), where each t is a constant or a variable. A clause with an empty body and without variables can be viewed as a tuple of a relational database. A query q (i.e., a goal) can be written as \(\leftarrow\) b1,..., bm. The logical meaning of a query can be explained by referring to the equivalent universally quantified formula [14]: \(\forall\)X1... \(\forall\)Xn \(\
eg\)(b1 \(\wedge\)... \(\wedge\) bm), where Xi is the variable that occurs in (b1 \(\wedge\)... \(\wedge\) bm). It is equivalent to \(\
eg\exists\)X1... \(\exists\)Xn (b1 \(\wedge\)... \(\wedge\) bm). For query processing, Prolog implements a top-down evaluation of the rules. Intuitively speaking, to process a query Q, the system tries to unify each b\(i\) with the head of the rules a0 \(\leftarrow\) a1 \(\wedge\)... \(\wedge\) an. If this unification is possible, a variable instantiation is propagated into the body of the rules. One subquery (i.e., a subgoal) proceeds for each ai in a1,..., an in a left to right order. A query succeeds for a given variable instantiation depending on whether the unification succeeds. For example, suppose the following Prolog program:  
p(V) :- s(V), t(V). s(a). s(b). t(b). V is a variable; a and b are constant. :- is the implication \(\leftarrow\). The query p(X) will return p(b) as the result, as it is the only case where a variable unification succeeds. Figure 1 shows the Prolog evaluation tree of the query for the variable instantiation X = V = a. This instantiation fails because t(a) is not in the program (and this information cannot be deduced from the program by reasoning). Consequently, p(a) \(\leftarrow\) s(a), t(a) fails. In the closed-world assumption, the absence of information implies it is false. The rule body is evaluated in a left to right order: s(X), then t(X). Figure 2 shows that p(b) \(\leftarrow\) s(b), t(b) succeeds. Thus, p(b) is the result of the query. Prolog allows the definition of recursive rules (containing the same predicates in the head and the body of the rules). This mechanism can easily be exploited to calculate the transitive closure in a graph. The following rules define the transitive closure in a directed graph (see the example in [15]):  
connected(N,N).connected(N1,N2):-edge(N1,L),connected(L,N2). We considered that the direct links between the different vertices of the graph were modeled by the \"edge\" predicate; for example: edge(a,b). ; edge(b,c). ; and edge(a,e). The \"connected\" predicate could be used to determine the transitive closure. The query \"connected(X,Y)\" would compute all the results.