Method schemas

ABSTRACT

The concept of method schemas is proposed as a simple model for object-oriented programming with features such as classes with methods and inheritance, method name overloading, and late binding. An important issue is to check whether a given method schema can possibly lead to inconsistencies in some interpretations. The consistency problem for method schemas is studied. The problem is shown to be undecidable in general. Decidability is obtained for monadic and/or recursion-free method schemas. The effect of covariance is considered. The issues of incremental consistency checking and of a sound algorithm for the general case are briefly discussed.

REFERENCES

• 1: Serge Abiteboul , Paris C. Kanellakis, Object identity as a query language primitive, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.159-173, June 1989, Portland, Oregon, United States
• 2: Edward Ashcroft , Zohar Manna , Amir Pnueli, Decidable Properties of Monadic Functional Schemas, Journal of the ACM (JACM), v.20 n.3, p.489-499, July 1973 [doi>10.1145/321765.321780]
• 3: 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]
• 4: F. Bancilhon , G. Barbedette , V. Benzaken , C. Delobel , S. Gamerman , C. Lecluse , P. Pfeffer , P. Richard , F. Velez, The design and implementation of O2, Lecture notes in computer science on Advances in object-oriented database systems, p.1-22, September 1988, Bad Mu:9Ainster am Stein-Edernburg, Germany
• 5: Jay Banerjee , Hong-Tai Chou , Jorge F. Garza , Won Kim , Darrell Woelk , Nat Ballou , Hyoung-Joo Kim, Data model issues for object-oriented applications, ACM Transactions on Information Systems (TOIS), v.5 n.1, p.3-26, Jan. 1987 [doi>10.1145/22890.22945]
• 6: Jay Banerjee , Won Kim , Hyoung-Joo Kim , Henry F. Korth, Semantics and implementation of schema evolution in object-oriented databases, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.311-322, May 27-29, 1987, San Francisco, California, United States
• 7: A. Borgida, Type systems for querying class hierarchies with non-strict inheritance, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.394-400, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73759]
• 8: S.A. Cook. Linear-time Simulation of Deterministic Two-way Pushdown Automata. Proc. IFIP Congress, 172-179, 1971.
• 9: J. E. Doner. Tree Acceptors and some of their Applications. JCSS, 4:406-451, 1971.
• 10: D. Fishman et al. Iris" an Object-Oriented Database Management System. A CM TOIS, 5:1:46-69, 1987.
• 11: Sheila A. Greibach, Theory of Program Structures: Schemes, Semantics, Verification, Springer-Verlag New York, Inc., Secaucus, NJ, 1985
• 12: R. Hull, private communication, June 1989.
• 13: Richard Hull , Jianwen Su, On accessing object-oriented databases: expressive power, complexity, and restrictions, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.147-158, June 1989, Portland, Oregon, United States
• 14: R. Hull , K. Tanaka , M. Yoshikawa, Behavior analysis of object-oriented databases: method structure, execution trees and reachability, 3rd International Conference, FODO 1989 on Foundations of Data Organization and Algorithms, p.372-388, July 1989, Paris, France
• 15: D. C. Luckham, D. M. R. Park, M. S. Paterson. On Formalized Computer Programs. JCSS, 4:220-249, 1970.
• 16: D. Maier, A. Otis, and A. Purdy. Development of an Object-Oriented Dbms. Bulletin of IEEE on Database Engineering, 1985.
• 17: Andrea H. Skarra , Stanley B. Zdonik, Type evolution in an object-oriented database, Research directions in object-oriented programming, MIT Press, Cambridge, MA, 1987
• 18: M. Y. Vardi, Invited talk: automata theory for database theoreticians, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.83-92, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73729]
• 19: E. Waller, Vdrification de type en presence d'h~ritage et de surcharge, DEA, Orsay, 1989.
• 20: S. Zdonik. Object Management Systems for Design Environments. Bulletin of IEEE on Database Engineering, 1985.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

General Terms:
Algorithms, Design, Languages, Management, Performance, Theory