Speaker: Dan Suciu, University of Washington
Abstract: We discuss two novel connections between information theory and data management. The first is a new paradigm for query processing, which we call "from proofs to algorithms". In order to evaluate a query, one first proves an upper bound on its output, by proving an information theoretic inequality. Then, each step of this proof becomes a relational operator. The resulting algorithm is "worst case optimal", meaning that it runs in time bounded by the maximum output to the query. Second, we consider the "implication problem" for Functional Dependencies, Multivalued Dependencies, and Conditional Independence constraints in graphical models, and ask whether it relaxes to an inequality between the corresponding information theoretic measures. When it does, then we can convert an implication between exact constraints into an implication between approximate constraints. We show that FDs, MVDs, and the special cases of graphoid axioms studied by Geiger and Pearl do relax, but, rather surprisingly, there exists exact implications that cannot be relaxed.
Joint work with Mahmoud Abo Khamis, Batya Kenig, and Hung Q. Ngo.
Bio: Dan Suciu is a Professor in Computer Science at the University of Washington. He received his Ph.D. from the University of Pennsylvania in 1995, was a principal member of the technical staff at AT&T Labs and joined the University of Washington in 2000. Suciu is conducting research in data management, with an emphasis on topics related to Big Data and data sharing, such as probabilistic data, data pricing, parallel data processing, data security. He is a co-author of two books Data on the Web: from Relations to Semistructured Data and XML, 1999, and Probabilistic Databases, 2011. He is a Fellow of the ACM, holds twelve US patents, received the best paper award in SIGMOD 2000 and ICDT 2013, the ACM PODS Alberto Mendelzon Test of Time Award in 2010 and in 2012, the 10 Year Most Influential Paper Award in ICDE 2013, the VLDB Ten Year Best Paper Award in 2014, and is a recipient of the NSF Career Award and of an Alfred P. Sloan Fellowship. Suciu serves on the VLDB Board of Trustees, and is an associate editor for the Journal of the ACM, VLDB Journal, ACM TWEB, and Information Systems and is a past associate editor for ACM TODS and ACM TOIS. Suciu's PhD students Gerome Miklau, Christopher Re and Paris Koutris received the ACM SIGMOD Best Dissertation Award in 2006, 2010, and 2016 respectively, and Nilesh Dalvi was a runner up in 2008.