Knowledgebase transformations

ABSTRACT

We propose a language that expresses uniformly queries and updates on knowledgebases consisting of finite sets of relational structures. The language contains an operator that “inserts” arbitrary first-order sentences into knowledgebase. The semantics of the insertion is based on the notion of update formalized by Katsuno and Mendelzon in the context of belief revision theory. Our language can express, among other things, hypothetical queries and queries on recursively indefinite databases. The expressive power of our language lies between existential second-order and general second-order queries. The data complexity is in general within exponential time, although it can be lowered to co-NP and to polynomial time by restricting the form of queries and updates.

REFERENCES

• AbG85: S. Abiteboul & G. Grahne. Update semantics for incomplete databases. In" Proceedings of the 11th International Conference on Very Large Databases, pages 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. Yournal of Symbolic Logic, (50) 510-530, 1985.
• ABW88: 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
• 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]
• Bon88: A. J. Bonner, Hypothetical datalog: complexity and expressibility, Lecture notes in computer science on ICDT '88, p.144-160, October 1988, Bruges, Belgium
• CH82: A.K. Chandra ~# D. Harel. Structure and complexity of relational queries. Journal of Computer and System Sciences, (25) 99-28, 1982.
• 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]
• Fre91: Karen A. Frenkel, The human genome project and informatics, Communications of the ACM, v.34 n.11, p.40-51, Nov. 1991 [doi>10.1145/125490.125492]
• 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]
• Gab85: D.M. Gabbay. N-Prolog: an extension of Prolog with hypothetical implications. II. Logical foundations and negation as failure. Journal of Logic Programming. (2) 251-283, 1985.
• Gär86: P. Ggrdenfors. Belief revisions and the Ramsey test for conditionals. The Philosophical Review, (95) 81-93, 1986.
• Gär88: P. G~rdenfors. Knowledge in Flux: Modeling the Dynamics of Epistemic States. Bradford Books, MIT Press, Cambridge, MA, 1988.
• Gra91: G. Grahne. Updates and counterfactu- Ms. In: Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning, pages 269-276, 1991.
• GM91: G. Grahne & A. O. Mendelzon. Updates and subjunctive queries. In ~ 1#. Demolombe, T. Imielinski L. Farifias del Cerro (Eds.), Workshop on Nonstandard Queries and Answers, pages 33-52, 1991.
• HV91: J. Halpern & M. Y. Vardi. Model checking vs. theorem proving: a manifesto. In: Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning, pages 325-334, 1991.
• IN88: Tomasz Imielinski , Shamim Naqvi, Explicit control of logic programs through rule algebra, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.103-116, March 1988, Austin, Texas, United States [doi>10.1145/308386.308422]
• Kan90: Paris C. Kanellakis, Elements of relational database theory, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• KM91a: H. Katsuno #z A. O. Mendelzon. On the difference between updating a knowledge base and revising it. In: Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning, pages 387-394, 1991.
• KM91b: 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]
• LM81: E.W. Leggett Jr. # D. J. Moore. Optimization problems and the polynomial hierarchy. Theoretical Computer Science, (15) 279-289, 1981.
• 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
• McC68: J. McCarthy. Programs with common sense. In: M. Minsky, (Ed.), Semantic Information Processing, MIT Press, Cambridge, MA, 1968, pages 403-418.
• McC80: J. McCarthy. Circumscription a form of non-monotonic reasoning. Artificial Intelligence, (13) 27-39, 1980.
• Mey90: R. van der Meyden, Recursively indefinite databases (extended abstract), Proceedings of the third international conference on database theory on Database theory, p.364-378, November 1990, Paris, France
• Min82: Jack Minker, On Indefinite Databases and the Closed World Assumption, Proceedings of the 6th Conference on Automated Deduction, p.292-308, June 07-09, 1982
• Rei78: R. Reiter. On closed world databases. In: H. Gallaire & J. Minker, (Eds.), Logic and Databases, Plenum Press, New York 1978, pages 55-76.
• Rei84: R. Reiter. Towards a logical reconstruction of relational database theory. In: M. L. Brodie, J. Mylopoulos, & J. W. Schmidt, (Eds.), On Conceptual Modelling, $pringer-Verlag, New York 1984# pages 191-233.
• Rei92: R. Reiter. On specifying database updates. In: Proceedings of the Third International Conference on Extending Database Technology, to appear in 1992.
• Var82: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
• Win89: M. Winslett. Reasoning about action using a possible models approach. In: Proceedings of the Seventh National Conference on Artificial Intelligence, pages 89-93, 1988.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Languages, Theory