The P2 system uses an execution model inspired by database query engines and the Click modular router,
14 which
consists of elements that are connected together to implement a variety of network and flow control components. In
addition, P2 elements include database operators (such as
joins, aggregation, selections, and projects) that are directly
generated from the rules.
We will briefly explain how the SN evaluation is achieved
in P2. Each SN rule is implemented as a rule strand. Each
strand consists of a number of relational operators for selections, projections, joins, and aggregations. The example
strand receives new delta_path_old tuples generated
in the previous iteration to generate new paths (delta_
path_new), which are then inserted into the path table
(with duplicate elimination) for further processing in the
next iteration.
In Algorithm 1, we show the pseudocode for a centralized
implementation of multiple SN rule strands where each rule
has the form:
Dpj new :- p1old ,..., pkold -
1, Dpkold, pk+
1,..., pn, b1, b2,..., bm.
p1, …, pn are recursive predicates and b1, …, bm are base predicates. Dpkold refers to pk tuples generated for the first time in
the previous iteration. pkold refers to all pk tuples generated
before the previous iteration. These rules are logically equivalent to rules of the form:
Dpj new :- p1 ,..., pk-
1, Dpkold, pk+
1,..., pn, b1, b2,..., bm.
The earlier rules have the advantage of avoiding redundant
inferences within each iteration.
algorithm 1 Semi-naïve (SN) Evaluation in P2
while
$Bk.size > 0
"Bk where Bk.size > 0, Dpkold ¬ Bk. flush()
execute all rule strands
foreach recursive predicate pj
pjold ¬ pjold È Dpjold
Bj ¬ Dpj new - pjold
pj ¬ pjold È Bj
Dpj new ¬ f
In the algorithm, Bk denotes the buffer for pk tuples generated in the previous iteration (Dpkold). Initially, pk, pkold, Dpkold,
and Dpknew are empty. As a base case, we execute all the rules
to generate the initial pk tuples, which are inserted into the
corresponding Bk buffers. Each subsequent iteration of the
while loop consists of flushing all existing Dpkold tuples from Bk
and executing all rule strands to generate Dpj new tuples, which
are used to update pjold, Bj , and pj accordingly. Note that only
new pj tuples generated in the current iteration are inserted
into Bj for use in the next iteration. Fixpoint is reached when
all buffers are empty.
3. 2. Distributed plan generation
In the distributed implementation of the path-vector program, nonlocal rules whose body predicates have different location specifiers cannot be executed at a single node,
since the tuples that must be joined are situated at different
nodes in the network. A rule localization rewrite step ensures
that all tuples to be joined are at the same node. This allows
a rule body to be locally computable.
Consider the rule sp2 from the shortest-path program,
where the link and path predicates have different location specifiers. These two predicates are joined by a common @Nxt address field. Figure 3 shows the corresponding
logical query plan depicting the distributed join. The
clouds represent an “exchange”-like operator11 that forwards tuples from one network node to another; clouds are
labeled with the link attribute that determines the tuple’s
recipient. The first cloud (link.Nxt) sends link tuples to
the neighbor nodes indicated by their destination address
fields, in order to join with matching path tuples stored by
their source address fields. The second cloud (
path.Src)
transmits for further processing new path tuples computed from the join, setting the recipient according to the
source address field.
Based on the above distributed join, rule sp2 can be
rewritten into the following two rules. Note that all predicates in the body of sp2a have the same location specifiers;
the same is true of sp2b.
sp2a linkD(@Nxt,Src,Cost) :- link(@Src,Nxt,Cost).
sp2b path(@Src,Dest,Nxt,Path,Cost) :- linkD(@Nxt,Src,Cost1),
path(@Nxt,Dest,Path2,Cost2),Cost=Cost1+Cost2,
Path = f_concatPath(Src,Path2).
The rewrite is achievable because the link and path
predicates, although at different locations, share a common
join address field. The details of the rewrite algorithm and
associated proofs are described in a longer article.
20
Returning to our example, after rule localization we perform the SN rewrite, and then generate the rule strands shown
in Figure 4. Unlike the centralized strand in Figure 2, there
are now three rule strands. The extra two strands (sp2a@Src
and sp2b- 2@Nxt) are used as follows. Rule strand sp2a@
figure 3. Logical query plan for rule sp2.
( link.Src,path. Dest, f_concatPath( link.Src,
path.Path2), link.Cost1 + path.Cost2) as
path(Src,Dest,Path,Cost)
project
path.Src
link.Nxt=path.Nxt
link.Nxt
link(Src,Nxt,Cost1)