The problem of expressing and supporting classical greedy algorithms in Datalog has been the focus of many signicant research eorts that have produced very interesting solutions for particular algorithms. But we still lack a general treatment that characterizes the relationship of greedy algorithms to non-monotonic theories and leads to asymptotically optimal implementations. In this paper, we propose a general solution to this problem. Our approach begins by identifying a class of locally stratied programs that subsumes XY-stratied programs and is formally characterized using the Datalog 1S representation of numbers. Then, we propose a simple specialization of the iterated xpoint procedure that computes eciently the perfect model for these programs, achieving optimal asymptotic complexities for well-known greedy algorithms.This makes possible their ecient support in Datalog systems.
Due to the emergence of many important application areas, we are now
experiencing a major resurgence of interest in Datalog for parallel and distributed
programming
In the next section we recall the basic notions of local stratication, and
iterated xpoint, and then, in Section 3, we introduce a class of of programs that are
locally stratied by the temporal arguments of their predicates which subsumes
XY-stratied logic programs, and extend it by allowing more powerful logic
predicates expressing ‘ >’ and ‘+’ primitives needed for greedy algorithms. In Section 4,
therefore we show that these extended programs can be expanded into equivalent
XY-stratied programs via simple rewritings dened by the arithmetic functions
they use. While this rewriting denes the formal semantics of our greedy programs,
the equivalent programs produced by the rewriting would be very inecient if
implemented with the standard approach used for XY-stratied programs in systems
such as LDL++
Denition 1. A program P is locally stratied if it is possible to partition its Herbrand base BP into a countable number of subsets, called strata, B0; B1; : : : ; such that for every r 2 ground(P ) the stratum of the head of r is strictly higher that the strata of its negated goals, and higher or equal to the strata of its positive goals.
Each locally stratied program has a unique stable model, called its perfect
model, whereby its abstract semantics has many desirable properties
Then the iterated computation on our locally stratied program P is performed by starting from M0 = T0"!(;) and then continuing with MK+1 = T"K!(MK ).
While the iterated xpoint procedure seems to provide an ecient operational
semantics for computing of the perfect model for locally stratied program, in
reality this is not the case, because of a number of problems, including the fact that
the existence of local stratication for a given program represents an undecidable
question
To address these problems we will introduce the notion of programs that are locally stratied by the positive numbers that appear in a distinguished argument of their predicates, that we call temporal argument. Thus, we propose simple syntactic conditions that assures that (i) a local stratication exists and (ii) the actual strata are identied quite easily. We then turn to the issue of improving the eciency of the iterated xpoint procedure, by basically skipping over the computation of strata that do not produce any useful result. We will thus identify simple syntactic conditions that make this optimization possible, and we will show that greedy algorithms are naturally expressed under this restricted syntax, producing declarative Datalog programs that preserve the desirable complexity properties of their procedural counterparts.
Let us consider Datalog programs where the rst argument is a non-negative integer
represented by the successor notation: 0; s(0); s(1); : : : ; sn(0) described in
Thus the temporal argument in our int predicate is the last one, where a positive integer n is represented by n applications of the function symbol s to zero. We will use the short-hand sn(X) to denote the application of s to X repeated n times s(s(: : : s(X) : : :)).
Thus the Herbrand universe for the above program is fsn(0); sn(even)g where n denotes an arbitrary non-negative integer (under the convention that s0(X) = X, and thus s0(even) = even).
Now, let P be a Datalog1S program, then the temporal layering of P is the one obtained by assigning each atom in its Herbrand Base BP to the layer n whenever the last argument of the atom is sn(c), with c an arbitrary constant. For instance the temporal layering of the above program in Example 1 is as follows: Layer 0: int(sn(0); 0); int(sn(even); 0); int(sn(0); even); int(sn(even); even) 1: int(sn(0); s(0)); int(sn(even); s(0)); int(sn(0); s(even)); int(sn(even); s(even)) : : : k: int(sn(0); sk(0)); int(sn(even); sk(0)); int(sn(0); sk(even)); int(sn(even); sk(even)) We will focus on programs that are locally stratied according to their temporal layering: Denition 2 A Datalog1S program P will be said to be temporally stratied if P is locally stratied according to its temporal layering.
Thus the program in Example 1 is temporally stratied. However, the program in Example 2, below, it is not locally stratied, although it has the same Herbrand base, and can be assigned the same temporal layering as Example 1: Example 2 (A Temporally Layered Program that is not locally stratied ) int(even; 0): int(even; J) :int(even; s(J)): The simple programs so far considered only use one predicate, but to express powerful algorithms we need to consider programs featuring several predicates within each given layer. For these programs, deciding whether they are locally stratied, and determining the perfect model for those that are stratied, can be quite challenging in general. A solution is however at hand for the large class of such problems that satises the notion of XY-stratication discussed next.
Temporally stratied programs have been explored in the past. In particular,
The dierential xpoint (a.k.a. seminaive xpoint) of this program can be expressed by the following program, where dcl is the delta version of cl. Example 4 (Dierential rules used in computing the transitive closure of arc) dcl(X; Z; 0) dcl(X; Z; J1) arc(X; Z): dcl(X; Y; J); arc(Y; Z); J1 = J+1; :previous(X; Z; J): previous(X; Z; J1)
dcl(X; Z; J); J < J1:
The above program is a Datalog 1S program expressed by a slightly dierent notation
Example 5 (Dierential rules used in computing the transitive closure of dcl(X; Z; 0) arc(X; Z): dcl(X; Z; J1) dcl(X; Y; J); arc(Y; Z); J1 = J+1; :hdcl(X; Z; J): hdcl(X; Z; J) dcl(X; Z; J): hdcl(X; Z; J1) hdcl(X; Z; J); J1 = J+1
The resulting program is temporally stratied, i.e., locally stratied by the
temporal layering established by the last argument of its recursive predicates. Observe
that in the program above we only have two kinds of temporal arguments: J and
J+1 = J1, i.e., a variable and its immediate successors. For these programs there
is a simple test that allows us to determine if they are locally stratied. This is the
XY-stratication test that is performed by renaming the predicates in the recursive
rules that have a temporal argument, as follows: in each rule r rename with the
sux ‘_ old’ the goals having as temporal argument J when the temporal argument
in the head of r is J1 = J + 1. The program so obtained is called the bi-state version
of the original program. Then, a program P is said to be XY-stratied when its
bi-state version is stratied. XY-stratied programs are locally stratied and their
perfect model can be eciently computed using their bi-state version
dcl(X; Z; 0) arc(X; Z): dcl(X; Z; J1) dcl(X; Y; J); arc(Y; Z); J1 = J+1; :hdcl_old(X; Z; J): hdcl(X; Z; J) dcl(X; Z; J): hdcl(X; Z; J1) hdcl_old(X; Z; J); J1 = J+1: We have obtained a program that is stratied (e.g., with the following strata: 1:{arc}, 2:{dcl_old, hdcl_old}, 3:{dcl}, 4:{ hdcl}).
Therefore, XY-stratication provides a simple test to verify that temporally
layered programs are locally stratied and thus temporally stratied. As proven in
These steps repeated until (i) stops producing new tuples, construct the perfect model for our XY-stratied (and therefore temporally stratied) program. This basic procedure delivers good performance on many simple problems including the seminaive computation of the least xpoint of Example 2, above, but a more sophisticated approach is needed to achieve optimal performance for logic programs expressing greedy algorithms, since these are considerably more complex.
To simplify the expression, and also the compilation, of greedy algorithm, we will introduce the notation not(: : :). Thus, Example 4 can be re-expressed as follows:
dcl(X; Z; 0) arc(X; Z): dtrcl(X; Z; J1) dcl(X; Y; J); arc(Y; Z); J1 = J+1;
not(dcl(X; Z; K); K < J): In general, a program with a goal ‘ not(condition)’ should be viewed as the shorthand of the program derived by (i) replacing ‘ not(condition)’ with :newp(SVlist), (where SVlist denotes the variables shared between condition and the rest of the rule), and (ii) adding the rule: newp(SVlist) condition:
Suppose now that warc(X; Z; W) describes a directed graph where W is the positive weight of the arc from X to Z. For now, let us assume that all such weights are integers. Then, a greedy algorithm to nd the shortest path between node pairs is as follows: Example 8 (A greedy algorithm to nd shortest paths between node pairs ) wtc(X; Z; W) warc(X; Z; W): wtc(X; Z; Cz) wtc(X; Y; Cy); not(wtc(X; _; C); C < Cy);
warc(Y; Z; W); Cz = Cy + W: Thus in the recursive rule, we use the not construct to nd the shortest distance Cy from a node X to a node Y and, for each arc in warc(Y; Z; W), we add a path from X to Z of length Cz = Cy + W. Our objective is to re-express this as an equivalent XY-stratied program. In order to do that, we will re-write the program into the following one, where we re-express ‘+’ using the successor logic of Datalog 1S. Example 9 (A temporally stratied program to nd shortest paths between node pairs ) wtc(X; Z; W) succadd(X; Y; W; C1) succadd(X; Y; W; C1) wtc(X; Z; Cz) warc(X; Z; W): wtc(X; Y; Cy); not(wtc(X; _; C); C < Cy); warc(Y; Z; W1); W = W1 + 1; C1 = Cy + 1: succadd(X; Y; W + 1; C); C1 = C + 1: succadd(X; Y; 0; Cz): Thus recursive succadd rule expresses ‘+’ by raising by 1 the value of Cy while replacing W + 1 with W until this becomes zero: at this point the addition has been completed, whereby Cz is the distance of Z from X. We can now expand the not(:::) goal, and nally verify that the resulting program is XY-stratied, by the rst goals in the second and third rule as wtc_old and succadd_old, respectively. For the rules resulting from the expansion of not(:::) we proceed as in Example 4. Then we obtain a bistate program which is stratied: therefore the original program in Example 9 is XY-stratied and thus temporally stratied.
A program such as that in Example 9, where the rewriting of its <; +, and not goals produce a temporally stratied programs will be called an Implicit Temporally Stratied (ITS) program. Now, many programs expressing greedy algorithms can be transformed into XY-stratied programs that provide a formal semantics for such programs, since these are known to be locally stratied. The perfect model for these programs can also be computed using the standard bistate based computation of XY-stratied programs, but as discussed next, this computation would fail to deliver optimal performance for the program in Example 9 and other greedy programs.
The obvious problem with the standard bistate-based computation of the program in Example 9 is that in order to derive Cz = Cy + W, we go through the computation of the W 1 temporal strata that take us from Cy to Cz, even though no new wtc value might be produced in step (i) and in step (ii) of the Perfect Model Computation for XY-stratied programs discussed on page 5. In order to bypass this sequence, we might consider jumping directly to stratum with temporal argument Cz, but that might not be correct, since the same rule that has now produced Cz might have previously produced a value C0z, Cy < C0z < Cz, which must be considered before Cz. The solution to this problem is obvious: (1) we store the value Cz produced by the second rule into a priority queue (PQ) and then (2) we fetch (and remove) the least value from PQ, and use it as the next value of the temporal argument. Needless to say, our PQ is exactly the data structure used in Dijkstra’s shortest path algorithm and other greedy algorithms. Thus we can achieve an optimal computation of our greedy algorithms by simply replacing the +1 successor operation with a PQ store+fetch operation.
This PQ optimization however it is is not applicable to all temporally stratied programs and in particular to Example 1, due to the fact that the only goal in its rules is a negated goal. To avoid this potential problem we now introduce the notion of Strict Implicit Temporally Stratied (SITS) that assures the applicability of the PQ optimization.
Denition 3 An ITS program will be said to be strict when every rule containing negated goals also contains some positive goal which has a temporal argument that is than the temporal argument of every negated goal.
Thus this condition excludes the program in Example 1, and also disallows the following rule that satises the standard notion of implicit temporal stratication: wtc(X; Z; Cz) wtc(X; Y; Cy); arc(Y; Z; W); Cz = Cy + W;
not(wtc(X; _; C); C < Cz): The problem with this rule is that it oers no assurance that Cy C. A rule like the one above is no problem for the iterated xpoint procedure that visits every successive value of the temporal argument, but it cannot be supported in a computation that jumps from the current temporal argument to the next temporal value extracted from PQ. However teh strictness condition solves this problem and maket it possible to use the following computation:
Computation of Perfect Model for SITS Programs 1: Initialize the priority queue (PQ) to empty. 2: Let M := T0"!(;) 3: Add the values of temporal arguments generated in step 2 to PQ. 4: Repeat the following three steps until PQ becomes empty: 5: Remove the least temporal argument K from (PQ) and 6: Let M := T"K!(M ).
7: Add the values of the newly generated temporal arguments to PQ.
Thefore, SITS programs can be computed eciently by a simple optimization of the iterated xpoint algorithm that consists of skipping over unproductive values of temporal arguments:
In our discussion so far, we have assumed that temporal arguments are positive
integers, but our treatment of greedy algorithms generalizes to the case in which
we have arbitrary positive numbers, not just integers, whereby arbitrary positive
weights can, e.g., be used as arc weights in our graphs. This conclusion follows
from the argument presented in
Using oating-point numbers and real arithmetic, we can now express a
cornucopia of greedy algorithms, starting with the single-source Dijkstra algorithm shown
below.
Since, ecient Datalog implementations, such as DeALS
Given an undirected graph, g(X; Y; Cxy), the exit rule selects an arbitrary node X, from which to start the search. Then, the second rule selects candidate new nodes, using the conditions Y<>a, and not(tspath(_; Y; C1); C1 < C) ensures that we do not cycle back to the initial node ad previously derived nodes.
Finally the third rule selects from the candidate new nodes cand(Y; C) the one that has the shortest distance from a.
tspath(a; 0) node(a): cand(Y; C) tspath(X; Cx); g(X; Y; Cxy); Y<>a;
not(tspath(Y; C1); C1 < C); C = Cx + Cxy:
tspath(Y; C) cand(Y; C); not(cand(_; C1); C1 C):
Thus, this algorithm will work correctly under the assumption that there are no ties,
i.e., no two arcs departing from the same node have the same weight. In the situation
where there are ties, we can employ a construct such as choice
C): This program is SITS once we assume that the min aggregate is dened as follows: mtspath(Y; C) tspath(Y; C) cand(Y; C); not(cand(_; C1); C1 < C): mtspath(Y; C); not(mtspath(Y; C1); C1 < C): Here the intra-layer stratication uses cand al the rst level, and mtspath at the second level, and tspath at the top level. Thus, while the body of the second rule eliminates the nodes having a smaller C, the aggregate in the head only retains the rst (i.e., the smallest) Y out of those candidate nodes that share the same C.
While the use of min or max aggregates could be all a user wants in most practical applications, from a conceptual viewpoint we might regret the fact that we have given up non-determinism, and we can only generate one TSP path rather than a dierent one at each run. However, non-determinism can be recovered by a builtin predicate, such a hash function h(_), that reorders its input nondeterministically. Then our program becomes: Example 13 (Using randomized hashing for non-determinstic TSP ) tspath(a; 0) node(a): cand(Y; C) tspath(X; Cx); g(X; Y; Cxy);
Y<>a; not(tspath(Y; C1); C1 < C); C = Cx + Cxy: slct(SL; C) cand(Y; C); not(cand(_; C1); C1 C); tspath(L; C) slct(L; C); not(slct(L1; C); h(L) > h(L1)): Here the the intra-layer stratication has cand below slct which is below tspath. Similar techniques for breaking ties can be used in Prim’s and other algorithms.
We build a tree with nodes st(X; Cx) where C is a node and Cx is the cost of the tree when X was produced. We start from a node a with cost 0. Then for the current level C, we nd all the new nodes reachable from this or previous nodes. This provides a set of candidates for which, in the third rule, we take the one that delivers the least cost.
Example 14 (Prim’s minimum cost spanning tree. ) st(a; 0): cand(C1; Y) st(C1; Y) st(C; _); st(Cx; X); Cx C; arc(X; Y; Cxy); Y <> a; not(st(Cy; Y); Cy < C); C1 = C + Cxy: cand(C1; Y); not(cand(C; _); C < C1):
Our example assumes that no two arcs have the same weight. When this is not the case, we will use the same tie-breaking solutions used for TSP.
Human coding is a lossless data compression algorithm. The idea is to assign variable-length codes to input characters, with lengths of the assigned codes based on the frequencies of corresponding characters. Frequent characters are assigned shorter codes. The variable-length prex codes are bit sequences assigned to input characters in such a way that no code of a character is the prex of the code of another character.
The input is the list of unique characters along with their frequency of occurrences and output is the Human tree. The basic algorithm is as follows. We start from a set of facts, token(Char; Freq) which corresponds to the leaf nodes of the Human tree. Then the algorithm can be expressed as follows:
huf(F; X; 0; 0) token(X; F): huf(H; nil; H1; H2) huf(H1; _; _; _); not(huf(H11; _; _; _); H11 < H1); huf(H2; _; _; _); H1 < H2; not(huf(H22; _; _; _); H22 < H2);
H22<>H1; H = H1 + H2: For instance, say that we have three facts: token(a, 4). token(b, 5). token (c,10). Then the rst step consists in executing the rules whose body layer is 0: these are the exit rules, since their bodies consists of facts, which are always viewed as belonging to zero layer. This produces the following leaf nodes in our tree (identied by the fact that their left and right subtrees are both 0).
huf(4; a; 0; 0):
huf(5; b; 0; 0): huf(10; c; 0; 0) Also as a result of this step, we have that the values 4, 5, and 10 are entered into the priority PQ. Now, the system takes the least of these values and evaluates the rules for that layer. The rules produce nothing at layer 4, so we move to next layer, 5 where the second rule produces:
huf(9; nil; 4; 5) Thus the system has extracted two nodes with the minimum frequency from the min heap and generated a new node whose weight is the sum of those two.
At this point we have only 9 in the PQ, and where no node at level below 9 is still free the evaluation of the second rule produces nothing, but removes 9 from the PQ. The next value in the PQ is thus 10, and the evaluation of our rule at level 10 produces:
huf(19; nil; 9; 10) At this point, the evaluation at layer 19 produces no new value, whereby the PQ becomes empty, and the computation terminates.
Kruskal’s algorithm also constructs a minimum spanning tree for a connected weighted unordered graph. Thus an edge of a graph is represented by a fact edge(A; B; W) where A < B. At each step, the algorithm selects a least-cost edge among those that do not connect previously connected nodes. Thus, in the example below, the rst two rules state that each node is connected to itself, starting at level 0. Then, say that at level C we add the new edge tree(X; Y; C), connecting two nodes which, until level C were still disconnected.
Then, the last rule is executed that determines all the nodes X1 and Y1 respectively connected with X and Y. Thus, we dene mM(X; Y; X; Y) mM(X; Y; Y; X)
X < Y: X > Y: then we see that mM(X1; Y1; S; L) it returns S and L as respectively the smaller and larger of these two. Then we connect to S all the nodes previously connected to L, i.e., the Ln nodes in the last rule.
Example 16 (Kruskal’s Algorithm ) connt(X; X; 0) connt(Y; Y; 0) tree(X; Y; C) connt(S; Ln; C) edge(X; Y): edge(X; Y): tree(_; _; C); edge(X; Y; Cxy); not(connt(X; Y; C1); C1 < C); C = Clast + Cxy: tree(X; Y; C); connt(X1; X; C); connt(Y; Y1; C); mM(X1; Y1; S; L); connt(L; Ln; C):
Unlike our previous algorithms, the performance of Kruskal’s under our formulation cannot be guaranteed to be optimal, since connectivity is not supported by the special union-nd data structure.
The non-monotonic constructs proposed in this paper introduce a simple declarative
extension for deductive databases that greatly enhances their eectiveness in a range
of applications and thus achieves the same optimal time complexity of procedural
code algorithmsassuming that these do not make use of special data structures
such as Union-Find used by Kruskal’s minimum spanning tree algorithm. In fact, we
have shown that the greedy optimizations of procedural algorithms follow directly
from the need to achieve an ecient implementation for the iterated xpoint
procedure of locally stratied programs. From a theoretical viewpoint, this reveals the
computational upside of non-monotonic semantics classes that in the past were
primarily analyzed for their intractability downside. From a practical viewpoint, these
results allow us to express and implement eciently in Datalog systems
signicant algorithms expressed in declarative logic, while achieving the same asymptotic
complexity as their procedural counterparts. Indeed, support for strict local
stratication can be easily achieved through extensions of XY-stratication, which is now
part of DeALS
The author would like to thank Alex Shkapsky, Mohan Yang, and the referees for many suggested improvements.