Tech Report CS-92-33

Method Schemas

Serge Abiteboul, Paris Kanellakis, Sridhar Ramaswamy and Emmanuel Waller

July 1992

Abstract:

A method schema is a simple programming formalism for object-oriented databases with features such as classes, methods, inheritance, name overloading, and late binding. An important problem is to check whether a given method schema can lead to an inconsistency in some interpretation. This consistency question is shown to be undecidable in general. Decidability is obtained for monadic and/or recursion-free method schemas. In particular, consistency of monadic method schemas is shown to be decidable in $O(nc^3)$ time, where $n$ is the size of the method definitions and $c$ is the size of the class hierarchy; also, it is logspace-complete in PTIME, even for monadic, recursion-free schemas. Method signature covariance is shown to simplify the computational complexity of key decidable cases. For example: one coded method in the context of base methods with covariant signatures can be tested for consistency in $O(n+c)$ time for the monadic case (without covariance this problem is in $O(nc^2)$ time) and in PTIME for the fixed arity polyadic case (without covariance this problem is NP-complete). Incremental consistency checking of method schemas is a formalization of the database schema evolution problem, for which a sound, but necessarily incomplete, heuristic is proposed.

(complete text in pdf or gzipped postscript)