| Presentation | 1999/6/18 Complexity of the Type-Consistency Problem for Acyclic Object-Oriented Database Schemas Junji Yokouchi, Shougo Shimizu, Yasunori Ishihara, Minoru Ito, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Method invocation mechanism is one of the essential features of object-oriented programming languages. This mechanism contributes to data encapsulation and code reuse, but there is a risk of ruun-time type errors. 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. In this paper, we adopt update schemas introduced by Hull et al. as a model of OODB shemas. We show that the type-consistency problem for a subclass of update schemas, called acyclic schemas, is coNEXPTIME-complete. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | object-oriented database / acyclic schema / type-consistency problem / complexity |
| Paper # | COMP99-16 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1999/6/18(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Complexity of the Type-Consistency Problem for Acyclic Object-Oriented Database Schemas |
| Sub Title (in English) | |
| Keyword(1) | object-oriented database |
| Keyword(2) | acyclic schema |
| Keyword(3) | type-consistency problem |
| Keyword(4) | complexity |
| 1st Author's Name | Junji Yokouchi |
| 1st Author's Affiliation | Graduate School of Information Science, Nara Institute of Science and Technology() |
| 2nd Author's Name | Shougo Shimizu |
| 2nd Author's Affiliation | Graduate School of Information Science, Nara Institute of Science and Technology |
| 3rd Author's Name | Yasunori Ishihara |
| 3rd Author's Affiliation | Graduate School of Information Science, Nara Institute of Science and Technology |
| 4th Author's Name | Minoru Ito |
| 4th Author's Affiliation | Graduate School of Information Science, Nara Institute of Science and Technology |
| Date | 1999/6/18 |
| Paper # | COMP99-16 |
| Volume (vol) | vol.99 |
| Number (no) | 130 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |