RSS Meetups are monthly gatherings of LASIGE members with research interests mainly in Software Architecture, Verification, Testing, Programming Languages, Type Systems, Logic, Concurrency, and Formal Methods.

Title: Programming joins, simply and efficiently
Speakers: Fritz Henglein (DIKU, U. Copenhagen)
When: September 15, 2025, 13h30
Where: FCUL, 6.3.27
Invited by: Vasco Vasconcelos

Abstract: One often has to program relational joins on program data, that is computing the relation (collection) { (x1, …, xn) | F } where F is a relational first-order logic formula built from conjunction over predicate symbols representing input relations. Examples are classical binary joins such as the the products sold by salespeople or the set of triangles { (x1, x2, x3) | R(x1,2) and R(x2, x3) and R(x3, x1)} in a graph (binary relation) R.
We show that all joins are easy to program efficiently using elementary programming techniques: Building nested read-only dictionaries, always iterating over a dictionary with the smallest domain, and nested iteration over the variables x1, …, xn in any order. Employing amortized complexity analysis on inputs padded with ghost data and a weak property of the Atserias-Grohe-Marx fractional edge covering bound we show that this constitutes a simply programmed worst-case optimal join algorithm. The algorithm can be considered a simplified version of Generic Join where one step is left out. We illustrate the resulting 10 line source code for triangles in Python and a corresponding Haskell program and show that these execute multiple orders of magnitude faster on a ‘difficult’ class of data than piping the data through any of a number of common SQL engines.
This is joint work with Changjun Li, Mikkel Kragh Mathiesen and Mads Rehof.

Short Bio: Fritz Henglein’s research interests are in semantic, logical and algorithmic aspects of programming languages, specifically type inference, type-based program analysis, algorithmic functional programming and domain-specific languages, and the application of programming language technology, presently in enterprise systems (Project 3gERP and health care process modeling (Project TrustCare). After undergraduate studies at Technische Universität München, he obtained his Ph.D. from Rutgers University and joined New York University, Utrecht University and DIKU, the Department of Computer Science at the University of Copenhagen. After starting Hafnium ApSto keep the Y2K bug at bay and being on the start-up faculty of the IT University of Copenhagen to increase IT proficiency, he rejoined DIKU as professor with special duties in programming languages. He is now head of the algorithms and programming languages group at DIKU. His goal is to contribute to the development of software that comes with technical and legal guarantees of having no defects (which should be considered a very modest ambition indeed).