A Model-Based Approach to Updating Databases with Incomplete Information.

@article{DBLP:journals/tods/Winslett88,
  author    = {Marianne Winslett},
  title     = {A Model-Based Approach to Updating Databases with Incomplete
               Information},
  journal   = {ACM Trans. Database Syst.},
  volume    = {13},
  number    = {2},
  year      = {1988},
  pages     = {167-196},
  ee        = {http://doi.acm.org/10.1145/42338.42386, db/journals/tods/Winslett88.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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 paper we 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.

Copyright © 1988 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[1]

Serge Abiteboul, Gösta Grahne: Update Semantics for Incomplete Databases. VLDB 1985: 1-12 BibTeX

[2]

François Bancilhon, Nicolas Spyratos: Update Semantics of Relational Views. ACM Trans. Database Syst. 6(4): 557-575(1981) BibTeX

[3]

...

[4]

Keith L. Clark: Negation as Failure. Logic and Data Bases 1977: 293-322 BibTeX

[5]

E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX

[6]

James Davidson: A Natural Language Interface for Performing Database Updates. ICDE 1984: 69-76 BibTeX

[7]

Umeshwar Dayal, Philip A. Bernstein: On the Correct Translation of Update Operations on Relational Views. ACM Trans. Database Syst. 7(3): 381-416(1982) BibTeX

[8]

Johan de Kleer, Brian C. Williams: Diagnosing Multiple Faults. Artif. Intell. 32(1): 97-130(1987) BibTeX

[9]

Jon Doyle: A Truth Maintenance System. Artif. Intell. 12(3): 231-272(1979) BibTeX

[10]

Ronald Fagin, Gabriel M. Kuper, Jeffrey D. Ullman, Moshe Y. Vardi: Updating Logical Databases. Advances in Computing Research 3: 1-18(1986) BibTeX

[11]

Ronald Fagin, Jeffrey D. Ullman, Moshe Y. Vardi: On the Semantics of Updates in Databases. PODS 1983: 352-365 BibTeX

[12]

Matthew L. Ginsberg: Counterfactuals. Artif. Intell. 30(1): 35-79(1986) BibTeX

[13]

Stephen J. Hegner: Specification and Implementation of Programs for Updating Incomplete Information Databases. PODS 1987: 146-158 BibTeX

[14]

Tomasz Imielinski, Witold Lipski Jr.: Incomplete Information in Relational Databases. J. ACM 31(4): 761-791(1984) BibTeX

[15]

Arthur M. Keller: Updates to Relational Databases Through Views Involving Joins. JCDKB 1982: 363-384 BibTeX

[16]

...

[17]

Vladimir Lifschitz: Closed-World Databases and Circumscription. Artif. Intell. 27(2): 229-235(1985) BibTeX

[18]

John McCarthy: Circumscription - A Form of Non-Monotonic Reasoning. Artif. Intell. 13(1-2): 27-39(1980) BibTeX

[19]

Ryszard S. Michalski, Patrick H. Winston: Variable Precision Logic. Artif. Intell. 29(2): 121-146(1986) BibTeX

[20]

Nils J. Nilsson: Probabilistic Logic. Artif. Intell. 28(1): 71-87(1986) BibTeX

[21]

Raymond Reiter: Equality and Domain Closure in First-Order Databases. J. ACM 27(2): 235-249(1980) BibTeX

[22]

...

[23]

...

[24]

Raymond Reiter: A Theory of Diagnosis from First Principles. Artif. Intell. 32(1): 57-95(1987) BibTeX

[25]

...

[26]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

[27]

Yannis Vassiliou: Null Values in Data Base Management: A Denotational Semantics Approach. SIGMOD Conference 1979: 162-169 BibTeX

[28]

Andreas Weber: Updating Propositional Formulas. Expert Database Conf. 1986: 487-500 BibTeX

[29]

...

[30]

Marianne Winslett: A Model-Theoretic Approach to Updating Logical Databases. PODS 1986: 224-234 BibTeX

[31]

Marianne Winslett: Updating Logical Databases Containing Null Values. ICDT 1986: 421-435 BibTeX

[32]

...

[33]

...

[34]

Carlo Zaniolo: Database Relations with Null Values. PODS 1982: 27-33 BibTeX

Referenced by

1. Julie Wilks: Querying and Updating Constraint Databases with Incomplete Information. ADBIS 1997: 80-89
2. Jui-Shang Chiu, Arbee L. P. Chen: An Exploration of Relationships Among Exclusive Disjunctive Data. IEEE Trans. Knowl. Data Eng. 7(6): 928-940(1995)
3. Dominique Laurent, Viet Phan Luong, Nicolas Spyratos: Updating Intensional Predicates in Deductive Databases. ICDE 1993: 14-21
4. Anthony J. Bonner, Michael Kifer, Mariano P. Consens: Database Programming in Transaction Logic. DBPL 1993: 309-337