One of the workhorse techniques for implementing bottom-up Datalog engines is seminaive evaluation. This optimization improves the performance of Datalog’s most distinctive feature: recursively defined predicates. Under a naive evaluation strategy, many values are unnecessarily re-computed; seminaive evaluation computes (a safe approximation of) just the new values generated at each step. This optimization is critical, as it can asymptotically improve the performance of Datalog queries.

Seminaive evaluation is defined partly as a program transformation on sets of Datalog rules, and partly as a modification of the fixed point computation algorithm, and takes heavy advantage of the fact that Datalog is fundamentally a first-order programming language. This paper gives an extended version of this transformation which works on higher-order programs written in the Datafun language, which extends Datalog with features like first-class relations, higher-order functions, and datatypes like sum types.