La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

Complexity of the Type-Consistency Problem for Acyclic Object-Oriented Database Schemas Complexité du problème de cohérence de type pour les schémas de bases de données acycliques orientées objet

Shougo SHIMIZU, Yasunori ISHIHARA, Junji YOKOUCHI, Minoru ITO

  • Vues en texte intégral

    0

  • Citer

Résumé:

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.

Publication
IEICE TRANSACTIONS on Information Vol.E84-D No.5 pp.623-634
Date de publication
2001/05/01
Publicisé
ISSN en ligne
DOI
Type de manuscrit
PAPER
Catégories
Bases de données

Auteurs

Mots-clés

Table des matières