2016年4月18日
一种高效的数据库迭代结构算法——多维迭代算法
关键词：数据库 迭代 递归 多维
一、两种传统的数据库迭代结构算法
对于数据库的迭代结构，有两种传统的算法：递归算法和边界算法。
比如对于下面图1的结构：
图1
递归算法的数据结构如表1所示：
|
节点id
|
节点值
|
父节点id
|
|
1
|
1111
|
-2
|
|
3
|
1112
|
1
|
|
4
|
1113
|
1
|
|
5
|
1114
|
4
|
|
6
|
1115
|
4
|
|
7
|
1116
|
1
|
|
8
|
1117
|
7
|
|
9
|
1118
|
8
|
表1
父节点id如为负值，表示这是一个根节点。
从表1可以看出，我们用若干组父－子递归的结构来表达完整的迭代结构。
这种算法很容易理解，但是缺点也很明显：
1.
要从任意一个节点展现整个结构时，要从此节点向根节点做一个逆向递归，然后由根节点向所有层的子节点做N次正向递归，数据库的运算开销很大。特别是正向递归到达所有外围节点时要做一个空查询，形成浪费。
2.
尽管oracle对递归查询有优化算法，如
select distinct
*
from table1
start with 节点值='1111'
connect by prior 节点id=父节点id
from table1
start with 节点值='1111'
connect by prior 节点id=父节点id
这样可以形成以’1111’为根的整个节点树结构。
但是这种优化在统计时是无能为力的，而且此查询返回的结果丢失了很多结构的细节。
下面我们再来分析第二种迭代算法：边界算法。
这种算法有点类似邮递员送信路径的传统数学难题，方法是将节点的边界串起来，同时记录其结构。
对于图1的结构，数据库中记录如表2所示：
|
节点值
|
结构id
|
节点顺序
|
节点层次
|
|
1111
|
1001
|
1
|
1
|
|
1112
|
1001
|
2
|
2
|
|
1113
|
1001
|
3
|
2
|
|
1114
|
1001
|
4
|
3
|
|
1115
|
1001
|
5
|
3
|
|
1116
|
1001
|
6
|
2
|
|
1117
|
1001
|
7
|
3
|
|
1118
|
1001
|
8
|
4
|
表2
这里1001是此结构的id。因此我们可以用结构id，仅通过一次查询，就可以将整个结构展现出来。
此算法的缺点是：
1.
取子结构麻烦，比如我们要查询1113-1114-1115的子结构，我们要从1113开始将整个结构截取出来，然后分析哪些是它的子结构。
2.
数据更新麻烦，在插入或删除某个子结构时，要将节点顺序重新排序。
二、多维迭代算法的原理
所谓多维迭代算法，是指任意一个节点，在继承父节点的特性同时，创建自己的特性维度。
对于图1的结构，其数据库中的记录如表3所示：
|
节点值
|
结构id
|
节点维度
|
|
1111
|
1001
|
1
|
|
1112
|
1001
|
1,1
|
|
1113
|
1001
|
1,2
|
|
1114
|
1001
|
1,2,1
|
|
1115
|
1001
|
1,2,2
|
|
1116
|
1001
|
1,3
|
|
1117
|
1001
|
1,3,1
|
|
1118
|
1001
|
1,3,1,1
|
表3
我们可以看出，任意一个节点都有其结构中的唯一维度，而且往左减一个维度就是其父节点的维度。因此我们要取子结构也非常方便，只要对节点维度从左开始截取若干位进行匹配就可以了。这种结构无需递归，因此统计时效率得到级数级的提升。
下面介绍多维迭代的一些扩展算法：
1.
查询子结构
如查询1113的子结构，算法是取结构id=1001，且节点2维维度＝’1,2’，返回1113、1114、1115共3条数据，且1114和1115是1113的子节点。
2.
插入子结构
如我们要将图2的子结构插入1116这个节点上，即2221为1116的子节点：
图2
则运算方法为：首先获得2221的新维度(1,3,2)，然后将整个子结构的第1维度更新为(1,3,2)，最后最新子结构的结构id(1001)。
3.
取消子结构
假如我们要取消1116-1117-1118这个子结构，那么首先获得新的结构id，然后用1替换子结构的前2维(1,3)。
4.
替换子结构
假如我们用图2的子结构替换图1中1116-1117-1118的子结构，或者说用2221替换1116，则首先临时记录1116的结构id(1001)和维度(1,3)，然后取消1116子结构，然后更新2221子结构的id和维度。
三、多维迭代算法的典型应用
1.
ERP缺料统计
我们知道ERP的BOM是一个典型的递归结构，在进行缺料统计时，要把最顶层的料号展开成所有底层料号的集合，因此有很多的递归。
如果我们在表3的多维结构上增加数量属性，就可以得到一个类似BOM的结构体。即使我们不改动BOM，也可以通过第三方开发，把BOM结构映射为一个多维结构范式，从而减少递归运算。
2.
包装装配数据统计
生产上的包装和装配数据通常采用递归结构，如果要对多组数据进行统计的话，要进行成千上万次的递归，效率极低。
如果包装和装配数据都采用多维结构存储的话，只要一次查询就可以导出统计报表了，而且报表数据还保留了完整的结构。
3.
数据仓库应用
如果要对递归数据进行数据仓库处理的话，只要将递归结构映射为一个多维结构，就可以方便地储存和统计递归数据，同时保留其结构。
4.
家谱
我们只要在多维结构上分别定义父亲维度和母亲维度，就可以方便地进行多数家谱运算。
浅谈MES的通用设计之：过程数据的上传
MES的另一个常见应用是过程数据的上传。
车间现场的设备会产生大量过程数据，需要上传到MES，主要基于以下两个考虑：
1、
过程数据经过整理，可以用于统计分析。
2、
结果数据上传到MES后，MES会根据结果来判断产品的后续工序。
通常来说，不同行业有自己的专属工具，特别是自动测试台架有很强的定制性，软件也往往是高度定制的。
下面我尝试以实例说明，来探讨过程数据上传的通用设计。
某测试台架产生测试数据后，将关键数据写入PLC，上传到MES，MES根据传入数据的结果来决定将产品送入包装工位还是返修工位。
大致的设计思路是：
1、
MES将PLC的原始数据按照某种规则转换成标准的过程数据结构。
2、
MES判断结果，并执行对应的业务流程。
比如说，PLC的数据结构是：
|
字段
|
起始位
|
长度
|
示例
|
说明
|
|
String Length
|
0
|
3
|
011
|
PLC有效字符长度11
|
|
Result
|
3
|
1
|
P
|
测试结果，P表示成功，其它值表示失败
|
|
Item1
|
4
|
2
|
20
|
测试项1的值
|
|
Item2
|
6
|
3
|
120
|
测试项2的值
|
|
String End
|
9
|
2
|
OK
|
结束字符
|
现在我们在数据库中建一个表来表达通用的数据结构：
|
字段名
|
数据类型
|
说明
|
|
STATION
|
VARCHAR2(20 BYTE)
|
工位
|
|
ITEMNO
|
NUMBER(2,0)
|
参数序列
|
|
ITEMNAME
|
VARCHAR2(200 BYTE)
|
参数名
|
|
ITEMLENGTH
|
NUMBER(3,0)
|
参数长度
|
|
ITEMUNIT
|
VARCHAR2(20 BYTE)
|
参数单位
|
|
STATUSMARK
|
NUMBER(1,0)
|
值为1表示此参数用于判定测试结果
|
|
STATUSVALUE
|
VARCHAR2(20 BYTE)
|
判定测试通过的有效数据
|
那么此PLC数据结构在此表中这样定义：
|
STATION
|
ITEMNO
|
ITEMNAME
|
ITEMLENGTH
|
ITEMUNIT
|
STATUSMARK
|
STATUSVALUE
|
|
1234
|
1
|
Test Status
|
1
|
|
1
|
P
|
|
1234
|
2
|
Item1
|
2
|
G
|
|
|
|
1234
|
3
|
Item2
|
3
|
MM
|
|
|
有了这个结构作为参照，当我们接收到PLC的原始数据后，我们就可以解析出测试结果，以及测试项1、测试项2的值。
附加上产品序列号、测试工位、测试时间、测试人员这些基本数据，我们就得到完整的测试过程数据。
下面我们进一步就可以把过程数据保存到数据库中。
在数据库中建立一个主表，一个从表，其中主表保存产品序列号、测试工位、测试时间、测试人员、测试结果。从表保存所有测试项的名称、值和单位。
在数据库中再建立一个触发器，监控主表的创建，一旦有新的数据，则立即查询测试结果，根据结果的不同来执行对应的业务逻辑。
下面是实现数据解析及结果处理的示例代码(Oracel数据库)：
|
DECLARE
uploadstring VARCHAR2(2000);
leftstring
VARCHAR2(2000);
itemname
VARCHAR2(20);
itemvalue
VARCHAR2(2000);
itemunit VARCHAR2(2000);
itemlength
INTEGER;
statusmark
VARCHAR2(1);
statusvalue
VARCHAR2(1);
passfail
INTEGER;
CURSOR mycur IS
SELECT
t.itemno,
t.itemname,
t.itemlength,
t.itemunit,
t.statusmark,
t.statusvalue
FROM t -- à t是定义结构的表
WHERE t.station = I_STATION
ORDER BY t.itemno;
BEGIN
uploadstring
:= I_UPLOADSTRING;
leftstring
:= uploadstring;
itemname
:= 0;
itemvalue
:= uploadstring;
itemunit := '';
itemlength
:= 0;
statusmark
:= 0;
statusvalue
:= '';
passfail
:= 1;
-- 1. get all items 查询得到所有数据
FOR rec IN mycur
LOOP
itemname := rec.itemname;
itemlength := rec.itemlength;
statusmark := rec.statusmark;
statusvalue := rec.statusvalue;
itemvalue := SUBSTR(leftstring, 1,
itemlength);
--
1.1 check test status mark 找到判断结果的参数
IF statusmark = 1
THEN
if itemvalue = statusvalue
THEN
passfail := 1;
ELSE
passfail := 0;
END
IF;
END IF;
leftstring := SUBSTR(leftstring,
length(itemvalue)+1,1000);
END LOOP;
-- 1.2 add test data master 插入数据到主表
SP_INS_TESTDATAMST
(
I_ESN,
I_STATION,
I_TIME,
I_OPERATOR,
passfail,
O_MSTID -- à 主表流水号
);
COMMIT;
--
2 add test data detail插入数据到从表
leftstring := uploadstring;
FOR
rec2 IN mycur
LOOP
itemname := rec2.itemname;
itemlength := rec2.itemlength;
statusmark := rec2.statusmark;
statusvalue := rec2.statusvalue;
itemunit := rec2.itemunit;
itemvalue := SUBSTR(leftstring, 1,
itemlength);
--
1.1 check NOT test status mark
IF statusmark = 0
THEN
SP_INS_TESTDET
(
O_MSTID,
itemname,
itemvalue,
itemunit
);
COMMIT;
END IF;
leftstring := SUBSTR(leftstring,
length(itemvalue)+1,1000);
END LOOP;
END;
|
订阅：
博文 (Atom)
博文
