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
Times are displayed in 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 PientkaMcGill University
Seminaïve Evaluation for a Higher-Order Functional LanguageDistinguished Paper
Research Papers
Neel KrishnaswamiComputer Laboratory, University of Cambridge, Michael ArntzeniusUniversity of Birmingham, UK
Link to publication DOI Media Attached File Attached
Decomposition Diversity with Symmetric Data and Codata
Research Papers
David BinderUniversity of Tübingen, Julian JabsUniversity of Tübingen, Ingo SkupinUniversity of Tübingen, Klaus OstermannUniversity of Tübingen, Germany
Link to publication DOI Media Attached