Communications - November 2009

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@