An Operational Semantics for Network Datalog

Network Datalog (NDlog) is a recursive query language that extends Datalog by allowing programs to be distributed in a network. In our initial efforts to formally specify NDlog’s operational semantics, we have found several problems with the current evaluation algorithm being used, including unsound results, unintended multiple derivations of the same table entry, and divergence. In this paper, we make a first step towards correcting these problems by formally specifying a new operational semantics for NDlog and proving its correctness for the fragment of non-recursive programs. We also argue that if termination is guaranteed, then the results also extend to recursive programs. Finally, we identify a number of potential implementation improvements to NDlog.