Refinements of Complexity Results on Type Consistency for Object-Oriented Databases
| Autor: | Hiroyuki Seki, Yasunori Ishihara, Minoru Ito, Shougo Shimizu |
|---|---|
| Rok vydání: | 2001 |
| Předmět: |
Theoretical computer science
Computational complexity theory Computer science Programming language Computer Networks and Communications Applied Mathematics Code reuse InformationSystems_DATABASEMANAGEMENT Type error computer.software_genre Theoretical Computer Science Object oriented databases Computational Theory and Mathematics Schema (psychology) computer Class hierarchy Rollback |
| Zdroj: | Journal of Computer and System Sciences. 62(4):537-564 |
| ISSN: | 0022-0000 |
| DOI: | 10.1006/jcss.2001.1750 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect