层次模型
1.层次模型概述
用树形结构表示实体之间联系的模型叫层次模型。层次模型是最早用于商品数据库管理系统的数据模型。
层次型数据库管理系统是紧随网状数据库模型而出现的。现实世界中很多事物是按层次组织起来的。层次数据模型的提出,首先是为了模拟这种按层次组织起来的事物。层次数据库也是按记录来存取数据的。层次数据模型中最基本的数据关系是基本层次关系,它代表两个记录型之间一对多的关系,也叫做双亲子女关系(PCR)。数据库中有且仅有一个记录型无双亲,称为根节点。其他记录型有且仅有一个双亲。在层次模型中从一个节点到其双亲的映射是惟一的,所以对每一个记录型(除根节点外)只需要指出它的双亲,就可以表示出层次模型的整体结构。层次模型是树状的。 最著名最典型的层次数据库系统是于1969由IBM公司的IMS(Information Management System),这是IBM公司研制的最早的大型数据库系统程序产品。从60年代末产生起,如今已经发展到IMSV6,提供群集、N路数据共享、消息队列共享等先进特性的支持。
2.层次模型的结构
层次模型的表示方法是:树的结点表示实体集(记录的型),结点之间的连线表示相连两实体集之间的关系,这种关系只能是“1一M”的。通常把表示1的实体集放在上方,称为父结点,表示M的实体集放在下方,称为子结点。层次模型的结构特点是:
- (1) 有且仅有一个根结点。
- (2) 根结点以外的其它结点有且仅有一个父结点。
因而层次模型只能表示“1一M”关系,而不能直接表示“M—M”关系。在层次模型中,一个结点称为一个记录型,用来描述实体集。每个记录型可以有一个或多个记录值,上层一个记录值对应下层一个或多个记录值,而下层每个记录值只能对应上层一个记录值。例如,系记录型有:计算机系、电信系等记录值。而计算机系的下层记录值有软件、结构、应用等研究室和数据结构、操作系统、数据库等课程,软件研究室下层又有员工和项目记录值,如图所示:
关于层次模型中实体集之间多对多的联系的处理,解决的方法是引入冗余结点。例如,学生和课程之间的多对多的联系,引入学生和课程的冗余结点,转换为两棵树:一棵树的根是学生,子结点是课程,它表现了一个学生可以选多门课程;一棵树的根是课程,子结点是学生,它反映了一门课程可以被多个学生选。至于冗余结点可以用虚拟结点实现:在冗余结点处仅存放一个指针,指向实际结点。
3.层次模型的物理存储
层次模型的物理存储有两种实现方法:
- 顺序法:按照层次顺序把所有的记录邻接存放,即通过物理空间的位置相邻来实现层次顺序。
- 指针法:各个记录存放时不是按层次顺序,而是用指针按层次顺序把它们链接起来。
4.层次模型所受的限制
- 层次模型的树是有序树(层次顺序)。对任一结点的所有子树都规定了先后次序,这一限制隐含了对数据库存取路径的控制。
- 树中父子结点之间只存在一种联系,因此,对树中的任一结点,只有一条自根结点到达它的路径。
- 不能直接表示多对多的联系。
- 树结点中任何记录的属性只能是不可再分的简单数据类型。