Paris Kanellakis, 8 October 1992: DB
Veronica Archibald
Department of Computer Science, University of Toronto
(SF = Sandford Fleming Building, 10 King's College Road)
-------------------------------------------------------------
DB
SF1105, at 2:00 p.m., 8 October 1992
Paris Kanellakis
Brown University
"Method Schemas -- A Programming Framework for OODBs"
A method schema is a simple programming framework 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(N*H^3) time, where N is the size of the method definitions
and H 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+H)
time for the monadic case (without covariance this problem is in O(N*H^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.
Joint work with: Serge Abiteboul, Sridhar Ramaswamy, and Emmanuel Waller.