Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site ucbvax.BERKELEY.EDU
Path: utzoo!decvax!decwrl!pyramid!pesnta!hplabs!ucbvax!su-score.arpa!WINSLETT
From: WINSLETT@SU-SCORE.ARPA (Marianne Winslett)
Newsgroups: mod.ai
Subject: Seminar - Updating Databases with Incomplete Information (SU)
Message-ID: <12188926618.35.WINSLETT@SU-SCORE.ARPA>
Date: Fri, 7-Mar-86 20:33:40 EST
Article-I.D.: SU-SCORE.12188926618.35.WINSLETT
Posted: Fri Mar  7 20:33:40 1986
Date-Received: Tue, 11-Mar-86 08:47:40 EST
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The ARPA Internet
Lines: 48
Approved: ailist@sri-ai.arpa


         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.

-------