Phokion Kolaitis (University of California Santa Cruz and IBM Research)
Abstract: 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 data exchange and integration, inconsistent databases, probabilistic databases, and voting with partial preferences.