Type systems for querying class hierarchies with non-strict inheritance

ABSTRACT

Type checking at query compilation time is important for both detecting programmer errors and reducing the running time of queries. We have argued elsewhere [2] that entity-based data management systems which support class hierarchies, such as semantic data models and object-oriented dbms, should not be confined to have “strict inheritance” — i.e., they should permit contradictions between class specifications, albeit in an explicit and controlled way. In this paper we present a type system for queries manipulating objects in such classes. We provide sound and complete axiomatizations of the predications “&sgr; is a subtype of &tgr;” and “expression e has type &tgr;”. The absence of strict inheritance has normally been felt to preclude effective type checking. We show that the problem is co-NP-hard when disjoint types are admitted in the schema, but present a low-order polynomial-time algorithm that determines the absence of type errors in a query when the database has only entities.

REFERENCES

• 1: Antonio Albano , Luca Cardelli , Renzo Orsini, GALILEO: a strongly-typed, interactive conceptual language, ACM Transactions on Database Systems (TODS), v.10 n.2, p.230-260, June 1985 [doi>10.1145/3857.3859]
• 2: A. Borgida, Modeling class hierarchies with contradictions, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.434-443, June 01-03, 1988, Chicago, Illinois, United States
• 3: 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
• 4: Frank Manola , Umeshwar Dayal, PDM: an object-oriented data model, Proceedings on the 1986 international workshop on Object-oriented database systems, p.18-25, September 23-26, 1986, Pacific Grove, California, United States
• 5: Dowling, W. and Gallier, J. Linear-time algorithms for testing the satisfiability of propositional Horn formulae. J. Logic Programming 3:267-284, 1984.
• 6: Etherington,D. and Reiter, R.. On inheritance hierarchies with exceptions. In Proceedings of AAAI-83. 1983.
• 7: John Mylopoulos , Philip A. Bernstein , Harry K. T. Wong, A language facility for designing database-intensive applications, ACM Transactions on Database Systems (TODS), v.5 n.2, p.185-207, June 1980 [doi>10.1145/320141.320150]
• 8: Atsushi Ohori , Peter Buneman, Type inference in a database programming language, Proceedings of the 1988 ACM conference on LISP and functional programming, p.174-183, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62700]
• 9: Pxatt, V. ~onear-optimal method for reasoning about action. umal of Computer Systems Science 20(1 ):231-254, 1980.
• 10: David W. Shipman, The functional data model and the data languages DAPLEX, ACM Transactions on Database Systems (TODS), v.6 n.1, p.140-173, March 1981 [doi>10.1145/319540.319561]
• 11: M. Wand. Complete Type Inference for Simple Objects. In Proc. Conf. on Logic in Computer Science. 1987.
• 12: Carlo Zaniolo, The database language GEM, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

General Terms:
Design, Languages, Theory