基于“超”实体构件的信息组织与呈现

张瑞军，黎雯霞，张志清，张 凌，张 鹏

(1. 武汉科技大学管理学院，湖北 武汉，430081;2. 武汉铁路职业技术学院铁道信号工程学院，湖北 武汉，430205)

基于“超”实体构件的信息组织与呈现

张瑞军1，黎雯霞2，张志清1，张 凌1，张 鹏1

(1. 武汉科技大学管理学院，湖北 武汉，430081;2. 武汉铁路职业技术学院铁道信号工程学院，湖北 武汉，430205)

在关系数据库中，多层一对多实体级联的树形连接模式常发生中间结点语义歧义问题。为此，本文提出一种树形结构 “超”实体模型，给出其概念、数据结构、连接查询算法和树视图构造算法，分析了相应的时间复杂度和存储空间复杂度。在提出构件模型的基础上，设计了树形结构“超”实体构件和1/K开关连接构件。探讨了基于可编辑电子书的〈深度，维度，交互性〉的三元组信息呈现方法。“超”实体模型及算法在大型信息系统的数据库设计与主界面设计中取得了良好的应用效果。

“超”实体；树形结构；信息组织；信息呈现；构件；信息系统；数据库

在关系数据库概念模型中，常存在一种基于层次结构的多级实体联系模式，如企事业单位的行政组织机构图、设备备件分类、行政区域划分等，在信息系统实现时，它多表现为一种树形菜单式结构[1]。以高校为例，其行政组织通常按[学校]→[学院]→[系]→[教研室]的多层级树形结构规划实体，但是当某一系为校直属系时，会新增[学校]→[系]的关系模式。这时原有的树形结构就变为图结构，[系]这一级实体原有的元组语义和函数依赖也将受到破坏。同时，当访问树的层级很深、每层元组较多时，多级实体连接运算结果将写到内存的中间文件里，这将消耗大量的CPU和内存资源，导致系统运行效率下降。

研究人员对树形结构进行了深入探讨，如李俊飞等[2]采用TreeView控件设计树形结构输入输出控件，用于自定义单表和多表关联；陈正铭[3]采用先根遍历算法分析了树形结构在数据表中的存储问题；唐青松[4]研究了深度优先算法在树形结构数据表中的应用。但这些研究均基于每一级实体的固定语义，没有考虑树形结点的语义发生变化的情况。为此，本文提出一种树形结构“超”实体的概念，给出其数据结构、数据表存储模式及相关算法，并将其应用于信息系统的数据组织与信息呈现中。

1 树形结构“超”实体

1.1 相关概念

定义1 树形结构“超”实体：对于多层具有一对多联系的实体，提取其关键字和主要的共用属性，将命名统一，并增加用于标注父结点的关键字，将封装好的实体称为树形结构“超”实体。

以高校行政组织E-R图(见图1)为例，其各实体的关键字(ID1、ID2、…、IDn)和主要属性(name1、name2、…、namen)命名不同，但语义一致，可将它们归一化，并增加一个标识父结点的属性，这样便形成了如下的关系模式：

sup_ent(ID，name，upID)

其中，ID为关键字，用于唯一标识树中某一结点实体；name为结点名；upID为父结点的编码，作为外关键字与父结点关联。这种关系模式采用静态表的方式实现了如图2所示的树形数据结构[5]，表1为相应的静态数据表示例。

Fig.1 E-R diagram of administrative organization in universities

表1 树形结构“超”实体对应的静态数据表示例

Table 1 Example of static data tables related to the tree structure super entity

定义2 逻辑层：“超”实体树中的各层。各结点在逻辑层中的深度为树中各结点的深度。

定义3 语义层：“超”实体树中狭义语义相同的各层。若同一语义层的各结点不在同一逻辑层，则将它们归约到逻辑层最深的一层。

如表1所示，ID值为001的学校处于逻辑层和语义层的第1层，逻辑层的第2层为学院、第3层为系。而ID值为002的计算机系作为直属系，在逻辑层上为第2层，而语义层则被归约到第3层。这也有效地解决了[系]这一实体发生语义歧义的问题。

1.2 基本算法

树形结构“超”实体具有双重属性，在存储上表现为一个数据表，在数据结构上表现为树，其基本算法有：

