News

Our work on the LpBound cardinality estimator to appear in ACM SIGMOD 2025 received the Best Paper Award!

Our work on information-theoretic cardinality estimation with guarantees, which appeared initially in PODS 2024, has received the SIGMOD Research Highlights Award. "SIGMOD Research Highlights are to showcase a set of research projects that exemplify core database research. In particular, these projects address an important problem, represent a definitive milestone in solving the problem, and have the potential of significant impact. SIGMOD Research Highlights also aim to make the selected works widely known in the database community, to our industry partners, and to the broader ACM community."

Prof. Olteanu has been appointed Programme Committee Chair of the ACM Symposium on Principles of Database Systems (PODS) 2027. PODS is the premier international conference on the theoretical aspects of database systems.

Prof. Olteanu is invited to speak on Query Optimization Unleashed — Bridging Theory, AI, and Systems for the Future of Databases".

• Output-Sensitive Evaluation of Regular Path Queries[ arxiv ]
  Mahmoud Abo Khamis, Ahmet Kara, Dan Olteanu, Dan Suciu.
  To appear in ACM PODS (PACMMOD Journal), June 2025.

• Insert-Only versus Insert-Delete in Dynamic Query Evaluation. [ arxiv, ACM ]
  Mahmoud Abo Khamis, Ahmet Kara, Dan Olteanu, Dan Suciu.
  To appear in ACM PODS (PACMMOD Journal), November 2024.

• Using Process Calculus for Optimizing Data and Computation Sharing in Complex Stateful Parallel Computations.
  Zilu Tian, Christoph Koch, Dan Olteanu

• LpBound: Pessimistic Cardinality Estimation Using Lp-Norms of Degree Sequences. [arxiv]
  Haozhe Zhang, Christoph Mayer, Mahmoud Abo Khamis, Dan Olteanu, Dan Suciu.

• LpBound in Action: Cardinality Estimation with One-Sided Guarantees. [demo, video]
  Haozhe Zhang, Christoph Mayer, Mahmoud Abo Khamis, Dan Olteanu, Dan Suciu

• Pessimistic Cardinality Estimation.
  Mahmoud Abo Khamis, Kyle Deeds, Dan Olteanu, Dan Suciu.

Overview of pessimistic cardinality estimators and their comparison with traditional, density-based estimators.

Many thanks to the Swiss National Science Foundation (SNSF) for funding our research on cardinality estimation with strong theoretical guarantees for the next four years!

Dr. Tian gave a talk in the Hyperscale Systems and Cloud Architecture lab at Nanyang Technological University (NTU), Singapore on her on-going work on using process calculus for optimizing data and computation sharing in complex stateful parallel computations.

During his sabbatical, Prof. Olteanu will give lectures on DaST research projects at several institutions:

• Sept 2024: GSL Talk @ Microsoft Gray Systems Lab on cardinality estimation
• Nov 2024: CS distinguished colloquium @ Boston University on incremental view maintenance
• Nov 2024: Seminar @ MIT CSAIL on cardinality estimation
• Nov 2024: Data Lab Seminar @ Northeastern on machine learning over relational data
• Nov 2024: LFCS Seminar at University of Edinburgh on cardinality estimation
• Jan 2025: Database Seminar @ University of Washington on factorised databases
• Jan 2025: Logic and Algorithms in Database Theory and AI Reunion, Simons Institute for the Theory of Computing, UC Berkeley: Seminar on cardinality estimation

Postdoctoral researcher Dr. Zilu Tian was awarded an UZH grant to support her research project "Efficient execution of distributed agent-based simulations" starting October 2024.

• CHORUS: Foundation Models for Unified Data Discovery and Exploration. [arxiv ]
  Moe Kayali, Anton Lykov, Ilias Fountalis, Nikolaos Vasiloglou, Dan Olteanu, Dan Suciu.

Nominated for the best paper award at VLDB 2024 (15 out of 303 accepted papers were nominated)

Dr. Ahmet Kara will join OTH Regensburg as tenured professor starting September 2024. The DaST group wishes him all the best in his future career and thanks him for his extraordinary contributions to the research, teaching, admin, and well-being of the group over the past four years.

Dr. Zhang was invited to talk on "Recent Advances in Incremental View Maintenance" at the SPARSE workshop collocated with PLDI 2024 in Copenhagen.

Prof. Olteanu co-organises together with Prof. Geerts (U Antwerp) a special session on Bridging Theory and Practice at PODS 2024 in Santiago, Chile on June 9, 2024.
Three distinguished invited speakers will give their insights into how to identify research problems that (do not) have potential for theory and practice and their recipes for theory to practice transition or vice versa.

Prof. Olteanu will deliver the Gems of PODS lecture at the ACM PODS 2024 conference to be held in Santiago, Chile in June 2024. Gems of PODS features topics and results in PODS that have been highly influential in the PODS community and beyond. The lecture will be on the Incremental View Maintenance problem.

• Banzhaf Values for Facts in Query Answering. [ arxiv ]
  Omer Abramovich, Daniel Deutch, Nave Frost, Ahmet Kara, Dan Olteanu.
  In SIGMOD 2024.

