树型结构在关系数据库中的描述

方银清

(集美大学 信息工程学院，福建 厦门 361009)

0 引言

数据库是现代计算机信息处理的核心，特别是大数据处理．从上世纪80年代以来，关系数据库以其安全性、数据完整性、良好的数据接口得到快速的发展[1-2]．而树型结构是现实世界中常用的一种非线性的数据结构，如家庭族谱、机器零件、单位组织结构等等．树型结构的计算机信息处理必须进行数据结构的转换，把非线性的数据结构转换为关系数据模型，进而把数据存入数据库．而这正是树型结构计算机处理的难点之一．

1 树型结构的属性

树型结构是一种非线性数据结构，除根节点外，每个节点都只有一个前驱，为该节点的双亲节点．每个节点可以有多个后继，称为孩子节点，没有孩子的节点称为叶子．从一个节点到其子孙节点的分支称为路径．从根节点到该节点路径上所有的节点称为该节点的祖先．如图1所示，树型结构明显具有层次关系，根节点A属于第1层，BCD属于第2层，EFGH 属于第3层，IJKL属于第4层．从理论上看，树型结构的每个节点都和其它的节点具有关系，关系密切的节点包括它的祖先和子孙[3-4]．

2 树型结构的问题

树型结构的核心是数据元素之间一对多的关系．然而在关系数据库中，表是以行和列的形式组织起来的数据集合，数据元素之间呈线性排列，彼此间没有关系．如何在关系数据库中设计树型数据结构并有效应用，是我们要解决的问题[2]．关系数据库用一张二维表表示一个具有共同属性节点的集合，每条记录表示一个节点．但是记录的先后顺序和节点之间的关系无关．节点与节点之间的关系也可通过二维表表示，但必须具有相同的外键．对于具有n个节点的树型结构，理论上要建立n(n-1)/2张表来描述它们之间的关系，这必然造成大量的数据冗余，而且给数据完整性的维护造成困难．

图1 一棵树的结构图

要描述树型结构的节点之间的关系，通常的做法记录节点的同时记录其双亲节点的地址或关键字．这种方法只能直接描述其双亲，不能直接描述它的其他祖先或子孙，这种方法叫做双亲表示法．另外一种方法就孩子表示法，记录本节点的同时记录所有孩子的关键字．这种方法的问题在于，事先不知道每个孩子的个数，会造成表结构的不确定．同样的，这种方法只能直接描述其孩子，不能直接描述它的祖先和其他的子孙，这种方法叫做孩子表示法．这两种方法共同的不足在于，要描述某节点的所有的祖先和子孙，必须编写算法进行遍历计算．不能利用关系数据库所提供SQL查询语言来直接进行查询．而SQL语言是关系数据库系统所使用的唯一的数据语言，功能非常灵活强大，可以实现数据定义、数据操作和数据控制等功能[5-11]．

3 树型结构的路径表示方法

一种新的路径表示方法可以比较好地解决上面方法所遇到的问题．路径表示法的本质在于把树型结构线性化,关系数据库只记录从根节点到所有叶子节点的路径,并且从左到右编号．如图1所示，该图共有5个叶子节点HIJKL，因此共需记录5条路径：路径1：ABEI；路径2：ABEJ;路径3：ABFK;路径4：ACGL;路径5：ADH．

4 数据库表的设计

设计一个关系TREE(路径号，节点ID，节点名称，节点所在层)以记录图1 中节点的关系，即根节点到叶子的路径，如图2所示．节点所在层为节点在树中的层数，A在第1层，BCD在第2层，EFGH在第3层，IJKL在第4层.利用ACESS数据库，创建一张表，名称为TREE．录入数据后如图3 所示．

图2 树的存储表结构

图3 树在表TREE中的数据表示

5 节点关系SQL查询

在应用树型结构时，经常需要查询的功能有：能获取任意节点的子节点集或子孙节点集；能获取任意节点的父节点集或祖先节点集[11]．录入数据后，就可以利用方便灵活的SQL语言，来进行各种查询．

(1)查询某个节点的祖先，如节点E的祖先．首先，查出节点E所在的路径号和节点在树中的层数：

Select path，layer from tree where name=′E′;结果如图4．

图4 节点E的路径和层

再查出E节点的祖先：

Select id,name from tree where path=1 and layer<3 order by layer；结果如图5．

图5 节点E的祖先

(2)查询节点E的所有子孙.

Select id,name from tree where layer>3 and path in (select path from tree where name=′E′)； 结果如图6．

图6节点E的子孙

(3)查询节点E的所有兄弟和堂兄弟.

Select distinct(name) from tree where layer=3； 结果如图7．

图7 节点E的兄弟和堂兄弟

6 结语

把非线性的树型结构转化成线性的关系数据库模型，是计算机处理树型结构的难点．利用路径法解决上述问题，并且可以利用现成的SQL语言对关系数据库进行操作，不用重新编程，不用重新改造SQL语言，就可以在数据库中对树型结构进行各种操作和查询．对这种非线性数据结构的信息处理具有很大的实用性．是非线性数据结构线性化方法的一种突破．

[1]杨 帆,沈来信.基于树型结构的数据库管理软件的设计[J].黄山学院学报,2014,16(3):38～41.

[2]吕 刚,蒋勇铭,王 军.基于关系数据库的树形结构设计与实现[J].计算机光盘软件与应用,2012,(17):224～225.

[3]陈世东,黄有群.Oracle中的递归查询算法在一般数据库的实现[J].沈阳工业大学学报,2001,23(5):432～436.

[4]赵爱芹,陈和平,熊健驰.关系数据库层次树查询机制浅析[J].计算机工程与设计,2006,27(18):3454～3456.

[5]张华兴,孙 毅,单继宏.网页树形结构自动生成研究[J].计算机系统应用,2009,18(7):61～66.

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

[7]林子雨,杨冬青,王腾蛟.基于关系数据库的关键词查询[J].软件学报,2010,(10):2454～2478.

[8]宋彩霞,新 春.Oracle数据库基于索引SQL优化方法的研究与实现[J].计算机工程与设计,2004,25(12):2327～2330.

[9]李书振.ySQL数据库的安全机制[J].计算机应用,2002,22(6):51～53.

[10]兰旭辉,熊家军,邓 刚.基于MySQL的应用程序设计[J].计算机工程与设计,2004,25(3):442～444.

[11]邓宏涛.关系数据库中树型结构信息的处理方法研究[J].江汉大学学报(自然科学版),2010,38(2):50～53.