Write a Blog >>

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

Displayed time zone: Saskatchewan, Central America change

11:45 - 12:30
Datalog, OO + Functional ProgrammingResearch Papers at Ile de France III (IDF III)
Chair(s): Brigitte Pientka McGill University
Seminaïve Evaluation for a Higher-Order Functional LanguageDistinguished Paper
Research Papers
Neel Krishnaswami Computer Laboratory, University of Cambridge, Michael Arntzenius University of Birmingham, UK
Link to publication DOI Media Attached File Attached
Decomposition Diversity with Symmetric Data and Codata
Research Papers
David Binder University of Tübingen, Julian Jabs University of Tübingen, Ingo Skupin University of Tübingen, Klaus Ostermann University of Tübingen, Germany
Link to publication DOI Media Attached