数据库多维迭代算法

关键词&＃xff1a;数据库 迭代 递归 多维

一、两种传统的数据库迭代结构算法

对于数据库的迭代结构&＃xff0c;有两种传统的算法&＃xff1a;递归算法和边界算法。

比如对于下面图1的结构&＃xff1a;

图1

递归算法的数据结构如表1所示&＃xff1a;

表1

父节点id如为负值&＃xff0c;表示这是一个根节点。

从表1可以看出&＃xff0c;我们用若干组父&＃xff0d;子递归的结构来表达完整的迭代结构。

这种算法很容易理解&＃xff0c;但是缺点也很明显&＃xff1a;

1. 要从任意一个节点展现整个结构时&＃xff0c;要从此节点向根节点做一个逆向递归&＃xff0c;然后由根节点向所有层的子节点做N次正向递归&＃xff0c;数据库的运算开销很大。特别是正向递归到达所有外围节点时要做一个空查询&＃xff0c;形成浪费。
2. 尽管oracle对递归查询有优化算法&＃xff0c;如

select distinct *
from table1
start with 节点值&＃61;&＃39;1111&＃39;
connect by prior 节点id&＃61;父节点id

这样可以形成以’1111’为根的整个节点树结构。

但是这种优化在统计时是无能为力的&＃xff0c;而且此查询返回的结果丢失了很多结构的细节。

下面我们再来分析第二种迭代算法&＃xff1a;边界算法。

这种算法有点类似邮递员送信路径的传统数学难题&＃xff0c;方法是将节点的边界串起来&＃xff0c;同时记录其结构。

对于图1的结构&＃xff0c;数据库中记录如表2所示&＃xff1a;

表2

这里1001是此结构的id。因此我们可以用结构id&＃xff0c;仅通过一次查询&＃xff0c;就可以将整个结构展现出来。

此算法的缺点是&＃xff1a;

1. 取子结构麻烦&＃xff0c;比如我们要查询1113-1114-1115的子结构&＃xff0c;我们要从1113开始将整个结构截取出来&＃xff0c;然后分析哪些是它的子结构。
2. 数据更新麻烦&＃xff0c;在插入或删除某个子结构时&＃xff0c;要将节点顺序重新排序。

二、多维迭代算法的原理

所谓多维迭代算法&＃xff0c;是指任意一个节点&＃xff0c;在继承父节点的特性同时&＃xff0c;创建自己的特性维度。

对于图1的结构&＃xff0c;其数据库中的记录如表3所示&＃xff1a;

表3

我们可以看出&＃xff0c;任意一个节点都有其结构中的唯一维度&＃xff0c;而且往左减一个维度就是其父节点的维度。因此我们要取子结构也非常方便&＃xff0c;只要对节点维度从左开始截取若干位进行匹配就可以了。这种结构无需递归&＃xff0c;因此统计时效率得到级数级的提升。

下面介绍多维迭代的一些扩展算法&＃xff1a;

1. 查询子结构

如查询1113的子结构&＃xff0c;算法是取结构id&＃61;1001&＃xff0c;且节点2维维度&＃xff1d;’1,2’&＃xff0c;返回1113、1114、1115共3条数据&＃xff0c;且1114和1115是1113的子节点。

2. 插入子结构

如我们要将图2的子结构插入1116这个节点上&＃xff0c;即2221为1116的子节点&＃xff1a;

图2

则运算方法为&＃xff1a;首先获得2221的新维度(1,3,2)&＃xff0c;然后将整个子结构的第1维度更新为(1,3,2)&＃xff0c;最后最新子结构的结构id(1001)。

3. 取消子结构

假如我们要取消1116-1117-1118这个子结构&＃xff0c;那么首先获得新的结构id&＃xff0c;然后用1替换子结构的前2维(1,3)。

4. 替换子结构

假如我们用图2的子结构替换图1中1116-1117-1118的子结构&＃xff0c;或者说用2221替换1116&＃xff0c;则首先临时记录1116的结构id(1001)和维度(1,3)&＃xff0c;然后取消1116子结构&＃xff0c;然后更新2221子结构的id和维度。

三、多维迭代算法的典型应用

1. ERP缺料统计

我们知道ERP的BOM是一个典型的递归结构&＃xff0c;在进行缺料统计时&＃xff0c;要把最顶层的料号展开成所有底层料号的集合&＃xff0c;因此有很多的递归。

如果我们在表3的多维结构上增加数量属性&＃xff0c;就可以得到一个类似BOM的结构体。即使我们不改动BOM&＃xff0c;也可以通过第三方开发&＃xff0c;把BOM结构映射为一个多维结构范式&＃xff0c;从而减少递归运算。

2. 包装装配数据统计

生产上的包装和装配数据通常采用递归结构&＃xff0c;如果要对多组数据进行统计的话&＃xff0c;要进行成千上万次的递归&＃xff0c;效率极低。

如果包装和装配数据都采用多维结构存储的话&＃xff0c;只要一次查询就可以导出统计报表了&＃xff0c;而且报表数据还保留了完整的结构。

3. 数据仓库应用

如果要对递归数据进行数据仓库处理的话&＃xff0c;只要将递归结构映射为一个多维结构&＃xff0c;就可以方便地储存和统计递归数据&＃xff0c;同时保留其结构。

4. 家谱

我们只要在多维结构上分别定义父亲维度和母亲维度&＃xff0c;就可以方便地进行多数家谱运算。