WINSLETT@SU-SCORE.ARPA (Marianne Winslett) (03/08/86)
Updating Databases With Incomplete Information --or-- Belief Revision is Harder Than You Thought Marianne Winslett PhD Oral Area X Seminar Margaret Jacks 352 Friday, March 14, 3:15 PM Suppose one wishes to construct, use, and maintain a database of knowledge about the real world, even though the facts about that world are only partially known. In the database domain, this situation arises when database users must coax information into and out of databases in the face of missing values and uncertainty. 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 the old set of beliefs. In the logic domain, one might choose to represent such a database as a logical theory, and view the models of the theory as possible states of the real world. How can new information (i.e., updates) be incorporated into the database? For example, given the new information that "b or c is true," how can we 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? The burden may be placed on the user or other omniscient authority to determine exactly which changes in the theory will bring about the desired set of models. But what's really needed is a way to specify an update intensionally, by stating some well-formed formula that the state of the world is now known to satisfy and letting the database management system automatically figure out how to accomplish that update. This talk will explore a technique for updating databases containing incomplete information. Our approach embeds the incomplete database and the updates in the language of first-order logic, which we believe has strong advantages over relational tables and traditional data manipulation languages when information is incomplete. We present semantics and algorithms for our update operators, and describe an implementation of the algorithms. This talk should be accessible to all who are comfortable with first-order logic and have a passing acquaintance with the notion of database updates. -------
tim@LINC.CIS.UPENN.EDU (Tim Finin) (03/06/87)
COLLOQUIUM Computer and Information Science University of Pennsylvania UPDATING DATABASES WITH INCOMPLETE INFORMATION Marianne Winslett Stanford University Computer Science Department 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 artificial intelligence 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 ``b 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 difficult and tedious burden of determining exactly what to add and remove from the database is placed on the user. The goal of our research was to relieve users of that burden, by equipping the database management system with update algorithms that can automatically determine what to add and remove from the database. Under our approach, new information about the state of the world is input to the database management system as a well-formed formula that the state of the world is now known to satisfy. We have constructed database update algorithms to interpret this update formula and incorporate the new information represented by the formula into the database without further assistance from the user. In this talk we will show how to embed the incomplete database and the incoming information in the language of mathematical logic, explain the semantics of our update operators, and discuss the algorithms that implement these operators. March 9, 1987 Room 216 Moore 3:00 to 4:30 Refreshments Available 2:30 to 3:00