Maintaining Distributed Recursive Views Incrementally

This paper proposes an algorithm to compute incrementally the changes to distributed recursive database views in response to insertions and deletions of base facts. Our algorithm uses a pipelined semi-näıve (PSN) evaluation strategy introduced in declarative networking. Unlike prior work, our algorithm is formally proven to be correct for recursive query computation in the presence of message reordering in the system. Our proof proceeds in two stages. First, we show that all the operations performed by our PSN algorithm computes the same set of results as traditional centralized semi-näıve evaluation. Second, we prove that our algorithm terminates, even in the presence of cyclic derivations due to recursion.