For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Complexity of the Type-Consistency Problem for Acyclic Object-Oriented Database Schemas
Shougo SHIMIZU Yasunori ISHIHARA Junji YOKOUCHI Minoru ITO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2001/05/01
Print ISSN: 0916-8532
Type of Manuscript: PAPER
object-oriented database, type-consistency problem, acyclic schema, complexity,
Full Text: PDF(800KB)>>
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 runtime type errors. In the case of object-oriented databases (OODBs), a runtime error causes rollback. Therefore, it is desirable to ensure that a given OODB schema is consistent, i.e., no runtime 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 Hull et al., which have all of the basic features of OODBs such as class hierarchy, inheritance, complex objects, and so on. The type-consistency problem for update schemas is known to be undecidable. We introduce a subclass of update schemas, called acyclic schemas, and show that the type-consistency problem for acyclic schemas is in coNEXPTIME. Furthermore, we show that the problem for recursion-free acyclic schemas is coNEXPTIME-hard and the problem for retrieval acyclic schemas is PSPACE-complete.