Complexity of the Type-Consistency Problem for Acyclic Object-Oriented Database Schemas
スポンサーリンク
概要
- 論文の詳細を見る
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 acyelic schemas is coNEXPTIME-hard and the problem for retrieval acyclic schemas is PSPACE-complete.
- 社団法人電子情報通信学会の論文
- 2001-05-01
著者
-
ITO Minoru
Graduate School of Information Science, Nara Institute of Science and Technology (NAIST)
-
Ito M
Nara Inst. Sci. And Technol. Nara Jpn
-
Ishihara Y
Osaka Univ. Toyonaka‐shi Jpn
-
ISHIHARA Yasunori
Department of Informatics and Mathematical Science, Graduate School of Engineering Science
-
Ishihara Y
Osaka Univ. Osaka Jpn
-
SHIMIZU Shougo
Graduate School of Information Science, Nara Institute of Science and Technology
-
YOKOUCHI Junji
FUJISOFUT ABC Inc.
-
Shimizu Shougo
Graduate School Of Information Science Nara Institute Of Science And Technology
-
Ishihara Yasunori
Department Of Informatics And Mathematical Science Graduate School Of Engineering Science
-
Ito Minoru
Graduate School Of Information Science Nara Institute Of Science And Technology (naist)
-
Ito Minoru
Graduate School Of Information Science Nara Institute Of Science And Technology
関連論文
- Two-layer distributed service placement method on mobile ad-hoc networks (モバイルコンピューティングとユビキタス通信)
- HDAR: Highly Distributed Adaptive Service Replication for MANETs
- Computational Complexity of Finding Meaningful Association Rules
- Implication Problems for Specialization Constraints on Databases Supporting Complex Objects
- Computational Complexity of Finding Highly Co-occurrent Itemsets in Market Basket Databases
- An Approximation Algorithm for the Task-Coalition Assignment Problem
- A Case of Severe Hypoglycemia during Infancy Turned out to be Turner Syndrome with Ringed X
- Aromatase Inhibitor, Anastrozole, Therapy for Precocious Puberty in 3-year-old Girl with the McCune-Albright Syndrome
- A Case of Severe Hypoglycemia during Infancy Turned out to be Turner Syndrome with Ringed X
- A Female Case of Cushing's Disease with Growth Disturbance
- A Formal Approach to Detecting Security Flaws in Object-Oriented Databases (Special Issue on New Generation Database Technologies)
- An Authorization Model for Object-Oriented Databases and Its Efficient Access Control
- Assignment of Data Types to Words in a Natural Language Specification
- Implementation of Natural Language Specifications of Communication Protocols by Executable Specifications
- A Translation Method from Natural Language Specifications of Communication Protocols into Algebraic Specifications Using Contextual Dependencies
- Complexity of the Type-Consistency Problem for Acyclic Object-Oriented Database Schemas
- Mole Fraction Control of Poly(3-Hydroxybutyric-Co-3-Hydroxyvaleric Acid in Fed-Batch Culture of Alcaligenes eutrophus
- 343 Mole Fraction Control of PHA in Fed-Batch Culture of Alcaligenes eutrophus
- Characteristics of Ice-nucleation Activity in Fusarium avenaceum IFO 7158
- Dynamics of the Hydration of Amino Alcohols and Diamines in Aqueous Solution
- Nutrient-enriched Diet in the Early Neonatal Period Influences the 3-year-old Height in Very Low Birth Weight Infants
- A Personal Navigation System with Functions to Compose Tour Schedules Based on Multiple Conflicting Criteria(Selected Papers from ICMU 2005(Second International Conference on Mobile Computing and Ubiquitous Networking))
- Dynamics of the Hydration of Halogenoalcohols in Aqueous Solution
- HDAR : Highly Distributed Adaptive Service Replication for MANETs
- Probabilistic Coverage Methods in People-Centric Sensing
- Specialization Constraints for a Complex Object Model Supporting Selective Inheritance
- A Reinforcement Learning Method with the Inference of the Other Agent's Policy for 2-Player Stochastic Games
- A Personal Navigation System with Functions to Compose Tour Schedules Based on Multiple Conflicting Criteria
- A Personal Navigation System with Functions to Compose Tour Schedules Based on Multiple Conflicting Criteria
- Probabilistic Coverage Methods in People-Centric Sensing