Seminaïve Evaluation for a Higher-Order Functional Language
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.
|Presentation Slides (popl20-presentation.pdf)||1.73MiB|
Thu 23 Jan
|11:45 - 12:07|
Neel KrishnaswamiComputer Laboratory, University of Cambridge, Michael ArntzeniusUniversity of Birmingham, UKLink to publication DOI Media Attached File Attached
|12:07 - 12:30|
David BinderUniversity of Tübingen, Julian JabsUniversity of Tübingen, Ingo SkupinUniversity of Tübingen, Klaus OstermannUniversity of Tübingen, GermanyLink to publication DOI Media Attached