Dan Olteanu wins Test-of-Time Award for 2016 paper

The International Conference on Database Theory (ICDT) presented the 2026 Test of Time Award to Visiting Professor Dan Olteanu and his co-authors Vince Bárány, Balder ten Cate, Benny Kimelfeld, and Zografoula Vagena.  

The award recognises a paper presented 10 years prior at the ICDT conference that has best met the ‘test of time’ and had the highest impact in terms of research, methodology, conceptual contribution, or transfer to practice over the past decade. The award was presented during the EDBT/ICDT 2026 Joint Conference last month in Tampere Finland. 

The 2016 paper that earned the award is ‘Declarative Probabilistic Programming with Datalog’. The paper was written while Dan was a professor with the department. 

The paper proposes Generative Datalog, a probabilistic extension of Datalog that allows sampling from discrete probability distributions. Generative Datalog can be seen as a declarative probabilistic programming language that operates on standard relational databases. The idea is simple but elegant: Given that we can view an existential Datalog program as a generator of families of models, why not turn it into a generator of a probabilistic model? On the side of language design, all it takes is to attach probability distributions to the tuple-generating dependencies. Although the language itself is conceptually simple, it rests on a surprisingly deep mathematical foundation. Even in this initial paper, where all distributions are discrete, establishing its formal semantics already requires tools from measure theory.

The paper explains the language, defines the semantics, a probabilistic version of the chase, discusses adding constraints in the spirit of probabilistic programming, and touches upon the equivalence problem for programs. It generated a significant amount of follow-up in a variety of areas spanning database theory, database systems, and programming languages. 

Together with his former Oxford research team, Dan previously won the 2022 Test of Time Award at the International Conference on Database Theory for their 2012 work on factorised databases.