Refinements of Complexity Results on Type Consistency for Object-Oriented Databases

摘要

The method invocation mechanism is one of the essential features in object-oriented programming languages. This mechanism contributes to data encapsulation and code reuse, but there is a risk of a run-time type error. In the case of object-oriented databases (OODBs), a run-time error causes rollback. Therefore, it is desirable to ensure that a given OODB schema is consistent; i.e., no run-time type error occurs during the execution of queries under any database instance of the OODB schema. This paper discusses the computational complexity of the type-consistency problem. As a model of OODB schemas, we adopt update schemas introduced by R. Hull et al., which have all of the basic features of OODBs such as class hierarchy, inheritance, and complex objects. For several subclasses of update schemas, the complexity of the type-consistency problem is presented. Importantly, it turns out that nonflatness of the class hierarchy, recursion in the queries, and update operations in the queries each make the problem difficult.