Maintenance of stratified databases viewed as a belief revision system

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. A 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.

REFERENCES

• ABW: K. R. Apt , H. A. Blair , A. Walker, Towards a theory of declarative knowledge, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• BMSU: Francois Bancilhon , David Maier , Yehoshua Sagiv , Jeffrey D Ullman, Magic sets and other strange ways to implement logic programs (extended abstract), Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.1-15, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15399]
• CH: Chandra, A and Harel, D, 'Horn Clause Queries and Generahzauons", Journal of Logic Programming, vol 1, pp 1-15, 1985
• C: Cousot, P, "Asynchronous Iterattve Methods For Solving a Fixed Pomt System of Monotone Equauons m a Complete LatUce",Rapport de Recherche N 88, L A 7, Umv Sclenufique et Medlcale de Grenoble, 1977
• D: Do)le, J, "A Truth Mamtenance System", Art~ficml lntelhgence 12, pp 231-272, 1979
• GMN: Herve Gallaire , Jack Minker , Jean-Marie Nicolas, Logic and Databases: A Deductive Approach, ACM Computing Surveys (CSUR), v.16 n.2, p.153-185, June 1984 [doi>10.1145/356924.356929]
• VG: Van Gelder, A, "Negauon as Fmlure Using T~ght Denvauons for General Logic Programs", in Proc Thud IEEE S ymposmm on Logic Programming, Salt Lake City, Utah, 1986
• dK: Johan de Kleer, An assumption-based TMS, Artificial Intelligence, v.28 n.2, p.127-162, March 1986 [doi>10.1016/0004-3702(86)90080-9 ]
• L: Lffschltz, V, "On the Declarauve SemanUcs of Logic Programs w~th Negatmn", m Proc Workshop on Foundations of DeducUve Databases and Logzc Programming, Washington D C, pp 420- 432, 1986
• LST: Lloyd, J W, Sonenberg, E A and Topor, R, "integrity Constraint Checkang m Stmufied D-a,,~t ~ses', Techmcal Report 86/5, Dept of Computer Science, Un,, of Melbourne, 1986
• MC: McCarthy, J, "Ca'cumscnptton - A Form of Non-monotonic Reasoning", Aruficml Intelhgence 13, pp 295-323, 1980
• MS: Martins, J P, and Shapwo, S C, "Reasomng m Mullaple Belief Spaces", m Proc IJCAI-83, pp 370-373, 1983
• NY: Nicolas, J-M, and Yazdanlan, K, "An Outhne of BDGEN a Deducuve DBMS", m Proc IFIP- 83,pp 711-717, 1983
• Pu: Pugm, J-M, "BOUM Manuel de reference et d'uuhsat~on", Rapport Interne du Centre de Recherche BULL, 1984
• Pr: Przymusmsk~, T, "On the Semanucs of Strattfied Deducuve Databases", m Proc Workshop on Foundattons of Deducttve Databases and Logzc Programming, Washington D C, pp 433-443, 1986
• S1: John C. Shepherdson, Negation as failure: a comparison of Clark's completed data base and Reiter's closed world assumption, Journal of Logic Programming, v.1 n.1, p.51-79, June 1984 [doi>10.1016/0743-1066(84)90023-2 ]
• S2: John C. Shepherdson, Negation as failure. II, Journal of Logic Programming, v.2 n.3, p.185-202, Oct. 1985 [doi>10.1016/0743-1066(85)90018-4 ]
• SS: Stallman, R M and Sussman, G J, "Forward Reasoning and Dependency-Dtrected Backtracking m a System for Computer-A~ded Ctrcmt Analysis", Aruficml Intelhgence 9, pp 135-196, 1977
• TS: R. W. Topor , E. A. Sonenberg, On domain independent databases, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• STZE: Shmueh, O, Tsar, S, Zfira, H, and Ever-Had,ant, R, "Dynamic Rule Support m Prolog", Manuscript, 1985

INDEX TERMS

Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Nonmonotonic reasoning and belief revision

General Terms:
Design, Management, Theory