Maintenance of Stratified Databases Viewed as a Belief Revision System.

@inproceedings{DBLP:conf/pods/AptP87,
  author    = {Krzysztof R. Apt and
               Jean-Marc Pugin},
  title     = {Maintenance of Stratified Databases Viewed as a Belief Revision
               System},
  booktitle = {Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, March 23-25, 1987, San Diego,
               California},
  publisher = {ACM},
  year      = {1987},
  isbn      = {0-89791-223-3},
  pages     = {136-145},
  ee        = {http://doi.acm.org/10.1145/28659.28674, db/conf/pods/AptP87.html},
  crossref  = {DBLP:conf/pods/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We study here declarative and dynamic aspects of non- monotonic reasoning in the context of deductive databases. More precisely, we consider here maintenance of a special class of indefinite deductive databases, called stratified databases, introduced in Apt, Blair and Walker [ABW] and Van Gelder [VG] in which recursion "through" negation is disallowed.

stratified database has a natural model associated with it which is selected as its intended meaning. The maintenance problem for these databases is complicated because insertions can lead to deletions and vice versa.

To solve this problem we make use of the ideas present in the works of Doyle [D] and de Kleer [dK] on belief revision systems. We offer here a number of solutions which differ in the amount of static and dynamic information used and the form of support introduced. We also discuss the implementation issues and the trade-offs involved.

Copyright © 1987 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.

• 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
• UNIX/LINUX/Mac: use mount point /pods8298/... 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
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[ABW]

...

[BMMSU]

François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 BibTeX

[CH]

Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX

[C]

...

[D]

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

[GMN]

Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984) BibTeX

[VG]

Allen Van Gelder: Negation as Failure Using Tight Derivations for General Logic Programs. SLP 1986: 127-138 BibTeX

[dK]

Johan de Kleer: An Assumption-Based TMS. Artif. Intell. 28(2): 127-162(1986) BibTeX

[L]

...

[LST]

...

[MC]

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

[MS]

...

[NY]

...

[Pu]

...

[Pr]

...

[S1]

John C. Shepherdson: Negation as Failure: A Comparison of Clark's Completed Data Base and Reiter's Closed World Assumption. J. Log. Program. 1(1): 51-79(1984) BibTeX

[S2]

John C. Shepherdson: Negation as Failure II. J. Log. Program. 2(3): 185-202(1985) BibTeX

[SS]

Richard M. Stallman, Gerald J. Sussman: Forward Reasoning and Dependency-Directed Backtracking in a System for Computer-Aided Circuit Analysis. Artif. Intell. 9(2): 135-196(1977) BibTeX

[TS]

...

[STZE]

...

Referenced by

1. Guozhu Dong, Jianwen Su: Incremental Maintenance of Recursive Views Using Relational Calculus/SQL. SIGMOD Record 29(1): 44-51(2000)
2. Guozhu Dong, Jianwen Su: Space-Bounded FOIES. PODS 1995: 139-150
3. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
   Contents
4. Guozhu Dong, Jianwen Su: First-Order Incremental Evaluation of Datalog Queries. DBPL 1993: 295-308
5. Guozhu Dong, Rodney W. Topor: Incremental Evaluation of Datalog Queries. ICDT 1992: 282-296
6. Ouri Wolfson, Hasanat M. Dewan, Salvatore J. Stolfo, Yechiam Yemini: Incremental Evaluation of Rules and its Relationship to Parallelism. SIGMOD Conference 1991: 78-87
7. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
   Contents
8. Serge Abiteboul: Updates, A New Frontier. ICDT 1988: 1-18