Distinguished Lecture - Phokion Kolaitis: The Query Containment Problem: Set Semantics vs. Bag Semantics

Abstract:

Query containment is a fundamental algorithmic task in database query processing and optimization. Under set semantics, the query-containment problem for conjunctive queries has long been known to be NP-complete.  SQL queries, however, are typically evaluated under bag semantics and return multisets (bags) as answers, since duplicates are not eliminated unless explicitly specified. The exact complexity of the query-containment problem for conjunctive queries under bag semantics has been an outstanding problem for more than twenty-five years. To this date, it is not even known whether conjunctive-query containment under bag semantics is decidable.

The aim of this talk is to present a comprehensive overview of results about the query-containment problem for conjunctive queries and their variants under bag semantics, including recent results that reveal tight connections between this problem and open problems in information theory.

Short Bio:

Phokion Kolaitis is a Distinguished Professor at the University of California Santa Cruz and a Principal Research Staff Member at the IBM Almaden Research Center. His research interests include principles of database systems, logic in computer science, and computational complexity.

Kolaitis is a Fellow of the American Association for the Advancement of Science (AAAS), a Fellow of the Association for Computing Machinery, a Foreign Member of the Finnish Academy of Science and Letters, a Foreign Member of Academia Europaea, and the recipient of a 1993 Guggenheim Fellowship. He is also the recipient of two IBM Research Division Outstanding Innovation Awards, an IBM Research Division Outstanding Technical Achievement Award, a co-winner of both the 2008 and the 2014 ACM PODS Alberto O. Mendelzon Test-of-Time Award, and a co-winner of the 2013 International Conference on Database Theory Test-of-Time Award.