Logic, Data,
and
Incomplete Information
Instructor: Phokion G. Kolaitis
University of California Santa Cruz and IBM Research
email: kolaitis@ucsc.edu; web: https://users.soe.ucsc.edu/~kolaitis/
Dates: July 26 - July 30, 2021; Time: 16:00-17:30 (CEST)
ESSLLI 2021 Daily Schedule (including room information)
Course Description
During the past fifty years, first-order logic and its variants have been successfully used as a database query language. In traditional applications, the data at hand are assumed to be unambiguous and consistent, which implies that queries (specified in some logical formalism) are posed on a well-defined complete and consistent database. In more recent applications, however, the data may be incomplete, inconsistent, or uncertain. This state of affairs necessitates the introduction and study of the certain answers of database queries, which is an alternative semantics that takes the incompleteness, inconsistency, or uncertainty of the data into account. The aim of this course is to examine the semantics and the algorithmic aspects of the certain answers to queries in four different such contexts, namely, in the contexts of inconsistent databases, data exchange, probabilistic databases, and voting with partial preferences.
Tentative Outline
Theme 1: Overview of Database Query Languages and Complexity
The relational data model; first-order logic as a database query language; conjunctive queries and unions of conjunctive queries; the query evaluation problem; data complexity and combined complexity; algorithmic aspects of conjunctive query evaluation.
Theme 2: Inconsistent Databases and Consistent Answers
Managing inconsistency in databases using logic; integrity constraints and database repairs; consistent answers of queries; trichotomy theorems for the computational complexity of the consistent answers of conjunctive queries.
Theme 3: Data Exchange, Schema Mappings, and Certain Answers
Database dependencies and schema mappings; solutions and universal solutions in data exchange and data integration; certain answers and possible answers of queries in data exchange and data integration; algorithmic aspects of the certain answers of conjunctive queries in data exchange and data integration.
Theme 4: Probabilistic Databases and Query Answering
Modeling uncertainty in data using probabilistic databases; the tuple-independence model for probabilistic databases; semantics of queries on probabilistic databases; dichotomy theorems for the computational complexity of conjunctive-query evaluation on probabilistic databases.
Theme 5: Voting with Partial Preferences, Necessary and Possible Winners
Social choice and voting rules; modeling incomplete information about voting preferences using partial orders; necessary winners and possible winners; enriching voting with relational database context; necessary answers and possible answers to queries on election databases, and their computational complexity.
Slides of Lectures and References
Slides - Final Version
References
A list of textbooks, monographs, and handbooks for background reading and reference.
Phokion Kolaitis is a Distinguished Research 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. For additional information, please visit his personal website.