Logic Program

A collection of Horn Clauses is called a Logic Program. Variable appeared in the body may be regarded as quantified existentially within the body, while other variables are universally quantified over the entire rule [22]. For example the following clause:

$$parent(X,Z) \wedge{} parent(Y,Z) \wedge{} \neq(X,Y) \rightarrow sibling(X,Y)$$

may be read as:

``for all $X$ and $Y$, $X$ is a sibling of $Y$, if there exists $Z$ such that $Z$ is a parent of both $X$ and $Y$, and $X$ and $Y$ are not the same individual.''

The variables may be universally quantified, which is also correct[22]. Then, the above rule will be read as:

``for all $X$, $Y$ and $Z$, if $Z$ is a parent of both $X$ and $Y$, and $X$ is not $Y$, then $X$ is a sibling of $Y$.''

Datalog introduces some built-in predicates as: $=$, $\neq$, $>$, $<$ etc. They can be written in the usual infix notation as: $A>B$, or as an atomic formula: $>{}(A,B)$.

Predicates in a Logic Program depend on one another. Rules describing family relationships are given in Figure 4.1. There are intensional relations provided by predicates: $sibling$, $cousin$, and $related$.

Siblings are persons with a common parent, but one may not be his own sibling (rule number $1$). Cousins are people with a common ancestor who is the same number of generations away from each and at least two generations (rules number $2$ and $3$). Rules $4$-$6$ define $X$ and $Y$ to be related if they have a common ancestor.

Figure 4.1: Example Logic Program

$sibling/2$ depends on facts represented by $parent/2$. $cousin/2$ depends on facts represented by $parent/2$ and rules defined by $sibling/2$, and by itself (third rule). Similarly $related/2$ depends on $sibling/2$, $parent/2$ and itself. There are recursive definitions for $cousin/2$ and $related/2$.

To visualize dependencies among predicates so-called Dependency Graph [22] can be drawn. Its nodes are predicates, and arcs represent relationships. If there is a rule with a subgoal whose predicate is $p$, and with a head whose predicate is $q$, there is an arc from predicate $p$ to $q$. There are no nodes for built-in predicates (like $\neq$).

A Logic Program is recursive if its Dependency Graph has one or more cycles. The dependency graph for the example in Figure 4.1, is given in Figure 4.2. There are two cycles: one involving predicate $related/2$ and the other $cousin/2$. Thus, these predicates are recursive and the predicates: $parent/2$ and $sibling/2$ are non-recursive.

Figure 4.2: Dependency Graph for Figure 4.1