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
메서드 호출 메커니즘은 객체 지향 프로그래밍 언어의 필수 기능 중 하나입니다. 이 메커니즘은 데이터 캡슐화 및 코드 재사용에 기여하지만 런타임 유형 오류가 발생할 위험이 있습니다. 객체 지향 데이터베이스(OODB)의 경우 런타임 오류로 인해 롤백이 발생합니다. 따라서 주어진 OODB 스키마가 일관되게 유지되도록 하는 것이 바람직합니다. 즉, OODB 스키마의 데이터베이스 인스턴스에서 쿼리를 실행하는 동안 런타임 오류가 발생하지 않도록 하는 것이 바람직합니다. 이 논문에서는 유형 일관성 문제의 계산 복잡성에 대해 논의합니다. OODB 스키마의 모델로서 우리는 클래스 계층 구조, 상속, 복합 객체 등과 같은 OODB의 기본 기능을 모두 갖춘 Hull 등이 소개한 업데이트 스키마를 채택합니다. 업데이트 스키마의 유형 일관성 문제는 결정할 수 없는 것으로 알려져 있습니다. 비순환 스키마라고 하는 업데이트 스키마의 하위 클래스를 소개하고 비순환 스키마의 유형 일관성 문제가 coNEXPTIME에 있음을 보여줍니다. 또한 재귀 없는 비순환 스키마의 문제는 coNEXPTIME-hard이고 검색 비순환 스키마의 문제는 PSPACE-complete임을 보여줍니다.
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.
부
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
부
@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},}
부
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 -