Por Fritz Henglein (DIKU, U. Copenhagen).
Os RSS Meetups são encontros mensais dos membros do LASIGE com interesses de investigação principalmente em Arquitetura de Software, Verificação, Testes, Linguagens de Programação, Sistemas de Tipos, Lógica, Concorrência e Métodos Formais. Todos são bem-vindos, incluindo estudantes e não investigadores.
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.
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 ApS to 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).
