The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Le mécanisme d’invocation de méthode est l’une des fonctionnalités essentielles des langages de programmation orientés objet. Ce mécanisme contribue à l'encapsulation des données et à la réutilisation du code, mais il existe un risque d'erreurs de type d'exécution. Dans le cas des bases de données orientées objet (OODB), une erreur d'exécution provoque une restauration. Par conséquent, il est souhaitable de garantir qu'un schéma OODB donné est cohérent, c'est-à-dire qu'aucune erreur d'exécution ne se produit lors de l'exécution de requêtes sous une instance de base de données du schéma OODB. Cet article discute de la complexité informatique du problème de cohérence de type. En tant que modèle de schémas OODB, nous adoptons les schémas de mise à jour introduits par Hull et al., qui possèdent toutes les fonctionnalités de base des OODB telles que la hiérarchie des classes, l'héritage, les objets complexes, etc. Le problème de cohérence des types pour les schémas de mise à jour est connu pour être indécidable. Nous introduisons une sous-classe de schémas de mise à jour, appelés schémas acycliques, et montrons que le problème de cohérence de type pour les schémas acycliques se situe dans coNEXPTIME. De plus, nous montrons que le problème des schémas acycliques sans récursion est coNEXPTIME-difficile et que le problème des schémas acycliques de récupération est PSPACE-complet.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Shougo SHIMIZU, Yasunori ISHIHARA, Junji YOKOUCHI, Minoru ITO, "Complexity of the Type-Consistency Problem for Acyclic Object-Oriented Database Schemas" in IEICE TRANSACTIONS on Information,
vol. E84-D, no. 5, pp. 623-634, May 2001, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e84-d_5_623/_p
Copier
@ARTICLE{e84-d_5_623,
author={Shougo SHIMIZU, Yasunori ISHIHARA, Junji YOKOUCHI, Minoru ITO, },
journal={IEICE TRANSACTIONS on Information},
title={Complexity of the Type-Consistency Problem for Acyclic Object-Oriented Database Schemas},
year={2001},
volume={E84-D},
number={5},
pages={623-634},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={May},}
Copier
TY - JOUR
TI - Complexity of the Type-Consistency Problem for Acyclic Object-Oriented Database Schemas
T2 - IEICE TRANSACTIONS on Information
SP - 623
EP - 634
AU - Shougo SHIMIZU
AU - Yasunori ISHIHARA
AU - Junji YOKOUCHI
AU - Minoru ITO
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E84-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 2001
AB - 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.
ER -