(1) CreateTree(&T,structure);//按structure结构来构造树。

(2) SetValue(T, cur_node,values); //将values值赋给cur_node结点的除ID、upID属性之外的其它属性组。

(3) GetValue(T, cur_node,values); //取出cur_node结点属性组的值，并赋给values变量组。

(4) InsertChild(&T, p, c); //将树T的子树c的根结点ID值赋给p所指向结点的upID属性。

(5) DeleteChild(&T, cur_node); //删除cur_node所指向结点及以cur_node为根结点的子树。

(6) Parent(T, cur_node); //顺序访问按ID属性索引的数据表，若cur_node的upID值不为空，则返回ID值等于cur_node的upID值的结点，否则返回空。

(7) Son(T, cur_node); //顺序访问按ID属性索引的数据表，返回upID值等于cur_node的ID值的结点组，否则返回空。

(8) TraverseTree(T, Visit()); //按照Visit()策略访问树中的每个结点一次，且仅访问一次。这里有两种遍历策略：① 顺序遍历，即从头至尾访问“超”实体树所对应的数据表一次；②广度优先遍历，即将“超”实体树所对应的数据表按upID属性建立索引，顺序访问该表一次。

1.3 连接查询运算

信息系统开发中常涉及多个表之间的关联运算，其算法为：

Connect(T, Ent)；//将“超”实体树T中处于第k语义层的元组与语义上处于第k+1层的实体关联起来。

这里讨论一下查询运算中从根结点一直访问到语义层最深(设为k)的结点(叶子结点)，并与语义上处于第k+1层的普通实体进行连接时(如表1中的教研室元组与另一个教师数据表之间的连接)，传统树形结构与“超”实体树之间的算法复杂度对比。

以上两个实体的前三个对应字段语义相同，假定二者长度相同，前一实体多出Others这一字段。定义sup_ent实体中每个元组的容量为1，则二者元组存储容量之比为：

(1)

式中：Centi为传统树结构第i层实体存储容量；Csup_ent为树形结构“超”实体存储容量；ai为增量因子。

假定传统树形结构中第i层实体的元组数为ni(i=1,2,…,k), 第k+1层实体对应数据表容量为C。数据表连接时通常通过笛卡儿积运算来完成，这时首先在内存中按一定规则交替读取两个表的若干块元组，做连接运算后写入内存的中间文件，再读取中间文件，根据查询的需要做选择和投影运算。当传统树形结构的前k层数据表做连接运算后并与第k+1层数据表连接时，生成的中间文件大小为：

Cent=Cent1×Cent2×…×Centk×C

=n1(1+a1)×n2(1+a2)×…×nk(1+ak)C

(2)

而对于“超”实体树，只需按upID建立索引，访问一次后第k层的叶子结点和第k+1层数据表连接即可，生成的中间文件大小为：

Csup_ent=n1+n2+…+nk-1+nk×C

(3)

很显然有：Cent≫Csup_ent。

假设内存每秒读写数据块数为m，则读写时间分别为：

Tent=n1(1+a1)×n2(1+a2)×

…×nk(1+ak)C/m

(4)

Tsup_ent=(n1+n2+…+nk-1+nk×C)/m

(5)

同理也有：Tent≫Tsup_ent。

2 基于树形结构“超”实体的信息组织算法

树形结构“超”实体数据表建立好后，可以将其按upID属性建立索引，采用Windows系统中的TreeView这一类控件对表中数据按树形结构进行组织。这里可以采用广度优先算法来构造，其算法描述如下：

(1)游标cursor指向数据表第1条记录，将其值赋给结构变量tmp_node，树的深度depth=1，树的当前结点tv[depth].cur_node= tmp_node；

(2)游标指针下移，若游标已指向数据表末端，则算法结束，否则转向(3)；

(3)判断tv[depth].cur_node.ID是否等于tmp_node.upID。若相等，则将tmp_node作为tv[depth].cur_node的子结点插入，否则转向(4);

(4)判断tv[depth].cur_node是否有下一个兄弟节点，有则访问下一个兄弟节点，转(3)，否则转(5);

(5)depth++，转(2)。

树形结构“超”实体构造好后，可作为信息组织的骨架，通过1/K开关件与数据库、网页、电子地图、Word文档等各种媒介相连，形成一种可编辑电子书，以下就树形结构“超 ”实体与1/K开关件的构件化进行探讨。

