F-logic: a higher-order language for reasoning about objects, inheritance, and scheme

ABSTRACT

We propose a database logic which accounts in a clean declarative fashion for most of the “object-oriented” features such as object identity, complex objects, inheritance, methods, etc. Furthermore, database schema is part of the object language, which allows the user to browse schema and data using the same declarative formalism. The proposed logic has a formal semantics and a sound and complete resolution-based proof procedure, which makes it also computationally attractive.

REFERENCES

• 1: S. Abiteboul and C. Beeri. On the Power of Languages for Manipulation of Complex Objects. 1987. manuscript.
• 2: S. Abiteboul and S. Grumbach. COL" A Logic-Based Language for Complex Objects. In Workshop on Database Programming Languages, pages 253-276, Roscoff, France, September 1987.
• 3: 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]
• 4: 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]
• 5: 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]
• 6: C. Beeri, S. Naqvi, O. Shmueli, and S. Taut. Sets and Negation in a Logic Database Language (LDL). Technical Report, MCC, 1987.
• 7: C. Beeri, R. Nasr, and S. Taut. Embedding eterms in a Horn-clause Logic Language. In Third International Conference on Data and Knowledge Bases: Improving Usability and Responsiveness, pages 347-359, Morgan Kaufmann, 1988.
• 8: Peter Buneman , Achim Jung , Atsushi Ohori, Using powerdomains to generalize relational databases, Theoretical Computer Science, v.91 n.1, p.23-55, Dec. 9, 1991 [doi>10.1016/0304-3975(91)90266-5]
• 9: H. Ait-Kaci C. Zaniolo, D. Beech, S. Cammarata, L. Kerschberg, and D. Maier. Object-Oriented Database and Knowledge Systems. Technical Report DB-038-85, MCC, 1985.
• 10: Luca Cardelli, A semantics of multiple inheritance., Proc. of the international symposium on Semantics of data types, p.51-67, July 1984, Sophia-Antipolis, France
• 11: C.L. Chang and R.C.T. Lee. Symbolic Logic and Mechanical Theorem Proving. Academic Press, 1973.
• 12: W. Chen, M. Kifer, and D.S. Warren. HiLog: k First-Order Semantics for Higher-Order Logic Programming Constructs. In $-nd Intl. Workshop on Database Programming Languages, Morgan- Kaufmann, June 1989.
• 13: 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]
• 14: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 15: D.W. Etherington and R. Reiter. On Inheritance Hierarchies with Exceptions. In AAAI-83, pages 104-108, Washington, D.C., 1983.
• 16: 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]
• 17: M. L. Ginsberg, Multi-valued logics, Readings in nonmonotonic reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 18: P.J. Hayes. The Logic for Frames. In D. Metzing, editor, Frame Conception and Tezt Understanding, pages 46-61, Walter de Gruyter and Co., 1979.
• 19: 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
• 20: M. Kifer , J. Wu, A logic for object-oriented logic programming, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.379-393, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73758]
• 21: Ravi Krishnamurthy , Shamim A. Naqvi, Towards a Real Horn Clause Language, Proceedings of the 14th International Conference on Very Large Data Bases, p.252-263, August 29-September 01, 1988
• 22: 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]
• 23: G.M. Kuper. An Eztension of LPS to Arbitrary Sets. Technical Report, IBM, Yorktown Heights, 1987.
• 24: 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
• 25: 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
• 26: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 27: D. Maier. A Logic for Objects. In Workshop on Foundations of Deductive Databases and Logic Programming, pages 6-26, Washington D.C., August 1986.
• 28: D. Maier. Why Database Languages are a Bad Idea (position paper). In Proc. of the Workshop on Database Programming Languages, Roscoff, France, September 1987.
• 29: David Maier , Jacob Stein , Allen Otis , Alan Purdy, Development of an object-oriented DBMS, Conference proceedings on Object-oriented programming systems, languages and applications, p.472-482, September 29-October 02, 1986, Portland, Oregon, United States
• 30: D. Maier and D.S. Warren. A Theory of Computed Relations. Technical Report 80/12, Department of Computer Science, SUNY at Stony Brook, November 1980.
• 31: D. Maier and D.S. Warren. Incorporation Computed Relations in Relational Databases. Technical Report 80/17, Department of Computer Science, SUNY at Stony Brook, December 1980.
• 32: J. McCarthy. First Order Theories of Individual Concepts and Propositions. In :I.E. Hayes and D. Miehie, editors, Machine Inteligence, pages 129- 147, Edinburgh University Press, 1979.
• 33: M. Minsky. A Framework for Representing Knowledge. In J. Haugeland, editor, Mind design, pages 95-128, MIT Press, Cambridge, MA, 1981.
• 34: Amihai Motro, BAROQUE: a browser for relational databases, ACM Transactions on Information Systems (TOIS), v.4 n.2, p.164-181, April 1986 [doi>10.1145/6168.6172]
• 35: E. Neuhold and M. Stonebraker. Future Directions in DBMS Research. 1988. The Laguna Beech Report.
• 36: 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
• 37: Mark A. Roth , Henry F. Korth , Avi Silberschatz, Extended Algebra and Calculus for ~1NF Relational Databases, University of Texas at Austin, Austin, TX, 1984
• 38: G. Smolka and H. Ait-Kaei. inheritance Hierarchies: Semantics and Unification. Technical Report AI-057-87, MCC, May 1987.
• 39: Mark Stefik , Daniel Bobrow, Object-oriented programming: Themes and variations, AI Magazine, v.6 n.4, p.40-62, Winter 1986
• 40: David S. Touretzky, The mathematics of inheritance systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1986
• 41: D.S. Touretzky, J.F. ttorty, and R.H. Thornsson. A Clash of Intuitions: The Current State of Nonmonotonie Multiple inheritance Systems. In IJCAI-87, pages 476-482, 1987.
• 42: Vbase Object Manager. Ontologie, Inc., 1986. User Manual.
• 43: P. Wegner. The Object-Oriented Classification Paradigm. 1987. manuscript.
• 44: Darrell Woelk , Won Kim, Multimedia Information Management in an Object-Oriented Database System, Proceedings of the 13th International Conference on Very Large Data Bases, p.319-329, September 01-04, 1987

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Specialized application languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.3 Languages
          Subjects: Data description languages (DDL)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Semantic networks

General Terms:
Algorithms, Languages, Verification