对象数据库跨类查询与对象查询的索引结构分析

摘要：数据库技术的发展促使其在不同领域得到了广泛的应用。包括数字图书馆等在内的一些新的应用领域对数据库的应用提出了更高的要求。而在这些新的应用领域中，多会涉及到一些复杂的、非传统形式的数据。而对象数据库能较好地支持各种非传统形式的数据类型，可以对各种复杂的数据类型实施有效的管理，而且对象数据库引入的对象数据库跨类查询与对象查询的索引结构，现在提高了数据库跨类查询的效率。该文主要从对象数据库跨类查询索引结构的设计、对象数据库跨类查询索引机制的实现以及一种基于对象查询机制索引结构的说明这三个方面来对对象数据库跨类查询与对象查询的索引结构作详细的分析。

关键词：对象数据库；库跨类查询；对象查询；索引结构

中图分类号：TP393文献标识码：A文章编号：1009-3044(2012)03-0502-02

1对象数据库跨类查询索引结构的设计

1.1对象数据库跨类查询概述

在对象数据库中，一个对象会对应一个相应的标识符，而对象间的关系就是由相应的对象所对应的标识符之间的关系来体现的。对象之间的关系是数据库实现跨类查询的基础。通过数据库查询语言中那些支持跨类查询的描述和支持跨类查询处理操作的描述，从而完成对象数据库跨类查询的操作。

1.2认识对象数据库跨类查询索引结构

基于对象数据库的对象数据库跨类查询索引结构多是依靠对象间的双向指针连接、跨类查询处理以及跨类查询描述进行设计的。其中跨类查询处理以及跨类查询描述是依赖于对象间的双向指针连接的。1.2.1对象间的双向指针连接数据库中的每一个对象都具有一个唯一的对象标识符，系统可以根据对象相对应的标识符以及这些对象之间所建立的联系，借助这些对象彼此间建立的双向指针连接来表示这些对象之间的相互联系。其中用于描述对象之间相互关系的双向指针连接，包括指针连接的建立和指针连接的删除这两个方面。

1）指针连接的建立。当数据库系统在创建那些属于不同类而且彼此之间具有相互联系的对象时，数据库系统会根据相应的对象所对应的标识符，通过建立这些对象彼此之间的指针连接来表示这些对象之间的相互关系。

2）指针连接的删除。当数据库系统中某个对象被删除时，数据库系统会将那些与这个被删除的对象之间相关的指针连接自动删除。

1.2.2跨类查询处理

在数据库跨类查询处理时，会以某个初始类中的对象为出发点，通过对象之间的指针连接，来寻找目标类中的对象，并使用跨类查询的目标表达式，对目标类中的对象进行计算，其中的计算结果即是跨类查询的结 果。1.2.3跨类查询描述

在数据库查询语言中，数据库查询语言中包含描述跨类查询的语法，可以有效支持跨类查询描述定义的相关操作。其中包括路径表达式以及和类路径表达式相似的形式。

2对象数据库跨类查询索引机制的实现

2.1对象数据库系统对对象之间的双向指针连接自动维护的实现2.1.1具有联系的对象之间双向指针连接的自动创建数据库系统在创建一个类中的对象时会根据其为每个对象所分配的相应的标识符，找到与该对象具有联系的其他所有的对象，然后数据库系统中把这些用于描述对象之间相互关系的双向指针连接记录下来，而这些用于描述对象之间相互关系的双向指针连接是由新创建对象所对应的标识符以及其所属类所对应的标识符、关联对象所对应的标识符以及关联对象所属类所对应的标识符组成的。这些对象间可能存在着1:m或1:1的关系，对于1:m的关系，则可通过多对的用于描述对象之间相互关系的双向指针连接来记录这些对象彼此之间的关系。而对于1:1的关系，可以通过一对用于描述对象之间相互关系的双向指针连接来记录这两个对象之间的关系。

2.1.2具有联系的对象之间双向指针连接的自动删除

数据库系统在删除某个类的其中一个对象的时候，数据库系统会在记录中自动找到那些与该被删除的对象之间所有的指针连接，并自动将这些指针连接从数据库系统中删除掉。2.2跨类查询的描述在进行跨类查询的描述时，需要具备跨类查询的起点类和终点类、跨类查询所要经历的路径、跨类查询的目标表达式等几项内容。其中对跨类查询的方向没有明确的规定，其方向即可以是单向的也可以是双向的。2.3跨类查询的执行

跨类查询的执行就是以某个初始类中的对象为出发点，通过对象之间的指针连接来寻找目标类中的对象，并使用跨类查询的目标表达式，将目标对象表达式的计算结果返回。跨类查询执行的具体步骤如下：

1）根据跨类查询命令，确定目标类与初始类之间的类路径，然后在确定类路径之后，还需要对其正确性进行检查，要检查该类路径中是否存在回路以及类路径中前后两个类之间是否具有某种语义上的关联。

2）对于初始类中的每一个对象，要在跨类查询路径所涉及的所有类之间查找具有相互联系的对象，一直到找到属于目标类的相关对象为止。由于这些具有相互联系的对象之间可能存在着1:m或1:1的关系，对于1:m的关系，则寻找与前一个类中的某一个对象具有相互联系的后一个类中的多个对象，然后一直重复上述的查询处理过程，直到所有的相关对象取完为止。对于1:1的关系，则寻找与前一个类中的某一个对象具有相互联系的后一个类中的相应的某一个对象。

