Method Schemas

摘要

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(nc3) 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(nc2) 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.