Research or Processing queries Containing Backward Narigation of Path Expressions in Complex Object Models

点击翻译按钮获取中文摘要

1. A database schema in object-oriented databases is, in general, more flexible than one in relational databases, since an ISA hierarchy among classes can be defined and an object can have not only a simple value but another object as its attribute. Furthermore, a more complex query can be expressed using sophisticated path expression. In this research, we aim to develop a method for an efficient process of queries containing backward navigation in path expressions and have had the following results.2. In order to process a given query in a usual way, the query must be transformed into a query containing no backward navigation. We have had the following results on this transformation.(1) We introduce an algebraic query language that is independent of any specific query language. Under the language, we have shown that every algebra expression with backward navigation .has an equivalent algebra expression without backward navigation.(2) We have developed a polynomial time algorithm that transforms an algebra expression with back-ward navigation into an equivalent one without backward navigation.3. A navigability problem is to decide, given a class and a path expression with backward navigation, whether there is a database in which we can navigate from an object in the class to another object through the path expression. We have developed a polynomial time algorithm for deciding the navigavility problem.4. In the case where a given path expression contains closures, we have developed a polynomial time algorithm for deciding the navigability problem.