Other Datalog Examples

In the previous section we saw how tabling can finitely process certain programs and queries for which Prolog would go into an infinite loop. Tabling can also drastically improve the efficiency of some terminating Prolog programs. Consider reachability in a DAG. Prolog will terminate, but it may retraverse the same subgraph over and over again.

Let's reconsider the mostly linear owes graph at the end of the previous chapter (shown in Figure 2.2) on which Prolog had exponential complexity. Consider evaluating the query avoids(andy,X) with the left-recursive tabled definition of transitive closure. The forest for this evaluation will again consist of a single tree, and that tree will be very flat, similar in form to the one of Figure 3.9. Thus tabled evaluation will take linear time. So this is an example in which Prolog (with its right recursive definition) will terminate, but take exponential time; XSB with the left-recursive definition and tabling will terminate in linear time.

The ``doubly-connected linear'' graph used here may seem unusual and specially chosen, but the characteristics of the graph that cause Prolog to be exponential are not that unusual. Many naturally occurring directed graphs have multiple paths to the same node, and this is what casues the problem for Prolog. [For example, consider a graph (generated by graph-base [#!graphbase!#]) that places 5-letter English words in a graph with an edge between two words if one can be obtained from the other by changing a single letter.... (get example from Juliana, and see how it works.)

Transitive closure is perhaps the most common example of a recursive query in Datalog, but other query forms can be encountered. Consider the definition of same_generation. Given binary relations up and down on nodes, define a binary relation on nodes that associates two nodes if one can be reached from the other by going n steps up and then n steps down, for some n. The program is:

same_generation(X,X).
same_generation(X,Y) :- 
    up(X,Z1),
    same_generation(Z1,Z2),
    down(Z2,Y).

The name of the predicate arises from the fact that if we let up be defined by a ``parent_of'' relation and down be defined by the ``child_of'' relation, then same_generation/2 defines people in the same generation.

[to be continued...]