3 构件

3.1 定义

定义4 构件：构件是具有一定独立功能的软件单元，它通过输入输出接口在特定条件的触发下完成相应的功能。它可重用，也可封装,其形式化定义为：

c=(cD,In,Out,Func,Triggers)

其中：cD为构件的标识符；In为构件的输入，有：In=(i1,i2,…,in),n≥0；Out为构件的输出，有：

3.2 树形结构“超”实体构件

由树形结构“超”实体的信息组织算法可知，树形结构“超”实体构件的输入为数据表，输出为树，按照构件的定义，其形式化描述为：

cD= sup_ent001；

In=〈数据表结构及各元组数据〉；

Out=〈树〉；

Triggers=〈用户检索需求〉；

Func=〈CreateTree,InsertChild, SetValue,GetValue, DeleteChild,Parent,Son,TraverseTree,Connect〉。

3.3 1/K开关连接构件

在可编辑电子书中，为了实现不同媒体之间的无缝切换，前驱构件与若干后继构件之间是一种1/K开关连接方式，形成1/K开关连接构件，类似于物理电路中的单刀多掷开关。这时高层构件是一个前驱构件与多个后继构件的聚集，其构件的输入是前驱构件的输入，构件的输出是多个后继构件中某一个构件的输出，如图3所示，其中：Ind为前驱构件的输入接口；Outd为前驱构件的输出接口；Out1、Out2、…、Outn分别为构件1、构件2、…、构件n的输出接口；Trigger1、Trigger2、…、Triggern分别为构件1、构件2、…、构件n的触发条件。

1/K开关连接构件的形式化描述为：

1/K_switcher_Con=(cD,In,Out,Triggers)

其中：cD=switcher001；In=Ind；Triggers=(Trigger1,Trigger2,…,Triggern)，有

3.4 可编辑电子书

可编辑电子书以树形结构“超”实体构件为根、1/K开关连接件为分支、多种阅读器构件为结点，形成如图4所示的树形逻辑构架。

4 基于可编辑电子书的信息呈现方式

现代认知学和人类工效学表明，不同的信息呈现方式对人们的信息获取能力、知识学习能力、决策能力等有很大的影响[6]。典型的信息呈现方式有网页、信息系统、内容组织图等。网页以超文本链接的方式呈现信息，有利于信息资源的浏览与搜索，但由于缺乏对事物的整体认识，易让人产生迷惘感；传统的信息系统多以二维表文本方式对信息进行组织，有很好的条理性和可交互性，但缺乏直观的感觉；内容组织图以空间地图、图表、视频等方式呈现信息，对人的视觉形成强烈冲击，但其层次感不强、信息表达的深度不够。这里以“超”实体树形结构为目录，采用“快捷菜单+主题目录区+工作区”的∏型结构，给出一种可编辑电子书框架，其中工作区部分以1/K开关连接构件与树形结构“超”实体构件相关联，既可呈现关系数据库中的结构化信息，也可呈现网页、地图、视频等非结构化信息，其界面如图5所示。

该框架采用〈深度，维度，交互性〉三元组的信息呈现模型。深度方面，以“超”实体树的组织方式，通过树结点的逐层展开，从各个层次来表征信息，让用户对事物全貌有一个总体的认识；维度方面，以快捷菜单和流行的图文并茂的QQ菜单，从多侧面、多角度表现事物，并根据用户要求定制观察视觉；交互性方面，通过增、删、改、除等功能按钮对对象的属性进行编辑。

5 应用实例

笔者所在项目组承担了水利部大型信息系统项目长江防洪工程工情信息服务系统的设计与开发工作。该系统主要对长江中下游沿岸40多个堤段、涵闸、除险加固工程、崩岸整治工程的地质情况进行集中管理。作为一种数字图书馆，该系统除存储结构化的数据库信息外，还要存储视频、网页、地图、Word文档等半结构化或非结构化的信息，传统结构化的一对多实体级联模式已无法满足其要求。这里采用基于树形结构“超”实体的可编辑电子书框架。

