Updating databases with incomplete information
Marianne Winslett · 1987
Suppose one wishes to construct, use, and maintain a database of facts about the real world, even though the state of that world is only partially known. In the AI domain, this problem arises when an agent has a base set of beliefs that reflect partial knowledge about the world, and then tries to incorporate new, possibly contradictory knowledge into this set of beliefs. In the database domain, one facet of this situation is the well-known null values problem. We choose to represent such a database as a logical theory, and view the models of the theory as representing possible states of the world that are consistent with all known information. How can new information be incorporated into the database? For example, given the new information that or c is true, how can one get rid of all outdated information about b and c, add the new information, and yet in the process not disturb any other information in the database? In current-day database management systems, the burden of determining exactly what to add and remove from the database is placed on the user. Our research has produced a formal method of specifying the desired change intensionally, by stating a well-formed formula that the state of the world is now known to satisfy. The database update algorithms we provide will automatically accomplish that change. Our approach embeds the incomplete database and the incoming information in the language of mathematical logic, and gives formal definitions of the semantics of our update operators, along with proofs of correctness for their associated algorithms. We assess the computational complexity of the algorithms, and propose a means of lazy evaluation to avoid undesirable expense during execution of updates. We also examine means of enforcing integrity constraints as the database is updated. This thesis also examines the question of choices of semantics for update operators for databases with incomplete information, and proposes a framework for evaluation of competing candidate semantics. Several candidate semantics are evaluated with respect to that framework. A experimental implementation of our method has been constructed, and we include the results of test runs on a range of patterns of queries and updates.