面向对象数据库可视化查询的研究.doc

面向对象数据库可视化查询的研究闫永刚南京信息工程大学计算机与软件学院气象信息技术与安全摘要：为方便对语义丰富、结构复杂的对象数据库管理系统的操作，提高管理和开发效率，文中提出一种可根据需求自动产生结构清晰、布局合理的继承、合成及继衫合成全局结构的对象数据库模式图的算法，基于此生成的对象数据库模式图可进行可视化和导航式的信息查询。实验结果表明该算法可作为对象数据库可视化查询的基础，并可推广到具有类似继承和合成等复杂结构的其他工程应用领域。关键词：面向对象数据库；模式图；可视化查询；类层次1 引言数据库发展经历了三个阶段。第一阶段是层次和网状数据库，过程化程度较高，一般用户使用困难；第二阶段是关系数据库（1C），它以关系演算和关系代数为其数学基础，以二维表为其数据结构，利用非过程化数据操纵语言进行数据库管理，采用内Z外Z概念模式的三层模式结构，具有较高数据独立性，成为!世纪%年代到年代中期的主流数据库。上述层次!网状和关系数据库尽管设计和控制方式不同，但都用于一般事务处理，统称为传统数据库。近年来，随着网络技术、多媒体技术、空间信息科学、信息管理、人工智能、软件工程技术和数据挖掘技术等领域的发展及新的社会需求出现，信息无论从数量上还是结构上都远远超出了传统数据库能承受的范围。为了适应海量信息和复杂数据处理要求，新一代数据库应运而生，它们结合特定应用领域，分为多媒体数据库（结合多媒体技术）!空间数据库（结合空间信息学和FSP）!演绎数据库（结合人工智能）!工程数据库（结合软件工程）等。与传统数据库相比，它们既具有多样性（学科交叉的必然结果），又有统一性，建立它们的主要目的是为了处理海量信息和复杂数据结构。因此面向对象技术必不可少，它们之间关系如图1所示。新型数据库面向对象数据库传统数据库扩充改进图1 三种数据库之间的关系图1.1面向对象数据库概念面向对象数据库系统（OODBS）支持定义和操作OODB，应满足两个标准：首先它是数据库系统，其次它也是面向对象系统。第一个标准即作为数据库系统应具备的能力（持久性、事务管理、并发控制、恢复、查询、版本管理、完整性、安全性）。第二个标准就是要求面向对象数据库充分支持完整的面向对象（OO）概念和控制机制。综上所述，我们将面向对象数据库简写为：面向对象数据库=面向对象系统+数据库能力。本文提出一种基于面向对象数据库管理系统0MNIX的可视化查询机制，该机制的核心是面向对象数据库模式图的自动生成算法。该算法可以生成对象的继承层次图、合成层次图和继影合成全局模式图。用户可以在生成的模式图上以可视化方式进行对象实例和模式信息查询。目前该机制已成功应用于OMNIX系统的可视化管理器中。2 基本术语 面向对像数据库模式由类构成，类之间可能存在复杂的继承和合成关系。因此，一个完整的面向对象数据库模式图包括类继承层次、类合成层次及独立类层次等信息，生成对象模式图需要定义下列术语。21结点结点N(ID，Lx，y，Px,y，Wu，d，CLArray,Bool)表示数据库模式图中的类结点或空结点。其中：ID代表类名，由它获得该类相关的所有数据字典信息；h，y代表该类结点在模式图层中的位置，Px，y表示绘制类结点的坐标位置；wu，d表示向前、向后位置调整时的权重；C岫数组中存放该类的所有直接子类和合成关系类的指针；Bool表示该结点是否为空结点。类结点中有一类为叶结点，对于不同的模式图，叶结点有不同的解释，在继承模式图中叶结点指结点池中未被标记的，且其为最终子类或其所有直接子类结点都被标记的类结点；在合成模式图中叶结点指结点池中未被标记的，且其为最终被引用类或其所有直接合成类结点都被标记的类结点；在继承合成混合图中叶结点指结点池中未被标记的且其为最终子类或最终被引用类，或该类结点的CLAmy属性中所有链接类都被标记的类结点。22 类链接类链接clink(pointer，Bool)是存放类结点相关继承和合成关系的类的指针。Bool指示存放的是类结点的继承关系(True)或合成关系(False)，根据该属性可生成对象模式图的继承层次、合成层次或继影合成混合层次图。23 结点池结点池Npool(N，N2，Nn，MArray)用来临时存放类结点N1，N2，N。；Marray是一个数组用于指示对应类结点N1，N2：，Nn。是否被标注。开始时为未标注，初始化时把所有类结点放入结点池中，并建立类结点的所有类层次关系链接。24 层层Level(N1N2：，Nn，MArray)存放处于该层中的所有类结点N1，N2，Nn，同层中类结点间距离固定。由于层间距离固定像素大小，所以只需要Ly表示该层在整个模式图中的开始位置.层中需要提供计算每层中结点的位置的方法，并根据类结点的相关位置权重wu，d对其进行层中位置排序。25 图无论是产生对象模式继承层次图、合成层次图，还是继j影合成混合图，chart(L0，L1，Ln)都由若干层组成，其中所有独立类结点(即与其它类既无继承关系又无合成关系的类)都处于层Ly中，其他类则按继承或合成关系的复杂程度分别处于不同的层中。整个模式图呈类金字塔形状，最底层为独立类层，按类间关系复杂程度依次向上排列，最上层为数据库模式中最复杂继承关系的父类和具有最长合成路径的类。模式图自动产生过程中有两个需要注意的问题：一是对于结构复杂的对象模型需要插入空结点以使布局合理，二是类结点在层中的位置权重计算和排序问题。图l是一个具有跨层多继承和合成模式图。图l(a)中实线表示继承关系，虚线表示合成关系。图中结点c是一个多继承，既直接继承结点B，又直接继承结点D。由于结点B和结点D不处于同一层次，因此在生成模式图时需要在C和D的中间层中插入一个空结点，以尽可能地使布局合理美观，如果层数相隔较多，则需连续产生空结点。同样，对于结点I和D之间的合成关系，也需作相同的处理，结果如图l(b)所示。类结点在层中的位置权重计算和排序问题涉及前向或后向调整的权重计算calc_weight(Li，Nj)即计算i层中j结点的前向、后向调整的权重，计算公式如下: Wu= ， Wd= 其中NuP，表示i+1层中指向Nj的结点的层水平位置，m表示i+1层中指向Nj的结点数目；NdP，表示Nj指向的il层中的结点的层水平位置，n表示Nj指向il层中的结点数目。当层中所有类结点的位置权重计算完毕后，对该层中的所有类结点进行排序，一般按照Wu+Wd。进行排序并调整类结点在该层中的位置。为使布局更加合理，上述类结点在层中的位置权重计算和排序过程需重复多遍。3 算法描述构造对象模式图采用自底向上逐层的方法。构造对象模式图过程如下：首先利用数据字典把所有类放人结点池中，同时在每个结点保存该类结点的直接子类及直接合成类的链接；然后把所有不存在的任何类间关系的类加入到独立类层中并进行标记；接着产生一个新层，把所有叶结点加入到该新层中，同时对这些叶结点进行标记，使这些叶结点的上层结点成为新的叶结点；重复这个过程直到产生所有的类层次；类层次建立后需要确定每个类结点的具体位置包括所处层中位置和绘图信坐标位置，为了使类间关系密切的类互相靠近，需根据类间关系的紧密程度对同层中的类结点进行位置调整，以尽可能减少绘图时连线的交叉；最后是对整个模式图的位置进行调整，使之布局合理。以下分别描述对象数据库模式继承层次图、合成层次图、继影合成混合层次图的自动生成算法。算法1：对象数据库模式继承层次图的自动生成输入：对象数据库数据字典输出：对象数据库模式的继承层次图步骤： 生成结点池 NpoolNl，N2，Nn，MArrayMArray0，0，0，0for each NiNPool dofor each NjNi的直接子类doClinkkPointerNj；ClinkkbooltrueNiCLArrayClinkkNiCLAmy中存储的是所有该类的直接子类。 过滤出孤立结点并形成一个独立的类层次for each NiNPool doif NiCIArraIyNuLL then Nimark=lfor each NjNiCLAn可do Nimark=lfor each NkNPool doif Nk mark=0 thenLevel0Nk，Nkmark=1for each NiNPool do Nimark=0for each Nkkvel0 do Nkmark=l标记结点池中所有属于独立类层次中的结点。 生成一个新类层次for each NiNPool and Nimark=0 dofor eachNjNiCLArray doif all Njmark=l thenLeveli Ni，Nimark=l 重复步骤，直到结点池中的所有类结点都被标记，最后形成完整的继承层次图。 插入空结点for each NiLeveli dofor each NjNiCIArray doif level-lFindNode(Nj)=false thenNk new Null_Node()；level-1 Nk 位置计算for each Leveli E Level dofor each Nj leveli do NjLx,y=(j+l，i)leveli calc_weight(i,Nj);leveliSort();leveliCalc_pixel_pos() 全局位置调整：根据绘图区域的大小调整模式图的上下左右位置，使其尽可能居中。对于对象数据库模式的合成图的自动生成算法，除在构造结点池过程中，在每个结点中存储该结点的有直接合成指向类外，其他步骤与继承层次图的生成算法相同，具体描述如下。算法2：对象数据库模式合成层次图的自动生成输入：对象数据库数据字典输出：对象数据库模式的合成层次图步骤： 生成结点池NpoolNl，N2，Nn，MArrayMArray0，0，0，0for each NiNPool dofor each NjNi的合成子类doClinkkPointerNj；ClinkkboolfalseNiCLArrayClinkk后续步骤同继承层次图的生成步骤。对于对象数据库模式的继影合成混合层次图的自动生成算法，在构造结点池过程中，每个结点应同时存储该结点的所有直接子类和所有直接合成指向类，其他步骤与继承层次图的生成算法相同，具体描述如下。算法3：对象数据库模式继影合成混合层次图的自动生成输入：对象数据库数据字典输出：对象数据库模式的继衫合成混合层次图步骤： 生成结点池 NpoolNl，N2，Nn，MArrayMArray0，0，0，0for each NiNPool dofor each NjNi的直接子类doClinkkPointerNj；ClinkkbooltrueNiCLArrayClinkkFor each NjNi的合成指向类doClinkkPointerNj；ClinkkboolfalseNiCLArrayClinkk后续步骤同继承层次图的生成步骤。4实验结果OMNIX系统是一个国内自主研发的面向对象数据库管理系统，利用本文中的自动生成算法生成的对象模式图已经成功应用在该系统的可视化查询工具开发过程中。利用该查询工具可生成的OMNIX系统的继承层次图、合成层次图及继影合成全局层次图，然后在图中可以通过鼠标点击相关的类进行可视化查询。在全局对象模式图可视化信息查询界面上通过点击界面中显示的每个类的父类子类、引用类被引用类可以实现遍历整个模式信息和每个类的具体属性和方法的目的。根据测试目的，测试该系统时选取了不同规模的数据库应用系统，应用系统涉及的类从几十个到几百个，继承层次深度从一层到九层。大量测试结果表明，效果较好的是对象模式图自动生成算法生成的对象数据库模式图。5 结论本文提出的基于对象数据库模式图的可视化查询技术能够实现在自动产生的不同结构的对象模式图上进行可视化的、导航式的具有复杂路径的对象实例查询和数据库模式信息查询。此外，该技术也可以应用于具有类似继承和合成层次的工程电子类的自动布线图领域。该技术目前仍存在一些不足，如对象数据库模式图自动生成算法在生成复杂的全局模式图时，虽能完整反映其模式结构，但布局不够合理，需要进一步加以改进和完善。参考文献1Thomas Connolly，carolyn BegDa