对结构化数据，按照图5所示的“主题目录区+QQ菜单+明细表+网络表”的风格呈现数据。系统实现时，后台采用SQL Server数据库存储地质、地貌、水文、岩土、水利等相关信息。由于所涉及各堤段的从属关系特别复杂，对应树形目录中各层级的语义不尽相同，故采用“超”实体对树形目录进行管理，如图6所示。图6中，目录树的深度为5，叶子节点荆江大堤逻辑层为第4层，语义上归约为第5层；武汉市长江干堤节点下的叶子节点长江右岸节点的逻辑层与语义层均为第5层，这两类叶子节点语义相同，均可与数据表相连，这就很好地解决了一对多实体级联时语义歧义的问题。项目组还进行了对比测试：在相同软硬件条件下，分别采用传统的一对多表关联和树形结构“超”实体进行表结构设计时，前者算法检索第5级数据表所用时间为5.23 s，而采用后者算法的检索时间仅为0.56 s。

对非结构化、半结构化的数据，按照“主题目录区+工作区”的风格呈现信息，图7给出了地图的呈现方式。这种信息呈现模式以树形结构“超”实体构件为骨架，通过1/K开关连接件与地图浏览器构件相关联，可以很方便地在工作区内对地图进行缩放等浏览操作。当然也可通过1/K开关连接件与Word编辑器、网页浏览器、视频播放器等构件相连，完成非结构化信息的呈现。

6 结语

本文提出了一种解决一对多多级实体级联中元组语义歧义问题的“超”实体模型及其构造算法。该算法吸取树形数据结构的优点，以双亲结点表示法来完成数据表的存储，在软件实现上采用Windows中TreeView控件进行封装，在信息呈现方面采用目录树结构，配合QQ菜单等控件构成一种可编辑电子书框架，并在实际信息系统的设计与开发中取得了良好的应用效果。该算法框架可以使用户在使用信息系统时多层次、多角度地了解事物对象，为大型信息系统中的数据库设计与主界面设计提供了一种很好的思路。

[1] 张瑞军. 基于树形结构的数据检索方式研究[J]. 安徽电子信息职业技术学院学报,2004，3(3):60-62.

[2] 李俊飞, 陈皓, 赵卫东. 树形结构数据输入输出控件的设计与实现[J]. 计算机工程与设计，2011，32(9)：3054-3058.

[3] 陈正铭．树形结构在关系数据库中的存储与运算[J]．韶关学院学报，2008，29(9): 18-22.

[4] 唐青松．深度优先算法在创建树形结构中的应用研究[J]．计算机技术与发展，2014, 24(9)：226-229.

[5] 张瑞军, 杜星球, 陈定方．树形结构“超”实体构造算法在双重模式下的实现[J]．微计算机信息，2006, 22(11): 215-217.

[6] 张婷. 多媒体呈现方式与认知风格对学习效果的影响研究[D]. 大连：辽宁师范大学, 2013.

[责任编辑 尚 晶]

Information organization and presentation based on super entity component

ZhangRuijun1,LiWenxia2,ZhangZhiqing1,ZhangLing1,ZhangPeng1

(1.College of Management，Wuhan University of Science and Technology，Wuhan 430081，China; 2.Department of Railway Signal Engineering, Wuhan Railway Vocational College of Technology, Wuhan 430205, China)

In relational database, the problem of semantic ambiguity always happens to the intermediate nodes in tree structure of multilayer one-to-many entity relationship. This paper proposes a model of tree structure super entity, discusses the concepts, data structure, join query method and tree view construction algorithm of the super entity, and analyzes the time and space complexity of the algorithms. On the basis of the proposed component model, a tree structure super entity component and a 1/K switch connection component are designed. A three-tuple information presentation method of 〈depth, dimension, interaction〉 based on editable e-book is explored. Applied to the design of database and main interface of a large information system,the model and algorithms of super entity have yielded excellent results.

super entity; tree structure; information organization; information presentation; component; information system; database

2015-07-06

国家自然科学基金面上项目(71271161)；湖北省自然科学基金资助项目(2014CFB804，2015CFB564)；教育部人文社会科学研究专项任务项目(工程科技人才培养研究) (13JDGC009)；湖北省科技支撑计划软科学研究类一般项目(2015BDF087).

张瑞军(1972-)，男，武汉科技大学教授，博士. E-mail：zrjdoctor@126.com

TP311

A

1674-3644(2015)05-0385-06