• Join Size Bounds using Lp-Norms on Degree Sequences. [ arxiv]
  Mahmoud Abo Khamis, Vasileios Nakos, Dan Olteanu, Dan Suciu.
  In PODS 2024.
  Distinguished paper, invited to a special issue of ACM TODS for best of PODS 2024
• From Shapley Value to Model Counting and Back. [ arxiv]
  Ahmet Kara, Dan Olteanu, Dan Suciu.
  In PODS 2024.

• CHORUS: Foundation Models for Unified Data Discovery and Exploration will be presented at the 2nd Table Representation Learning Workshop, NeuIPS 2023.

We are grateful to UZH for a grant to support our on-going joint research project on dynamic query evaluation with Dr. Milos Nikolic from University of Edinburgh.

Dr. Kara delivers an overview lecture on factorized databases [video] at the Probabilistic Circuits and Logic workshop, which is part of the "Logic and Algorithms in Database Theory and AI" program at Simons Institute for the Theory of Computing in Berkeley, California.

• Givens Rotations for QR Decomposition, SVD and PCA over Database Joins. [arxiv]
  Dan Olteanu, Nils Vortmeier, Dorde Zivanovic.
• F-IVM: Analytics over Relational Databases under Updates. [arxiv]
  Ahmet Kara, Milos Nikolic, Dan Olteanu, Haozhe Zhang.

Prof. Olteanu is an invited lecturer in the advanced course CS294-248: Topics in Database Theory. His two lectures introduce the topic of incremental view maintenance and highlights recent results done by the DaST team towards efficient fully dynamic algorithms and optimality of the IVM problem.

Slides: pdf. Videos: part 1 and part 2.

After having spent some time as MSc student with DaST, Christoph Mayer joins DaST as PhD student. He will work on adaptive processing of database and machine learning workloads and will support our teaching on machine learning and query processing.

DaST work on incremental view maintenance will be presented at the Logic and Algorithms in Database Theory and AI Boot Camp at the Simons Institute for the Theory of Computing in Berkeley, California.

Videos: part 1 and part 2

• ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Joins via Reinforcement Learning. [ arxiv ]
  Junxiong Wang, Immanuel Trummer, Ahmet Kara, Dan Olteanu.
• Demonstrating ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Joins via Reinforcement Learning.
  Junxiong Wang, Mitchell E Gray, Immanuel Trummer, Ahmet Kara, Dan Olteanu.

Prof. Olteanu is honoured as Distinguished Associate Editor at VLDB 2023 for his work from March 2022 to June 2023 as associate editor of the Proceedings of Very Large Databases Volume 16. This award is in recognition of "the timely handling of the papers, active and thoughtful guidance of the discussions and reviewer probing, well-informed decisions, and detailed meta-reviews". The editorial board comprised 35 associate editors and 213 reviewers. They managed over 1000 papers, out of which 266 were accepted for this volume of PVLDB.

We are grateful to UZH for a grant to support our on-going joint research project on fact attribution in query answering with Prof. Daniel Deutch from Tel Aviv University.

Johannes joins DaST to support our teaching and research in data science, database theory, and logic.

• F-IVM: Analytics over Relational Databases under Updates
• FiGaRo: Matrix Decompositions over Database Joins

DRAGSTERS (Workshop on Distributions, Relational Algebra, Graphs, Semi-Rings, Tensors, and All That) at the 44th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2023).

Out SIGMOD'22 paper Givens QR Decomposition over Relational Databases has been successfully reproduced! It was awarded the badges "Artifacts Evaluated" and "Results Reproduced".

In his inaugural lecture, Prof. Dan Olteanu showcased how the intertwining of theory and systems can successfully address challenges that arise in answering questions over uncertain data and learning over large relational data. [slides (PDF, 8 MB), video] 

It was wonderful to meet in person DaST collaborators and friends from EPFL, University of Edinburgh, Ruhr-Bochum University, University of Washington, RelationalAI Zurich, and Apple Zurich, and talk about on-going research projects. More details are here.

Congratulations to our student Antonia Kormpa, who defended her PhD thesis in the Department of Computer Science, University of Oxford. Antonia's work establishes a polynomial-time equivalence between two query evaluation problems: for queries with intersection joins and for queries with equality joins. Her work appeared in ACM PODS 2022.

Congratulations to our student Dorde Zivanovic, who defended his PhD thesis in the Department of Computer Science, University of Oxford. Dorde's work in at the interface of linear algebra and relational databases: Matrix decompositions (QR, SVD, PCA), where the matrix is defined by joins over relational data. His work was published in ACM SIGMOD 2022 and will appear in the Special Issue of Databases and Machine Learning of the VLDB Journal 2023.

Brief overview of DaST efforts on the theory and systems for real-time analytics over continuously evolving databases. The slides are available here (PDF, 4 MB).

Prof. Dan Suciu (University of Washington) will be spending this semester in the DaST research group as part of his sabbatical. He is accompanied by his graduate students Anton Lykov and Moe Kayali. Looking forward to a wonderful research-intensive semester!

• Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries.
  In LMCS (Logical Methods in Computer Science) journal 2023.
• Conjunctive Queries with Free Access Patterns under Updates.
  In ICDT (International Conference on Database Theory) 2023.
  Distinguished paper, invited to LMCS special issue of best papers at ICDT 2023.
• Evaluation Trade-Offs for Acyclic Conjunctive Queries.
  In CSL (Computer Science Logic) 2023.

Congratulations to our student Haozhe Zhang, who defended his PhD thesis in the Department of Computer Science, University of Oxford. Haozhe's work in on worst-case optimality of maintenance for queries under updates to the input database.

• Functional collection programming with semi-ring dictionaries. [arxiv]
  Proc. ACM Program. Lang. 6(OOPSLA1): 1-33 (2022)
  Distinguished paper, invited to JFP special issue of best papers at OOPSLA 2022

Check out the exciting program of the Factorised Databases workshop to take place from August 2 to 4 in Zurich and online. Contact a member of the DaST team if you are interested to attend.

• Givens QR Decomposition over Relational Databases [arxiv Video], ACM SIGMOD
  Push QR decomposition of matrices, which are defined by acyclic joins over relational data, past the joins to improve runtime performance and numerical accuracy.
• The Complexity of Boolean Conjunctive Queries with Intersection Joins [arxiv, Video], ACM PODS
  Settle the longstanding open problem of the data complexity for queries with intersection joins and give syntactic characterisation of all such queries that can be computed in linear time data complexity.

Prof. Olteanu has been elected unanimously by the members of the ICDT (International Conference on Database Theory) council to serve as the chair of the council. In this new role, he is responsible for leading the council meetings.

Dan Olteanu and Jakub Závodný received the Test of Time Award for their ICDT 2012 paper "Factorized Representations of Query Results: Size Bounds and Readability". This award recognizes 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.

23-minute video of the talk is available here.

News: Conference announcement; UZH IfI; St Cross College, University of Oxford; Department of Computer Science, University of Oxford

Work by the DaST team on "Machine Learning through Database Glasses" to be presented at the Workshop on Databases and AI at NeuIPS 2021 conference.

The DaST group will give a tutorial on in-database machine learning at Distributed Event-Based Systems (DEBS) conference in June 2021.

Former PhD student Maximilian Schleich was awarded an Honourable Mention for the 2021 SIGMOD Jim Gray Doctoral Dissertation Award for his DPhil dissertation entitled "Structure-Aware Learning over Multi-Relational Databases". The award recognizes excellent research by doctoral candidates in the database field.

Dr. Ahmet Kara and Prof. Dan Olteanu will give an invited talk on their work on trade-offs in incremental maintenance for query processing at the workshop Spotlight on Logic and Databases associated with the Highlights of Logic, Games, and Automata conference.

LMFAO (Layered Multiple Functional Aggregate Optimisation) has been released in the public domain.

LMFAO 1.0 Repository https://github.com/fdbresearch/LMFAO

• Maintaining Triangle Queries under Updates. [arxiv]
  Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, Haozhe Zhang.
  In ACM Transactions on Database Systems (TODS), 2020.
  Special issue of best papers at ICDT 2019
• Functional Aggregate Queries with Additive Inequalities. [arxiv]
  Mahmoud Abo Khamis, Ryan Curtin, Benjamin Moseley, Hung Ngo, XuanLong Nguyen, Dan Olteanu and Maximilian Schleich.
  In ACM Transactions on Database Systems (TODS), 2020.
  Special issue of best papers at PODS 2019
• In-Database Learning with Sparse Tensors and Functional Dependencies. [arxiv]
  Mahmoud Abo Khamis, Hung Ngo, XuanLong Nguyen, Dan Olteanu, and Maximilian Schleich.
  In ACM Transactions on Database Systems (TODS), 2020.
  Special issue of best papers at PODS 2018

---

Dan Olteanu will give a . VLDB is an internationally premier forum for data management and database research in academia and industry.

• The Relational Data Borg is Learning [arxiv]
  Dan Olteanu.
  Keynote at Very Large Data Bases (VLDB) 2020
• LMFAO: An Engine for Batches of Group-By Aggregates (Demonstration) [arxiv, video]
  Maximilian Schleich, Dan Olteanu.
  In PVLDB 2020.

Check out videos and slides for our PODS and SIGMOD papers on incremental maintenance of queries and machine learning over evolving relational databases:

• F-IVM: Learning over Fast Evolving Relational Data. (Demonstration)
  Milos Nikolic, Haozhe Zhang, Ahmet Kara, Dan Olteanu.
  In ACM SIGMOD 2020. [pdf, video]
• Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries.
  Ahmet Kara, Milos Nikolic, Dan Olteanu, Haozhe Zhang.
  In ACM PODS 2020. [arxiv, extended slides, video]

Prof. Olteanu has been appointed Programme Committee Chair of the International Conference on Database Theory (ICDT) 2022. Together with PODS, ICDT is the main international forum for research in database theory.

As of 1 May 2020 the Board of the University has appointed Dan Olteanu as ordinary (full/chair) Professor for Big Data Science.
More...