=Paper=
{{Paper
|id=Vol-1433/tc_91
|storemode=property
|title=Expressing and Supporting Efficiently Greedy Algorithms as Locally Stratified Logic Programs
|pdfUrl=https://ceur-ws.org/Vol-1433/tc_91.pdf
|volume=Vol-1433
|dblpUrl=https://dblp.org/rec/conf/iclp/Zaniolo15
}}
==Expressing and Supporting Efficiently Greedy Algorithms as Locally Stratified Logic Programs==
https://ceur-ws.org/Vol-1433/tc_91.pdf
Technical Communications of ICLP 2015. Copyright with the Authors. 1
Expressing and Supporting E ciently Greedy
Algorithms as Locally Strati ed Logic Programs
CARLO ZANIOLO
University of California, Los Angeles
E-mail: zaniolo@cs.ucla.edu
submitted 29 April 2015; accepted 5 June 2015
Abstract
The problem of expressing and supporting classical greedy algorithms in Datalog has been
the focus of many signi cant 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 strati ed programs that subsumes
XY-strati ed programs and is formally characterized using the Datalog1S representation of
numbers. Then, we propose a simple specialization of the iterated xpoint procedure that
computes e ciently the perfect model for these programs, achieving optimal asymptotic
complexities for well-known greedy algorithms.This makes possible their e cient support
in Datalog systems.
KEYWORDS: Horn Clauses, Datalog, Aggregates, Greedy Algorithms.
1 Introduction
Due to the emergence of many important application areas, we are now experi-
encing a major resurgence of interest in Datalog for parallel and distributed pro-
gramming (Hellerstein 2010; Abiteboul et al. 2011) (Gottlob et al. 2011; Abite-
boul et al. 2011). This include exploring parallel execution of recursive queries in
the MapReduce framework (Afrati et al. 2011) and on multicore machines (Yang
et al. 2015), and in Data Stream Management Systems (Zaniolo 2011). The abun-
dance of new applications underscores the need to tackle and solve crucial Datalog
problems that have remained open for a long timstarting with algorithms that
require aggregates in recursive rules that provided the subject of much previous
work (Zaniolo et al. 1997; Greco and Zaniolo 2001a; Mumick et al. 1990; Kolaitis
1991; Mumick and Shmueli 1995; Ross and Sagiv 1997). In this context, a major
step forward was accomplished recently with the introduction of monotonic aggre-
gates (Mazuran et al. 2013; Shkapsky et al. 2013). Monotonic aggregates, however,
cannot address the problem of formulating and supporting e ciently greedy al-
gorithms, a di cult challenge that provided the focus of much previous research,
including (Greco et al. 1992; Greco and Zaniolo 1998; Greco and Zaniolo 2001b).
Their work provided a stable-model characterization for speci c greedy algorithms
but did not develop a general theory and e cient solutions for such programs. In
this paper, we achieve a general solution by showing that greedy algorithms can be
2 Carlo Zaniolo
expressed quite naturally as locally strati ed programs that are conducive to a very
e cient implementationi.e., one having the same asymptotic complexity as that
achievable using procedural languages and specialized data structures. This is a
very encouraging result, given that optimal performance is not easily achievable for
algorithms expressed in the concise and elegant formalism of declarative logic, i.e.,
without having to specify detailed operational steps and special data structures in
many pages of procedural code. Furthermore, many intractability results obtained
for locally strati ed logic programs (Palopoli 1992) underscore the di culty of us-
ing them to express and support low-complexity algorithms. But in this paper we
show that there is a natural correspondence between greedy algorithm and a special
subclass of locally strati ed programs, which we will call strictly strati ed temporal
programs, that overcome these di culties.
In the next section we recall the basic notions of local strati cation, and iter-
ated xpoint, and then, in Section 3, we introduce a class of of programs that are
locally strati ed by the temporal arguments of their predicates which subsumes
XY-strati ed logic programs, and extend it by allowing more powerful logic predi-
cates expressing `>' and `+' primitives needed for greedy algorithms. In Section 4,
therefore we show that these extended programs can be expanded into equivalent
XY-strati ed programs via simple rewritings de ned by the arithmetic functions
they use. While this rewriting de nes the formal semantics of our greedy programs,
the equivalent programs produced by the rewriting would be very ine cient if im-
plemented with the standard approach used for XY-strati ed programs in systems
such as LDL (Arni et al. 2003) and DeALS (Shkapsky et al. 2013; Yang et al.
++
2015). Therefore, we propose a modi cation of the Iterated Fixpoint computation
that solves this problem and actually achieves asymptotic optimality in the imple-
mentation of many greedy algorithms, which are discussed in details in Section 5.
2 Local Strati cation and Iterated Fixpoint
Let us now recall the de nition of local strati cation for Datalog programs where
rules have negated goals:
De nition 1. A program P is locally strati ed 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 ∈ 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 strati ed program has a unique stable model, called its perfect
model, whereby its abstract semantics has many desirable properties (Przymusinski
1988). Moreover, once the aforementioned strati cation B , B , . . . is known for a
program P , then the Iterated Fixpoint procedure can be used to compute the perfect
0 1
model of P . The iterated xpoint can be de ned using the immediate-consequence
operator for the rules in ground(P ) whose head is in stratum B : let T denote
the immediate consequence operator for instantiated rules belonging to the K -th
K K
Greedy Algorithms as Locally Strati ed Logic Programs 3
stratum. and let T denote he in ationary version to this operator de ned as
T (I) =T (I) ∪ I .
K
Then the iterated computation on our locally strati ed program P is performed
K K
by starting from M = T (∅) and then continuing with M = T (M ).
↑ω ↑ω
While the iterated xpoint procedure seems to provide an e cient operational
0 0 K+1 K K
semantics for computing of the perfect model for locally strati ed program, in
reality this is not the case, because of a number of problems, including the fact that
the existence of local strati cation for a given program represents an undecidable
question (Palopoli 1992).
To address these problems we will introduce the notion of programs that are lo-
cally strati ed 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 strati cation exists and (ii) the actual strata
are identi ed quite easily. We then turn to the issue of improving the e ciency
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 syntac-
tic conditions that make this optimization possible, and we will show that greedy
algorithms are naturally expressed under this restricted syntax, producing declar-
ative Datalog programs that preserve the desirable complexity properties of their
procedural counterparts.
3 Temporally Strati ed Datalog1S Programs
Let us consider Datalog programs where the rst argument is a non-negative integer
represented by the successor notation: 0, s(0), s(1), . . . , s (0) described in (Chomicki
n
and Imielinski 1988). These are known as Datalog programs, and have been stud-
ied extensively in (Chomicki 1990), where the authors called the 1S argument the
1S
temporal argument, a naming convention that we will also follow in this paper. For
example consider the following program:
Example 1 (A Datalog program de ning all even positive integers.)
1S
int(even, 0).
int(even, s(J)) ← ¬int(even, J).
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 s (X) to denote the application of s to X repeated n times
n
s(s(. . . s(X) . . .)).
Thus the Herbrand universe for the above program is {s (0), s (even)} where n
n n
denotes an arbitrary non-negative integer (under the convention that s (X) = X, 0
and thus s (even) = even).
0
Now, let P be a Datalog program, then the temporal layering of P is the one
obtained by assigning each atom in its Herbrand Base B to the layer n whenever
1S
the last argument of the atom is s (c), with c an arbitrary constant. For instance
P
n
the temporal layering of the above program in Example 1 is as follows:
4 Carlo Zaniolo
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 strati ed according to their temporal
layering:
De nition 2 A Datalog program P will be said to be temporally strati ed if P
1S
is locally strati ed according to its temporal layering.
Thus the program in Example 1 is temporally strati ed. However, the program
in Example 2, below, it is not locally strati ed, 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 strati ed )
int(even, 0).
int(even, J) ← ¬int(even, s(J)).
The simple programs so far considered only use one predicate, but to express pow-
erful algorithms we need to consider programs featuring several predicates within
each given layer. For these programs, deciding whether they are locally strati ed,
and determining the perfect model for those that are strati ed, can be quite chal-
lenging in general. A solution is however at hand for the large class of such problems
that satis es the notion of XY-strati cation discussed next.
4 XY-Strati ed Programs
Temporally strati ed programs have been explored in the past. In particular, (Zan-
iolo et al. 1993) introduced XY-strati ed programs that are e ciently supported in
LDL ++
and DeALS (Shkapsky et al. 2013), (Yang et al. 2015) and were also used in
a number of advanced applications (Guzzo and Saccà 2005), (Borkar et al. 2012). A
generalized version of XY-strati cation, called explicitly strati ed logic programs
(Lausen et al. 1998), was then used to model active rules and other interesting
applications. Take for instance the transitive closure prgram for a graph:
Example 3 (Transitive Closure expressed in Datalog )
cl(X, Z) ← arc(X, Z).
cl(X, Z) ← cl(X, Y), arc(Y, Z).
The dierential xpoint (a.k.a. seminaive xpoint) of this program can be ex-
pressed 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) ← arc(X, Z).
dcl(X, Z, J1) ← dcl(X, Y, J), arc(Y, Z), J1 = J+1, ¬previous(X, Z, J).
previous(X, Z, J1) ← dcl(X, Z, J), J < J1.
Greedy Algorithms as Locally Strati ed Logic Programs 5
The above program is a Datalog program expressed by a slightly dierent notation
(Chomicki 1990). In fact, instead of representing the successor of integer J by s(J),
1S
we represent it here by J+1 where +1 is a post x function symbol. Therefore,
we can easily conclude that the program above is temporally layered by the last
argument (i.e., J and J1) in our predicates. However we cannot conclude that the
resulting program is locally strati ed, because the de nition of ground(P ) does not
prevent us from instantiating J < J1 to values where J is actually larger than J1.
This problem can be solved by a simple rewriting of the rules to explicitly de ne >
using the past values of dcl kept in lower strata, which we will write as hdcl (for
historical dcl).
Example 5 (Dierential rules used in computing the transitive closure of arc)
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 strati ed, i.e., locally strati ed by the tem-
poral 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 strati ed. This is the
XY-strati cation 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
su x `_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-strati ed when its
bi-state version is strati ed. XY-strati ed programs are locally strati ed and their
perfect model can be e ciently computed using their bi-state version (Zaniolo et al.
1993). For instance, the bi-state version of the program in Example 5 is as follows:
Example 6 (The Bistate Version of Example 5)
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 strati ed (e.g., with the following strata:1:{arc},
2:{dcl_old, hdcl_old}, 3:{dcl}, 4:{hdcl}).
Therefore, XY-strati cation provides a simple test to verify that temporally lay-
ered programs are locally strati ed and thus temporally strati ed. As proven in
(Zaniolo et al. 1993), the perfect model of these programs can be computed as
follows (for clarity we refer to predicates without the su x `_old' as `new'):
Perfect Model Computation for XY-strati ed Programs:
(i) use the bistate program to derive the values for the new predicates, and
(ii) re-initializing the values of the `_old' predicates with those of the
predicates just computed, and then the values of the `new' predicates.
6 Carlo Zaniolo
These steps repeated until (i) stops producing new tuples, construct the perfect
model for our XY-strati ed (and therefore temporally strati ed) program. This ba-
sic procedure delivers good performance on many simple problems including the
seminaive computation of the least xpoint of Example 2, above, but a more so-
phisticated 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:
Example 7 (Example 4 re-expressed using not( ) )
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 short-
hand 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.
5 Greedy Algorithms
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-strati ed 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 strati ed program to nd shortest paths between node pairs )
wtc(X, Z, W) ← warc(X, Z, W).
_
succadd(X, Y, W, C1) ← wtc(X, Y, Cy), not(wtc(X, , C), C < Cy),
warc(Y, Z, W1), W = W1 + 1, C1 = Cy + 1.
succadd(X, Y, W, C1) ← succadd(X, Y, W + 1, C), C1 = C + 1.
wtc(X, Z, Cz) ← 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-strati ed, by the rst goals
Greedy Algorithms as Locally Strati ed Logic Programs 7
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 strati ed: therefore the original program in
Example 9 is XY-strati ed and thus temporally strati ed.
A program such as that in Example 9, where the rewriting of its <, +, and not
goals produce a temporally strati ed programs will be called an Implicit Temporally
Strati ed (ITS) program. Now, many programs expressing greedy algorithms can be
transformed into XY-strati ed programs that provide a formal semantics for such
programs, since these are known to be locally strati ed. The perfect model for these
programs can also be computed using the standard bistate based computation of
XY-strati ed 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 pro-
gram 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-strati ed programs discussed on page 5. In order to
bypass this sequence, we might consider jumping directly to stratum with tempo-
ral argument Cz, but that might not be correct, since the same rule that has now
produced Cz might have previously produced a value C z, Cy < C z < Cz, which
0 0
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 strati ed
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 Strati ed (SITS) that assures the applicability
of the PQ optimization.
De nition 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 satis es the standard notion of implicit temporal strati cation:
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
8 Carlo Zaniolo
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:
Algorithm 1 Computation of Perfect Model for SITS Programs
1: Initialize the priority queue (PQ) to empty.
2: Let M := T (∅)
↑ω
3: Add the values of temporal arguments generated in step 2 to PQ.
0
4: Repeat the following three steps until PQ becomes empty:
5: Remove the least temporal argument K from (PQ) and
6: Let M := T (M ).
↑ω
7: Add the values of the newly generated temporal arguments to PQ.
K
Thefore, SITS programs can be computed e ciently by a simple optimization of
the iterated xpoint algorithm that consists of skipping over unproductive values
of temporal arguments:
5.1 Beyond Integers
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 (Mazuran et al. 2013) where it was observed that
non-integers could be represented as rational numbers sharing a common very large
denominator D whereby all computations can be emulated by integer arithmetics on
their numerators. Now the standard mantissa+exponent internal representation of
real and oating-point numbers, that is used in modern hardware/ rmware, does
exactly thatmodulo some round-o. For instance, for a decimal oating point.
the smallest value of exponent supported might be −95 (or smaller), whereby every
number can be viewed as the numerator over the denominator D = 10 . (For sim-
95
plicity, we have used a decimal base, but the same conclusions hold for other bases.)
Naturally, precision is limited by the fact that the mantissa is of nite length, and
thus, e.g., the operation of addition becomes a rounded-o addition. Rounded-o
addition can also be easily expressed in Datalog whereby the expanded resulting
program is still XY-strati ed, and the overall formal semantics remains valid. Of
1S
course, round-o is also a concern at the operational semantics level, where it can
be addressed by the use of double precision and other techniques used when algo-
rithms are expressed in procedural languages. Once he/she selects single or double
precision, our user is assured an e cient excution for greedy algorithms owing to
the fact that the implementation will not step through each successive oating point
number, but jumps directly the next number in the PQ.
Using oating-point numbers and real arithmetic, we can now express a cornu-
Greedy Algorithms as Locally Strati ed Logic Programs 9
copia of greedy algorithms, starting with the single-source Dijkstra algorithm shown
below.
Example 10 (Single source Dijistra's Algorithm )
wtc(X, W) ← warc(a, W).
wtc(Z, Cz) ← wtc(Y, Cy), not(wtc(Y, C), C < Cy),
warc(Y, Z, W), Cz = Cy + W.
Since, e cient Datalog implementations, such as DeALS (Shkapsky et al. 2013),
use Hashing and other indexing techniques to achieve a constant-time computation
of the recursive rule above for each value of Y, an optimal performance can be
expected for the Dijistra's algorithm above, and similar observations can be made
for the other greedy algorithms which which require not special data structure other
than PQ. In particular this is true for the Traveling Salesman's Program (TSP)
discussed next, which closely emulates its procedural counterpart, thus achieving
optimal asymptotic complexity.
Traveling Salesman's Greedy Heuristics
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.
Example 11 (Travelling Salesman's starting at node 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 (Greco et al. 1992),
which models don't care non-deterministic semantics via a special class of stable
models called choice models. Alternatively, we can fall back on the solutions used
by procedural programmers. For instance, since nodes are represented by natural
numbers, or by elements of an ordered domain, we can expand the third rule in
Example 11 as follows:
Example 12 (Extrema as tie-breaker: alternative for 3 rule in Example 11 )
rd
tspath(minhYi, C) ← cand(Y, C), not(cand(_, C1), C1 ≤ C).
This program is SITS once we assume that the min aggregate is de ned as follows:
mtspath(Y, C) ← cand(Y, C), not(cand(_, C1), C1 < C).
tspath(Y, C) ← mtspath(Y, C), not(mtspath(Y, C1), C1 < C).
10 Carlo Zaniolo
Here the intra-layer strati cation 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 strati cation has cand below slct which is below tspath.
Similar techniques for breaking ties can be used in Prim's and other algorithms.
Prim's algorithm
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(C, _), st(Cx, X), Cx ≤ C,
arc(X, Y, Cxy), Y <> a,
not(st(Cy, Y), Cy < C), C1 = C + Cxy.
st(C1, Y) ← _
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 Encoding
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 pre x codes are bit sequences assigned to input
characters in such a way that no code of a character is the pre x of the code of
another character.
The input is the list of unique characters along with their frequency of occurrences
Greedy Algorithms as Locally Strati ed Logic Programs 11
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:
Example 15 (Human Encoding Algorithm )
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
(identi ed 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
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 respec-
tively connected with X and Y. Thus, we de ne
mM(X, Y, X, Y) ← X < Y.
mM(X, Y, Y, X) ← X > Y.
12 Carlo Zaniolo
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) ← edge(X, Y).
connt(Y, Y, 0) ← edge(X, Y).
tree(X, Y, C) ← __
tree( , , C), edge(X, Y, Cxy), not(connt(X, Y, C1), C1 < C),
C = Clast + Cxy.
connt(S, Ln, C) ← 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 formu-
lation cannot be guaranteed to be optimal, since connectivity is not supported by
the special union- nd data structure.
6 Conclusion
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 e cient implementation for the iterated xpoint pro-
cedure of locally strati ed programs. From a theoretical viewpoint, this reveals the
computational upside of non-monotonic semantics classes that in the past were pri-
marily analyzed for their intractability downside. From a practical viewpoint, these
results allow us to express and implement e ciently in Datalog systems signi -
cant algorithms expressed in declarative logic, while achieving the same asymptotic
complexity as their procedural counterparts. Indeed, support for strict local strati -
cation can be easily achieved through extensions of XY-strati cation, which is now
part of DeALS (Shkapsky et al. 2013),(Yang et al. 2015). The integrated support of
monotonic aggregates in recursion, greedy algorithms, and XY-strati cation sup-
ported by our system entails a declarative expression and e cient implementation
of complex algorithms, and provides further evidence that this is indeed an age of
renaissance for Datalog and deductive databases.
Acknowledgements
The author would like to thank Alex Shkapsky, Mohan Yang, and the referees for
many suggested improvements.
Greedy Algorithms as Locally Strati ed Logic Programs 13
References
Abiteboul, S., Bienvenu, M., Galland, A., and Antoine, E. 2011. A rule-based
language for web data management. In PODS. 293304.
Afrati, F. N., Borkar, V. R., Carey, M. J., Polyzotis, N., and Ullman, J. D.
2011. Map-reduce extensions and recursive queries. In EDBT. 18.
Arni, F., Ong, K., Tsur, S., Wang, H., and Zaniolo, C. 2003. The deductive database
system ldl++. TPLP 3, 1, 6194.
Borkar, V. R., Bu, Y., Carey, M. J., Rosen, J., Polyzotis, N., Condie, T.,
Weimer, M., and Ramakrishnan, R. 2012. Declarative systems for large-scale ma-
chine learning. IEEE Data Eng. Bull. 35, 2, 2432.
Chomicki, J. 1990. Polynomial time query processing in temporal deductive databases. In
Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles
of Database Systems. PODS '90. 379391.
Chomicki, J. and Imielinski, T. 1988. Temporal deductive databases and in nite ob-
jects. In PODS. 6173.
Gottlob, G., Orsi, G., and Pieris, A. 2011. Ontological queries: Rewriting and opti-
mization. In ICDE. 213.
Greco, S. and Zaniolo, C. 1998. Greedy algorithms in datalog with choice and nega-
tion. 294309.
Greco, S. and Zaniolo, C. 2001a. Greedy algorithms in datalog. TPLP 1, 4, 381407.
Greco, S. and Zaniolo, C. 2001b. Greedy algorithms in datalog. TPLP 1, 4, 381407.
Greco, S., Zaniolo, C., and Ganguly, S. 1992. Greedy by choice. In PODS. 105113.
Guzzo, A. and Saccà, D. 2005. Semi-in ationary DATALOG: A declarative database
language with procedural features. AI Commun. 18, 2, 7992.
Hellerstein, J. M. 2010. Datalog redux: experience and conjecture. In PODS. 12.
Kolaitis, P. G. 1991. The expressive power of strati ed logic programs. Inf. Comput. 90,
5066.
Lausen, G., Ludäscher, B., and May, W. 1998. On active deductive databases: The
statelog approach. In Transactions and Change in Logic Databases. 69106.
Mazuran, M., Serra, E., and Zaniolo, C. 2013. A declarative extension of horn
clauses, and its signi cance for datalog and its applications. TPLP 13, 4-5, 609623.
Mumick, I. S., Pirahesh, H., and Ramakrishnan, R. 1990. The magic of duplicates
and aggregates. In VLDB. 264277.
Mumick, I. S. and Shmueli, O. 1995. How expressive is strati ed aggregation? Annals
of Mathematics and Arti cial Intelligence 15, 407435.
Palopoli, L. 1992. Testing logic programs for local strati cation. Theor. Comput.
Sci. 103, 2, 205234.
Przymusinski, T. C. 1988. Perfect model semantics. In ICLP 1988.
Ross, K. A. and Sagiv, Y. 1997. Monotonic aggregation in deductive database. J.
Comput. Syst. Sci. 54, 1, 7997.
Shkapsky, A., Zeng, K., and Zaniolo, C. 2013. Graph queries in a next-generation
datalog system. PVLDB 6, 12, 12581261.
Yang, M., Shkapsky, A., and Zaniolo, C. 2015. Parallel bottom-up evaluation of logic
programs: Deals on shared-memory multicore machines. In ICLP 2015, Cork Ireland.
Zaniolo, C. 2011. The logic of query languages for data streams. In Logic and Databases
2011. EDBT 2011 Workshops. 12.
Zaniolo, C., Arni, N., and Ong, K. 1993. Negation and aggregates in recursive rules:
the ldl++ approach. In DOOD. 204221.
14 Carlo Zaniolo
Zaniolo, C., Ceri, S., Faloutsos, C., Snodgrass, R. T., Subrahmanian, V. S.,
and Zicari, R. 1997. Advanced Database Systems. Morgan Kaufmann.