时间：2022-11-03 22:30:01 | 来源：信息时代
时间：2022-11-03 22:30:01 来源：信息时代
内存数据库图论存取方法 : 基于图论的按“内存数据库图”来物理组织和存取内存数据库的一种方法,简称内存数据库图论存取方法。该方法能充分利用内存存取速度快、占存储空间少的特点,来组织和存取数据。下面介绍相关的概念、物理数据结构及其查询与维护操作。
1. 内存数据库图
将数据库及其索引集成在一起以一个称为内存数据库图(MM-DBG)的 “标值” (valued)对偶图(bipartite graph)来存储。该图由一个元组顶点子集TDB、一个属性值顶点子集VDB和连接这两个顶点子集的一个“标值”Rk的边(t,v,Rk)集组成。元组顶点子集包含所有表数据库中元组的顶点; 属性顶点子集包含所有代表数据库中属性值的顶点。元组顶点集中的元组不直接包含其属性值,而是对其每一属性值以一条边与相应的属性值顶点相连。同样,属性值顶点集的值与取它作为一个属性值的每一元组以一条边相连。边(t,v,Rk)表示t是关系R的元组,其第k个属性值为v。各种操作的中间结果以“临时边”被连接到有关的基本关系的元组,这样整个存储数据库就是一个存储的MM-DBG。
图1给出了MM-DBG的一个例子,其中图1(a)是两个关系“学生”和“系”组成的数据库DB,分图1(b)是DB的MM-DBG。
MM-DBG结构图有下列特性:
(1) 同一子集的任何两顶点之间都没有边。
(2)查询就是元组顶点及其相连属性值顶点间的一次交替访问。
(3)具有同一属性值的同一或不同关系的任意两个元组之间存在一条长度为2的路径。
(4)元组顶点子集按关系形成一种划分,属性值顶点子集按值域形成一种划分。
图1 关系ST和DT的MM-DBG结构
在线咨询
