Gems of PODS
Speaker: Benny Kimelfeld (Technion - Israel Institute of Technology)
Title: Enumeration Theory through the Lens of Database Challenges
Abstract: Computational tasks that require producing many answers arise throughout data management systems: SQL engines return all qualifying tuples; search engines retrieve all relevant documents, albeit ranked; graph databases are tasked with producing all paths connecting two nodes; query optimizers routinely explore a vast space of candidate plans; and so on. Abstractly, these tasks are formalized as enumeration problems, solved by enumeration algorithms, and studied through the lens of enumeration complexity. This talk reflects on the evolution of enumeration in database research. It will begin with a brief survey of classic complexity-theoretic notions and algorithmic techniques that play a central role in enumeration across many domains. It will then review past results on enumeration problems arising in various areas of database systems. After that, it will delve deeper into the evolution of ideas and results on answer enumeration in relational queries. It will conclude with challenges for future directions.
Bio: Benny Kimelfeld is a Professor of Computer Science at the Technion - Israel Institute of Technology, where he is the head and founder of the Technion Data and Knowledge Laboratory. He received his Ph.D. from the Hebrew University of Jerusalem, and prior to joining the Technion was a Research Staff Member at IBM Research Almaden and a Research Scientist at LogicBlox. He currently serves as the Dean of the Technion's School of Undergraduate Studies. His research spans foundational and systems aspects of data management, with contributions to algorithms for query evaluation, probabilistic and inconsistent databases, interpretability and explanation of query results, and the interplay between databases and machine learning. His work has been supported by the Israel Science Foundation (ISF), the U.S. National Science Foundation (NSF), and the German-Israeli Project Cooperation (DIP). He serves as an Associate Editor for the Journal of Computer and System Sciences (JCSS), and as the Editor of the Database Principles Column of SIGMOD Record. He has served as Program Committee Chair of ICDT 2018 and PODS 2025, and is currently the Chair of the ICDT Council.