Possible Worlds and Certain Answers
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.