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

General References
- A list of textbooks, monographs, and handbooks for background reading and reference.

Useful Links

ESSLLI 2021 Website

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.

Page updated

Report abuse