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

1.一般而言，面向对象数据库中的数据库模式比关系数据库中的数据库模式更灵活，因为可以定义类之间的ISA层次结构，并且对象不仅可以有一个简单的值，还可以有另一个对象作为其属性。此外，更复杂的查询可以使用复杂的路径表达式来表示。在这项研究中，我们的目标是开发一种高效的处理路径表达式中包含反向导航的查询的方法，并取得了以下结果。为了以通常的方式处理给定的查询，必须将该查询转换为不包含向后导航的查询。在这种变换上，我们得到了如下结果：(1)我们引入了一种独立于任何特定查询语言的代数查询语言。在该语言下，我们证明了每个有反向导航的代数表达式都有一个等价的无反向导航的代数表达式。(2)我们提出了一个多项式时间算法，将一个有反向导航的代数表达式转换为一个没有反向导航的等价代数表达式。可导航性问题是在给定一个类和一个具有反向导航的路径表达式的情况下，确定是否存在一个数据库，在该数据库中，我们可以通过路径表达式从类中的一个对象导航到另一个对象。提出了一种判定通航问题的多项式时间算法。在给定路径表达式包含闭包的情况下，我们提出了一种判定可导航性问题的多项式时间算法。

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.