EDBT/ICDT 2022 Invited Talks

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

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: Data Intelligence for Robust AI
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. Such constrained interactions 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 at 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.

Keynote 3: 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 4: 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.

EDBT Invited Talk: Logical Algorithmics
by Moshe Y. Vardi

Abstract: The standard approach to algorithm development is to focus on a specific problem and develop for it a specific algorithm. Codd's introduction of the relational model in 1970 included two fundamental ideas: (1) Relations provide a universal data representation formalism, and (2) Relational databases can be queried using first-order logic. Realizing these ideas required the development of a meta-algorithm, which takes a declarative query and executes it with respect to a database. In this talk, I will describe this approach, which I call Logical Algorithmics, in detail, and explore its profound ramification.

Moshe Y. Vardi is University Professor and the George Distinguished Service Professor in Computational Engineering at Rice University. He is the recipient of several awards, including the ACM SIGACT Goedel Prize, the ACM Kanellakis Award, the ACM SIGMOD Codd Award, the Knuth Prize, the IEEE Computer Society Goode Award, and the EATCS Distinguished Achievements Award. He is the author and co-author of over 750 papers, as well as two books. He is a Guggenheim Fellow as well as fellow of several societies, and a member of several academies, including the US National Academy of Engineering and National Academy of Science. He holds seven honorary doctorates. He is a Senior Editor of the Communications of the ACM, the premier publication in computing.

D&I Invited Talk: Algorithmic Fairness for Graphs
by Evaggelia Pitoura

Abstract: Algorithmic systems that exploit large datasets are increasingly being used to assist or even replace human decision making, a fact that has raised various concerns about the trustworthiness of such systems. Algorithmic fairness addresses such concerns. In this talk, we focus on fairness for graphs and specifically on PageRank fairness. PageRank assigns a score to each node in the graph that signifies the importance of the node. Given that nodes belong to groups, we study fairness in terms of the distribution of the scores assigned to each group. We first present fairness-aware PageRank algorithms that achieve fairness with minimum loss from the original PageRank. Then, we take a different approach where instead of modifying the PageRank algorithm, we ask how to improve the graph. Concretely, we derive analytical formulas for the contribution of each edge to fairness and use them to design link recommendation algorithms for maximizing fairness. We present experimental results using various real and synthetic graphs. We conclude the talk with a list of open problems and promising research directions for algorithmic fairness for both graph and relational data.

Evaggelia Pitoura is a Professor at the University of Ioannina, Greece. She received a BSc degree from the University of Patras, Greece, and an MS and PhD degree from Purdue University, USA. Her research interests are in data management with a recent emphasis on data exploration, graphs, and responsible data management. Her publications include more than 150 articles in top-tier international journals and conferences. Her research has been funded by the EC and national sources. She has served or serves on the editorial board of ACM TODS, VLDBJ, TKDE, DAPD and as a group leader, senior PC member, or co-chair of many international conferences (including PC chair of EDBT 2016 and co-chair of ICDE 2012). She has received three best paper awards (ICDE 1999, DBSocial 2013, PVLDB 2013), a Marie Currie Fellowship and two Recognition of Service Awards from ACM. She is an ACM senior member, chair of the Greek ACM-W event steering committee and member of the sectorial scientific council of Greece National Council for Research, Technology and Innovation.

ICDT Invited Tutorial: Answering Unions of Conjunctive Queries with Ideal Time Guarantees
by Nofar Carmeli

Abstract: The holy grail we strive for is, given a query, to identify an algorithm that answers it over general databases with optimal time guarantees for the specific query. In this tutorial, we focus on what can be seen as ideal time guarantees: linear preprocessing (needed to read the input) and constant time per answer (needed to print the output). We seek to understand which queries can be solved with these (or almost these) time guarantees and how.

We start with the basic building blocks of database queries: joins, and slowly increase the expressivity by introducing projections and unions until we cover positive relational algebra. We first consider the task of enumerating all query answers and then discuss related, more demanding, tasks such as ordered enumeration and direct access to query answers. We investigate the challenges in answering such queries and provide algorithms and conditional lower bounds.

Nofar Carmeli is currently a post doctoral researcher at the Valda team in École Normale Supérieure Paris. Her research focuses on theoretical aspects of database query optimization. She completed her Ph.D. at the Technion Data & Knowledge Laboratory in Israel.