EDBT/ICDT 2022 Invited Keynotes

We are very pleased to announce the EDBT/ICDT 2022 invited keynote speakers.

EDBT Invited Keynotes

Keynote 1: The (sorry) State of Graph Database Systems
by Peter Boncz

Abstract: Graph data management and analytics has been one of the hottest topics at database conferences, and continues to be popular. Many graph database systems, originally managing RDF data, but increasingly those catering for the Property Graph model, have appeared and captured a growing niche of the data management market. After a decade of this trend, one would hope for mature technology, but this keynote will point out a number of weaknesses across the board. But there is also reason for optimism, in terms of convergence of functionality and technical and algorithmic improvements. Spurring this maturation of graph technology is one of the main goals of LDBC (ldbcouncil.org), an academic and industry non-profit organisation that our community has produced.

This keynote will describe the current landscape of graph database systems, including its challenges and opportunities. It will provide an update on multi-pronged efforts to standardise graph database functionality, in which LDBC collaborates with ISO, and outline the current understanding of the main technical ingredients of future graph data systems architecture.

Peter Boncz holds appointments as tenured researcher at CWI and professor at VU University Amsterdam. His academic background is in database architecture, with the early column-store MonetDB the outcome of his PhD. MonetDB later won the 2016 ACM SIGMOD systems award. He has a track record in bridging the gap between academia and commercial application. In 2008 he co-founded Vectorwise around the analytical database system by the same name which pioneered vectorized query execution. He is co-recipient of the 2009 VLDB 10 Years Best Paper Award, and in 2013 became a Fellow at TU Munich on receiving the Humboldt Research Award for his research on database architecture. In the past decade, his work in graph data management has focused on the Linked Database Benchmark Council (LDBC), which he co-founded in 2013 and still chairs. He also co-founded the SIGMOD workshops DAMON and GRADES, the latter themed on graph data management. His most recent new activity is in advising the new CWI startup around DuckDB (duckdb.org).

Keynote 2: Interactive Learning for Language-- Data Intelligence to the Rescue
by Seung-won Hwang

Abstract: Training AI models can be viewed as interacting human intelligence with model intelligence. From this view, current norms of model training are constrained to crowdsourcing label annotations for a closed set. We argue such interaction is too constrained, which may explain why models solve datasets, instead of pursuing true learning goals. This talk discusses our recent work, showing how data intelligence research is relevant to enriching interactions between human and model intelligence, for robust training of NLP models that generalize well. More details can be found from http://seungwonh.github.io

Seung-won Hwang is a Professor of Computer Science and Engineering at Seoul National University. Prior to joining SNU, she has been a faculty at POSTECH and Yonsei University, after her PhD from UIUC. Her research interests concern the interaction between data and language intelligence. Her work has been published at top-tier AI, DB/DM, and IR/NLP venues, including ACL, AAAI, IJCAI, NAACL, SIGIR, SIGMOD, VLDB, and ICDE. Her contributions have been recognized by awards from WSDM and Microsoft Research.

ICDT Invited Keynotes

Keynote 1: Counting the Solutions to a Query
by Marcelo Arenas

Abstract: In this talk, we consider the problem of counting the solutions to a query. Our first motivating scenario is the use of regular expressions to extract paths from a graph database. More specifically, given a graph database D, a regular expression r and a natural number n, consider the problem of counting the number of paths p in D such that p conforms to r and the length of p is n. This problem is known to be hard, namely #P-complete. In this talk, we show that this problem admits a fully polynomial-time randomized approximation scheme (FPRAS). Remarkably, the key idea to prove this result is to show that the fundamental problem #NFA admits an FPRAS, where #NFA is the problem of counting the number of strings of length n accepted by a non-deterministic finite automaton (NFA). While this problem is known to be #P-complete and, more precisely, SpanL-complete, it was open whether this problem admits an FPRAS. In this work, we solve this open problem and obtain as a welcome corollary that every function in SpanL admits an FPRAS.

As a second motivating scenario, we consider the widely used class of conjunctive queries over relational databases. More specifically, for every class C of conjunctive queries with bounded treewidth, we introduce the first FPRAS for counting the answers to a query in C. In fact, our FPRAS is more general, and also applies to conjunctive queries with bounded hypertree width, as well as unions of such queries. As for the case of graph databases, the key ingredient in our proof is the resolution of a fundamental counting problem from automata theory. Specifically, we show that the problem #TA admits an FPRAS, where #TA is the problem of counting the number of trees of size n accepted by a tree automaton (TA).

This is joint work with Luis Alberto Croquevielle, Rajesh Jayaram and Cristian Riveros.

Marcelo Arenas is a Professor at the Department of Computer Science and the Institute for Mathematical and Computational Engineering, at the Pontificia Universidad Católica de Chile. He is the director of the Millennium Institute for Foundational Research on Data and the former director of the Center for Semantic Web Research. He received a Ph.D. from the University of Toronto in 2005. His research interests are in the areas of data management, applications of logic in computer science and Semantic Web. He has received an IBM Ph.D. Fellowship (2004), a SIGMOD Jim Gray Doctoral Dissertation Award Honorable Mention in 2006 for his Ph.D. dissertation "Design Principles for XML Data", the 2016 Semantic Web Science Association (SWSA) Ten-Year Award for the article "Semantics and Complexity of SPARQL" and nine best paper awards (PODS 2003, PODS 2005, ISWC 2006, ICDT 2010, ESWC 2011, PODS 2011, WWW 2012, ISWC 2014 and PODS 2019). He has served on multiple program committees and editorial boards, and he has chaired the program committees of ICDT 2015, ISWC 2015 and PODS 2018.

Keynote 2: On an Information Theoretic Approach to Cardinality Estimation
by Hung Ngo

Abstract: Cardinality estimation is among the most important problems in query optimization. It is well-known that, when query plans go haywire, in most cases one can trace the root cause to the cardinality estimator being far off. In particular, traditional cardinality estimation based on selectivity estimation may sometimes under-estimate cardinalities by orders of magnitudes, because the independence or the uniformity assumptions do not typically hold. This talk outlines an approach to cardinality estimation that is "model-free" from a statistical stand-point. Being model-free means the approach tries to avoid making any distributional assumptions, as much as possible. The approach is information-theoretic, and generalizes recent results on worst-case output size bounds of queries, allowing the estimator to take into account histogram information from the input relations. The estimator turns out to be the objective of a maximization problem subject to concave constraints, over an exponential number of variables. We then explain how the estimator can be computed in polynomial time for some fragment of these constraints. Overall, the talk introduces a new direction to address the classic problem of cardinality estimation that is designed to circumvent some of the pitfalls of selectivity-based estimation. We will also present connections to information inequalities. This talk is based on (published and unpublished) joint works with Mahmoud Abo Khamis, Sungjin Im, Hossein Keshavarz, Phokion Kolaitis, Ben Moseley, XuanLong Nguyen, Kirk Pruhs, and Dan Suciu.

Hung Ngo is the VP of Research at RelationalAI Inc., where he also leads the query optimization group. Before RelationalAI, he worked at LogicBlox Inc from 2015 to 2017, and was a professor of Computer Science and Engineering at the State University of New York at Buffalo from 2001 to 2015. His current research focus is in the design and analysis of query evaluation and optimization algorithms for Rel, a Turing-complete declarative programming language developed at RelationalAI. Ngo received best papers awards at PODS 2012, PODS 2016, and ICDT 2019.