3）采用相应的数据库表达式计算方法，并借助跨类查询所设定的目标类上的表达式，来对目标类上的对象进行计算，完成跨类查询的处理操作。

2.4路径表达式的计算

对象数据库查询处理模块的路径表达式计算的具体步骤如下：

1）验证路径表达式的正确性。一个正确的路径表达要满足如下两个方面的条件：一是正确的路径表达要求前后两个类之间要具有直接的关系，其中二者可以互为关系，或者其中一个类为另外一个类的类；二是正确的路径表达要求路径表达式的目标表达式必须是满足路径目标类属性要求的一个计算表达式。

2）数据库系统对初始类中的每一个对象进行扫描的时候，要根据相应的索引结构，对路径表达式所涉及的所有类，然后按照深度优先遍历算法查找这些类中具有相互联系的对象之间的关系，一直到找到目标类上的相应的对象为止。由于路径表达式的表达方向不明确，既可以是双向的也可以是单向的，所以查找的源点即可以是源类，也可以是目标类。

3）完成上述操作找到目标类上的对象后，还需要结合路径表达式的目标表达式，按照数据库表达式的计算方法，对目标表达式进行计算，并要把最终的计算结果返回。

3一种基于对象查询机制的索引结构

PNI即路径导航索引是基于对象查询机制而且支持路径表达式高效计算的一种索引结构，以下就以路径导航索引为例来对对象查询的索引结构进行说明。3.1路径导航索引结构的组成路径导航索引结构主要由Identity-Index、Path-Instance-Table、Attribute-Index这三部分组成。其中Path-Instance-Table用于存储路径的实例，而Identity-Index和Attribute-Index的建立是以Path-Instance-Table为基础的，Identity-Index和Attribute-Index的建立可以有效的实现快速的路径实例检索。

3.2路径导航索引结构的说明3.2.1 Path-Instance-Table

Path-Instance-Table翻译成汉语即路径实例表，顾名思义，路径实例表就是一张用来存储给定路径的所有实例的表，而且路径实例表中的每个元组对应一个具体的路径实例。数据库系统根据对象之间的关系，在不同的层次中，会给定相应层次的一个不同的路径。也就是说，可以通过对象间的关系来确定这些对象所有的路径实例。

路径实例表中存储的不是完整的对象实例，其中只存储了组成路径实例的所有对象的OID。在给定的一条路径即P=C1C2…Cn，该路径所对应的Path-Instance-Table的模式为[S1:OID，S2:OID，…，Sn:OID]，其长度路径为n-1，是一个具有n列的路径实例表，而且每列的数据类型都是为OID的数据类型，即是取值范围为C1到Cn的所有实例的OID数据类型的数据集合，而路径实例表的每一行对应Path-Instance-Table的一个路径实例。

其中Path-Instance-Table即路径实例表在设计时需要做到如下两点：

1）对于互为逆路径的两条路径，只存储其中的一个路径实例，这样看以节省存储开销。因为对于任意可逆路径P及其逆路径P′，将组成P的每一个路径实例的对象序列进行顺序置换后就可以得到P′的路径实例。

2）如果路径实例表存储的是完整的路径实例，在计算路径表达式时，需要找到路径实例的最后一个对象实例，通过投影计算，推出路径表达式的结果。如果路径实例表存储的只是存储路径实例中的第一个和最后一个实例，需要进行一次对象遍历以存取路径实例上相应的对象实例，然后进行路径表达式的计算。

3.2.2 Identity-Index

在路径实例表上建立Identity-Index，可以快速的实现路径实例的检索。其中Identity-Index是通过在路径实例表的每一列上建立一个以OID作为记录关键字的B+树索引来实现的。其中addr1到addrn是包含有记录关键字OID的路径实例对应路径实例表相应元组的物理地址，PagePointer是指向索引树下一层结点的指针。

3.2.3 Attribute-Index

在路径实例表上建立Attribute-Index，可以有效减少路径表达式计算的开销。Attribute-Index是将路径上某个类对象的属性值映射到包含该对象的路径实例信息上。其中Key-length是索引属性的长度，Key-value是索引记录的关键字。

4结束语

结论：对象数据库跨类查询与对象查询作为支持那些非传统的复杂数据查询的两种重要的查询方法，在当前的数据库查询应用领域得到了广泛的应用。而对象数据库跨类查询与对象查询方法的实现是以其所采用的索引结构为基础的，索引结构的设计和优化直接决定着对象数据库跨类查询与对象查询这两种数据库查询方法的查询效率，因此如何实现基于对象数据库跨类查询机制索引结构的优化以及基于对象查询机制索引结构的优化，将成为今后数据库数据查询研究领域的一项重要研究课题。

参考文献：

[1]王国仁.路径表达式的算法研究[J].计算机学报,2003(9).

[2]黄泽谦.一种支持对象数据库高效查询处理的索引结构[J].计算机学报, 2010(8).

[3]彭智勇.对象数据库跨类查询分析[J].计算机学报,2007(1).

[4]彭智勇.数据库跨类查询方法[C]∥2010第27届中国数据库学术会议论文集,2010.