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

研究或处理包含复杂对象模型中路径表达式的向后导航的查询

• 批准号: 09680399
• 负责人: ITO
• 金额: $ 1.54万
• 依托单位: Nara Institute of Science and Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1997
• 资助国家: 日本
• 起止时间: 1997 至 1998
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-09680399/
• 关键词: Object-Oriented Database; Path Expression; Backward Narigation; Query Processing; データベース; 複合オブジェクト

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.

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

项目成果

Toshiyuki Morita: "A Formal Approach to Detecting Security Flaws in Object-Oriented Databases" IEICE Transactions on Information and Systems. E82-D 1. 89-98 (1999)

Toshiyuki Morita：“检测面向对象数据库中安全缺陷的正式方法”IEICE Transactions on Information and Systems。

鈴木 伸崇: "オブジェクト指向データベースにおける逆行を含む属性集合およびその閉包を用いた経路式について" 電子情報通信学会論文誌(D-I). J82-D-I 1. 3-13 (1999)

Nobutaka Suzuki：“关于面向对象数据库中的属性集，包括使用其闭包的路由表达式”，电子、信息和通信工程师学会汇刊 (D-I) 1. 3-13 (1999)。

村上 哲也: "マルチエージェント環境における時刻の前後関係に関する推論問題" 電子情報通信学会技術研究報告. COMP97-85. (1998)

Tetsuya Murakami：“多智能体环境中时间背景的推理问题”IEICE COMP97-85 (1998)。

森多 俊之: "On the Detection Problem of Data Flaws in Object-Oriented Databases" 電子情報通信学会技術研究報告. COMP97-66. (1997)

Toshiyuki Morita：“面向对象数据库中数据缺陷的检测问题”IEICE COMP97-66。

鈴木伸崇: "オブジェクト指向データベースにおける逆行を含む属性集合およびその閉包を用いた経路式について" 電子情報通信学会論文誌(D-I). J82-D-I・1. 3-13 (1999)

Nobutaka Suzuki：“关于面向对象数据库中的属性集和使用闭包的路径表达式”，电子信息通信工程师学会汇刊 (D-I) 3-13 (1999)。