A logic for object-oriented logic programming

ABSTRACT

We present a logic for reasoning about complex objects, which is a revised and significantly extended version of Maier's O-logic [Mai86]. The logic naturally supports complex objects, object identity, deduction, is tolerant to inconsistent data, and has many other interesting features. It elegantly combines the object-oriented and value-oriented paradigms and, in particular, contains all of the predicate calculus as a special case. Our treatment of sets is also noteworthy: it is more general than ELPS [Kup87] and COL [AbG87], yet it avoids the semantic problems encountered in LDL [BNS87]. The proposed logic has a sound and complete resolution-based proof procedure.

REFERENCES

• AbB87: S. Abiteboul and C. Beeri, "On the Power of Languages for Manipulation of Complex Objects", unpublished manuscript, 1987.
• AbG87: S. Abiteboul and S. Grumbach, "COL: A Logic-Based Language for Complex Objects", Workshop on Database Programming Languages, Roscoff, France, Sept. 1987, 253-276.
• AiN86: H Aït-Kaci , R Nasr, Login: A logic programming language with built-in inheritance, Journal of Logic Programming, v.3 n.3, p.185-215, Oct. 1986 [doi>10.1016/0743-1066(86)90013-0]
• BaK86: Francois Bancilhon , Setrag Khoshafian, A calculus for complex objects, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.53-60, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15404]
• Ban86: F. Bancilhon, "A Logic- Programming/Object-Oriented Cocktail", Proc. of the A CM-SIGMODIntl. Conf. on Management of Data Record, Sept. 1986.
• Ban88: François Banciihon, Object-oriented database systems, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.152-162, March 1988, Austin, Texas, United States [doi>10.1145/308386.308429]
• BNS87: C. Beeri, S. Naqvi, O. Shmueli and S. Tsur, "Sets and Negation in a Logic Database Language (LDL)", MCC Report, 1987.
• Bee88: C. Beeri, Data models and languages for databases, Lecture notes in computer science on ICDT '88, p.19-40, October 1988, Bruges, Belgium
• BNT88: C. Beeri, R. Nasr and S. Tsur, "Embedding qJ-Terms in a Horn-Clause Logic Language", MCC Tech. Rep.# ACA-ST-050-88, January 1988.
• Bel75: N. D. Belnap, "A Useful Four-Valued I, ogic", in Modern Uses of Multiple-Valued Logic, J. M. Dunn and G. Epstein, (eds.), D. Reidel Publishing Co., 1975.
• Bel76: N.D. Belnap, "How a ConLputer Should Think", in Contemporary Aspects of Philosophy, G. Ryle, (ed.), Oriel Press, 1976, 30-56.
• BlS87: Howard A. Blair , V. S. Subrahmanian, Paraconsistent logic programming, Proc. of the seventh conference on Foundations of software technology and theoretical computer science, p.340-360, December 1987, Pune, India
• ChL73: Chin-Liang Chang , Richard C. Lee , Richard Char-Tung Lee, Symbolic Logic and Mechanical Theorem Proving, Academic Press, Inc., Orlando, FL, 1997
• ChW89: W. Chen , D. S. Warren, C-logic of complex objects, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.369-378, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73757]
• Fag82: Ronald Fagin, Horn clauses and database dependencies, Journal of the ACM (JACM), v.29 n.4, p.952-985, Oct. 1982 [doi>10.1145/322344.322347]
• FiK85: Richard Fikes , Tom Kehler, The role of frame-based representation in reasoning, Communications of the ACM, v.28 n.9, p.904-920, Sept. 1985 [doi>10.1145/4284.4285]
• Fit88: M. Fitting, "Bilattices and the Semantics of Logic Programming", manuscript, July, 1988.
• GaJ78: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• Gin87: M. L. Ginsberg, Multi-valued logics, Readings in nonmonotonic reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• GyV88: M. Gyssens and D. Van Gucht, "The powerset Operator as an Algebraic Tool for Understanding Least Fixpoint Semantics in the Context of Nested Relations", Proc. of the A CM-SIGMOD Intl. Conf. on Management of Data, 1988.
• Hay79: P.J. Hayes, "The Logic of Frames", in Frame Conception and Test Understanding, D. Metzing, (ed.), Walter de Gruyter and Co., 1979, 46-61.
• Hul87: R. Hull, A survey of theoretical research on typed complex database objects, Databases, Academic Press Ltd., London, UK, 1988
• KhC86: Setrag N. Khoshafian , George P. Copeland, Object identity, Conference proceedings on Object-oriented programming systems, languages and applications, p.406-416, September 29-October 02, 1986, Portland, Oregon, United States
• Kif88: M. Kifer, "On Safety, Domai,~ Independence, and Capturability of Database Queries", 3-d Int. Conference on Data and Knowledge Bases, Jerusalem, israel, June 1988, 405-415.
• KiL88a: M. Kifer and G. Lausen, "F-Logic-A "Higher-Order" Logic for Reasoning about Objects, Inheritance, and Schema , submitted for publication, Dec. 1988.
• KiL88b: M. Kifer , A. Li, On the semantics of rule-based expert systems with uncertainty, Lecture notes in computer science on ICDT '88, p.102-117, October 1988, Bruges, Belgium
• KiL89: M. Kifer , E. Lozinskii, RI: A logic for reasoning with inconsistency, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.253-262, June 1989, Pacific Grove, California, United States
• KuV84: Gabriel M. Kuper , Moshe Y. Vardi, A new approach to database logic, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588026]
• Kup87: G.M. Kuper, "An Extension of LPS to Arbitrary Sets", IBM Research Report, 1987.
• LRV88: C. Lecluse , P. Richard , F. Velez, O2, an object-oriented data model, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.424-433, June 01-03, 1988, Chicago, Illinois, United States
• LeR88: C. Lécluse , P. Richard, Modeling inheritance and genericity in object-oriented databases, Lecture notes in computer science on ICDT '88, p.223-238, October 1988, Bruges, Belgium
• Llo87: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• Mai86: D. Mater, "A Logic for Objects", Proc. of the Workshop on Foundations of Deductive Databases and Logic Programming, Washington D.C., Aug. 1986, 6-26.
• Prz88: T. C. Przymusinski, On the declarative semantics of deductive databases and logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• RKS85: Mark A. Roth , Henry F. Korth , Avi Silberschatz, Extended Algebra and Calculus for ~1NF Relational Databases, University of Texas at Austin, Austin, TX, 1984
• Rub87: Henryk Rybiński, On first-order-logic databases, ACM Transactions on Database Systems (TODS), v.12 n.3, p.325-349, Sept. 1987 [doi>10.1145/27629.27630]
• San85: E. Sandewall, "A Functional Approach to Non-Monotonic Logic", IJCAI-85, 1985, 100-106.
• STZ88: Oded Shmueli , Shalom Tsur , Carlo Zaniolo, Rewriting of rules containing set terms in a logic data language LDL, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.15-28, March 1988, Austin, Texas, United States [doi>10.1145/308386.308400]
• StB86: Mark Stefik , Daniel Bobrow, Object-oriented programming: Themes and variations, AI Magazine, v.6 n.4, p.40-62, Winter 1986
• Ull87: J. D. Ullman, Database theory—past and future, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-10, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28660]
• Ull88: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• VRS88: Allen Van Gelder , Kenneth Ross , John S. Schlipf, Unfounded sets and well-founded semantics for general logic programs, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.221-230, March 1988, Austin, Texas, United States [doi>10.1145/308386.308444]
• Var81: M.Y. Vardi, "The Decision Problem for Database Dependencies", Information Processing Letters, Oct. 1981, 251-254.
• Weg87: P. Wegner, "The Object-Oriented. . Classification Paradigm", manuscript, 1987.
• ZAB85: C. Zaniolo, H. Ait-Kaci, D. Beech, S. Cammarata, L. Kerschberg and D. Mater, "Object Oriented Database Systems and Knowledge Systems", MCC Tech. Rep.# DB-038-85, MCC, 1985.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs
          Subjects: Logics of programs

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Design, Languages, Theory