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 encapsul ation 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 consiste nt; i.e., no run-time type error occurs during the execution of queries und er any database instance of the OODB schema. This paper discusses the compu tational complexity of the type-consistency problem. As a model of OODB sch emas, we adopt update schemas introduced by R. Hull cr rrl.. which have all of the basic features of OODBs such as class hierarchy. inheritance. and c omplex objects. Fur 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 o perations in the queries each make the problem difficult. (C) 2001 Academic Press.