On the semantics of theory change: arbitration between old and new information

ABSTRACT

Katsuno and Mendelzon divide theory change, the problem of adding new information to a logical theory, into two types: revision and update. We propose a third type of theory change: arbitration. The key idea is the following: the new information is considered neither better nor worse than the old information represented by the logical theory. The new information is simply one voice against a set of others already incorporated into the logical theory. From this follows that arbitration should be commutative. First we define arbitration by a set of postulates and then describe a model-theoretic characterization of arbitration for the case of propositional logical theories. We also study weighted arbitration where different models of a theory can have different weights.

REFERENCES

• AG85: S. Abiteboul & G. Grahne. Update semantics for incomplete databases. Proceedings of the Eleventh International Conference on Very Large Databases, 1-12, 1985.
• ASV90: Serge Abiteboul , Eric Simon , Victor Vianu, Non-deterministic languages to express deterministic transformations, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.218-229, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298575]
• AGM85: C.E. Alchourr6n, P. G#rdenfors & D. Makinson. On the logic of theory change: partial meet contraction and revision functions. Journal of Symbolic Logic, (50) 510-530, 1985.
• BS81: F. Bancilhon , N. Spyratos, Update semantics of relational views, ACM Transactions on Database Systems (TODS), v.6 n.4, p.557-575, Dec. 1981 [doi>10.1145/319628.319634]
• Bor85: Alexander Borgida, Language features for flexible handling of exceptions in information systems, ACM Transactions on Database Systems (TODS), v.10 n.4, p.565-603, Dec. 1985 [doi>10.1145/4879.4995]
• Dal88: M. Dalai. Investigations into a theory of knowledge base revision: Preliminary report. Proceedings of the AAAI, pages 475-479, 1988.
• EG92: Thomas Eiter , Georg Gottlob, On the complexity of propositional knowledge base revision, updates, and counterfactuals, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.261-273, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137886]
• FUV83: Ronald Fagin , Jeffrey D. Ullman , Moshe Y. Vardi, On the semantics of updates in databases, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588100]
• Gär88: P. GKrdenfors. Knowledge in Fluz: Modeling the Dynamics of Epistemic States. Bradford Books, MIT Press, Cambridge, MA, 1988.
• GMR92: Gösta Grahne , Alberto O. Mendelzon , Peter Z. Revesz, Knowledgebase transformations, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.246-260, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137882]
• KW85: A.M. Keller & M. Winslett Wilkins. On the use of an extended relational model to handle changing incomplete information. IEEE Trans. on Software Engineering, 11:7, pages 620- 633, 1985.
• KM89: H. Katsuno & A. O. Mendelzon. A unified view of propositional knowledge base updates. Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, pages 1413-1419, 1989.
• KM91: H. Katsuno & A. O. Mendelzon. On the difference between updating a knowledge base and revising it. Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning, pages 387-394, 1991.
• KM91: Hirofumi Katsuno , Alberto O. Mendelzon, Propositional knowledge base revision and minimal change, Artificial Intelligence, v.52 n.3, p.263-294, Dec. 1991 [doi>10.1016/0004-3702(91)90069-V]
• KM92: H. Katsuno & A. O. Mendelzon. On the difference between updating a knowledge-base and revising it. manuscript.
• McC68: J. McCarthy. Programs with common sense. In: M. Minsky, (Ed.), Semantic Information Processing, M-IT Press, Cambridge, MA, pages 403-418, 1968.
• Mak85: D.Makinson. How to give it up: A survey of some formal aspects of the logic of theory change. Synth#se, (62) 347-363, 1985
• Rei92: It. Reiter. On specifying database updates. Proceedings of the Third In. ternational Conference on Eztending Database Technology, 1992.
• Rei78: R. Reiter. On closed world databases. In: Logic and Databases, H. Gallaire & J. Minker, editors. Plenum Press, New York, pages 55-76, 1978.
• Sat88: K. Satoh. Nonmonotonic reasoning by minimal belief revision. Proceedings International Conference on Fifth Generation Systems, pages 455-462, 1988.
• Web86: A. Weber. Updating propositional formulas. Proceedings First Conference on Ezpert Database Systems, pages 487-500, 1986.
• Win88: M. Winslett. Reasoning about action using a possible models approach. Proceedings of the Seventh National Conference on Artificial Intelligence, pages 89-93, 1988.
• Zad78: L.A. Zadeh. Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets and Systems, pages 3-28, 1978.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.3 Languages

          Nouns: SQL; Datalog

General Terms:
Algorithms, Languages, Theory, Verification