NOL Seminar with Phokion Kolaitis
published: 2025-12-01
event date:
2025-12-15
The Nordic Online Logic Seminar
is organised monthly over Zoom, with expository talks on topics of interest for
the broader logic community. The seminar is open for professional or aspiring
logicians and logic aficionados worldwide. If you wish to receive the Zoom ID
and password for it, as well as further announcements, please subscribe here:
https://listserv.gu.se/sympa/subscribe/nordiclogic
Date Monday, 15 December 2025 at 16:00 CET (UTC+1) on Zoom
Speaker Phokion Kolaitis (Distinguished Research Professor, UC Santa Cruz and Principal Research Staff Member, IBM Almaden Research Center)
Title Possible Worlds and Certain Answers
Abstract
Databases are typically assumed to have definite content so that users can pose
queries and retrieve unambiguous answers. It is often the case, however, that a
database may contain information that is incomplete, inconsistent, or uncertain.
Possible world semantics provides meaning to logic-based queries on databases
suffering from these deficiencies. Such databases are viewed as compact
representations of all their possible rectifications; by definition, the certain
answers are the query answers that hold true in every possible rectification of
a deficient database.
The goal of this lecture is to provide an overview of some of the work on certain answers as a unifying framework for coping with incompleteness, inconsistency, and uncertainty in databases. Case studies include inconsistent databases, probabilistic databases, and election databases in social choice theory.