|
|
算法是计算机科学中一个重要的研究方向，是解决复杂问题的关键。在计算机世界中，算法无处不在。数据库是存储数据和执行大批量计算的场所，在数据库中使用一些简单的 SQL 命令，进行存储、查询、统计、以解决现实世界中的问题已经是屡见不鲜。随着数据量的大幅度增加和业务规则的日益复杂，越来越需要一种专门的方法来满足效率和准确性方面的要求。如何把解决问题的复杂算法转换为数据库能够执行的命令，也是数据库应用技术研究的一个方面。本文以 MSSQL 中的命令来阐述例子。
数据库中可以存储实体的数据集合，在进行运算时，数据库使用批量计算的方法来处理数据，批量的从存储设备上读取数据，处理之后又批量的写回存储设备。有的数据库提供了游标，游标可以读取出表中一行的数据中的每一个字段，对这些字段进行复杂的业务规则计算，然后再写回数据库中。与使用批量的方法比较，批量计算的方法消耗的资源相对比较少，而使用游标则占用太多的资源，速度比较慢，效率较低并且还有加锁条件等许多的限制。
比如对于数据库中存储了学生成绩 student_Score(sno,cno,score,level) ，成绩从 0 分到 100 分不等，如果需要在分数的后面存储一个字段字 level 来说明成绩的优劣， 90 分以上的 A ， 80-90 分为 B ， 60-80 分的为 C ， 60 分以下的为 D, 以下有几种算法都可以达到同样的目标：
1. 定义一个游标，选择 student_Score 表中所有的成绩记录，定义一个存储成绩的变量 @cur_score ，存储当前纪录的分数，定义一个存储当前分数所在成绩级别的变量 @cur_level, 用以存储成绩好坏的标记。算法如下：如果游标中的纪录不为空，从游标中取出当前纪录的成绩，判断成绩所在的分数段，把结果存储在变量 @cur_level 中 , 以 @cur_level 中的值更新当前纪录中的 level 字段。整个过程需要至少读取数据库两次，一次为获得纪录，一次需要写入数据库，每条记录都需要经过这个过程，效率相对低。
2. 依次批量更新数据库，把所有的 level 字段的值设置为 D, 再次更新数据库，把成绩大于等于 60 的纪录的 Level 字段更新为 C, 依次更新 B,A 。这样做的一个缺点是有些纪录的 Level 字段被更新多次，比如一个记录最后的 Level 字段的值是 A, 则它首先被更新为 D, 依次被更新为 C,B,A 。这些重复的更新是可以被消除的，把算法改进一下就可以省去重复更新的花费。更新后的算法是这样的，把成绩介于 0 和 60 分的纪录的 Level 字段更新为 D ，依次更新各个分数段的成绩。实现的这种算法的 SQL 语句并不难写出，使用 Between…and… 表达式即可以表达例如介于 80 到 90 之间纪录的选择条件。
3. 鉴于第二种方法最后的分析，使用 between…and… 表达式同时参照一个表来更新纪录，则可以方便表达分数段与相应的 level 信息，把这些信息存储到一个表 level_about 中，在更新 student_score 表的过程中可以参照这个表。计算的过程中，需要把 level_about 表的内容读出来，然后进行计算。对于整个计算过程来说，牺牲空间和部分效率来换来操作方便，，由于现在计算机的速度相当快， level_about 表占用的空间又很小，这方面的损失可以忽略不记。 Level_about 表中的信息至少包含 3 个字段： start_score, 记录起始分数， end_score 记录终止分数 ,level 记录介于起始分数和终止分数之间的分数应该得到的成绩。表中的数据应该类似于这样： | Start_score<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" /> | End_score | level | | 0 | 59 | D | | 60 | 79 | C | | 80 | 89 | B | | 90 | 100 | A |
更新 student_Score 表中的纪录需要依据 Start_score 和 End_score 来判断当前记录中成绩所在的 Level, 在 MSSQL 中实现的 SQL 语句 :Update student_score set student_score.level=level_about.level from level_about where student.score between level_about.start_score and level_about.end_score 。比较以上 3 种方法，实现同一个目的采用不同的算法实现的效果是不同的。
一些简单的算法不需要经过修改就可以直接应用到数据库中，比如业务需要每天晚上都需要结算一天的情况，一周两次自动结算奖金，结算奖金时间在每周再周一和周四的晚上 0 点。为了实现系统的自动结算，需要使用系统的任务，给系统制订一个作业，指定每天晚上 0 点结算就可以实现系统的自动结算（由于结算的时间间隔可能是会变化，不能使用作业中的定时功能）。为了可以在周一和周四结算，在数据库中设置一个表 misc ，其中的字段相当于全局变量，表中只有一条纪录，使用其中的一个字段 (days) 来记录当前结算的次数，也就是以系统开始运行为标准经过的天数。系统执行任务同时更新 misc 表中的 days 使其增长 update misc set days=days+1 。业务需求是每周一和周四结算奖金，不难发现奇数次结算依次相差 7 天，偶数次结算依次相差 7 天，相邻奇数次和偶数此结算相差 3 天，可以使用求余的方式来统一这个问题。如果当前天数 (days) 与 7 求余结果为 0 或者当前天数 (days) 减去 3 之后求余的结果为 0 ，则当前天数是结算的日期。具体的实现的算法是 :1 、提取当前的天数到一个变量中 declare @days int set @days=(select days from misc),2. 判断是否满足结算条件 if @days%7=0 or (@days-3)%7=0 begin…..end 类似于这样简单的算法可以直接的应用到数据库中而不会发生问题。
复杂的业务规则需要复杂的算法，复杂的规则对于一个有具体数字的变量来说，实现起来已经比较复杂，如果应用到数据库中存储的杂乱无章的一大批数字，并且实现批量的计算，则需要对算法进行大幅度的调整。
比如业务规则需要在员工每 4000 元的奖金中扣除 400 元作为重复消费，并且在扣除最后的 400 元，重复消费一次奖励一件产品，需要在数据库中使用一个表 (award_repeat) 记录产生的重复消费。如果一次扣除的奖金不足 400 元，在下次结算的时候接着扣除，直到扣除的奖金够 400 元，然后奖励一件产品，进入下次的循环，比如现在奖金总数达到了 3600 元，则不会扣除，如果达到了 3700 元，则要扣除 100 元，如果达到了 7700 元，则要扣除 410 元，并且产生一个重复消费。
为了实现这个规则，在员工表（ member ）中记录每个员工奖金的总数（ [total_award] ），同时记录重复消费的次数 ([repeat_num]) ，在另外的过渡表 (award_day) 中记录每次的奖金和每次扣除重复消费的奖金，最后在奖金表 (award) 中综合当次奖金和当次结算需要扣除的重复消费就得到了当次结算实际发放的奖金。采用批量的计算方法，实现的算法是 : 在计算奖金之后，扣除重复消费之前把当前奖金累加到员工的 ([total_award]) 字段（ [total_award] ），记录没有扣除重复消费的所有的奖金总和。实现重复消费计算的的算法是，设定条件 (F1) 为在 member 表中存在奖金总数大于等于重复消费次数加 1 后乘以 4000 ，如果有满足条件 F1 的记录，则选择满足条件的纪录中主键和当前的日期 (days) 插入到重复消费表（ award_repeat ）中 , 然后更新 member 表中满足条件 F1 的 repeat_num 使其增加 1 ，重复检查条件 F1 ，直到 member 表中没有满足条件 F1 纪录。
扣除重复消费金额的算法相对比较复杂。综合考虑员工的总共奖金情况，他们处在不同范围，如图所示
绿色的部分是不用扣除的，×××的部分是需要扣除掉的。把问题统一在一起，所有的奖金总数总体分为两个部分，一部分在绿色的部分之中，一部分在×××部分之中。分别讨论这两种情况， 1 ，如果奖金总数落在绿色的范围之中，则需要扣除的奖金的总数（ A1 ）为重复消费的次数 (repeat_num) 乘于 400 ，而本次结算需要扣除的奖金金额为需要扣除的奖金的总数 (A1) 减去以前扣除的奖金的总数。 2 ，如果奖金总数落在×××的范围之中，则需要扣除的奖金总数不仅包括重复消费次数 (repeat_num) 乘于 400 ，而且还包括部分×××部分，而这些×××部分的可以这样计算得到：奖金总数（ total_award ）减去重复消费次数 (repeat_num) 乘以 4000 ，再减去 3600 ，即得到部分×××区域的金额。把需要扣除的金额加起来 (A2) ，减去已经扣除的金额总和就是本次结算需要扣除的奖金金额。
基于上述分析，算法分为两个部分，一个部分用于计算重复消费，相应的 Sql 语句为
while exists(select 1 from member where total_award>=(repeat_num+1)*4000)
begin
insert into award_repeat(turns,days,m_ID,award_type)
select @turns,@days,m_ID,0
from member
where total_award>=(repeat_num+1)*4000
-- 记录重复消费，以便于公司送产品
update member
set repeat_num=repeat_num+1
where total_award>=(repeat_num+1)*4000
-- 更新计算的结果 , 并进入循环
end
由于采用逐步增加 Repeat_num 的方法，每次计算重复消费之后更新重复消费的次数，经过有限次计算之后，循环结束，程序不会陷入死循环。
算法的第二部分实现分为两种情况，分别实现如下： (AwardRepeat 为视图，数据来自 award_day 表，视图的内容为员工编号 m_id 和相应编号扣除的奖金总和 , 由于一些员工没有扣除过奖金，需要使用外连接来确保完整性 )
第一种情况：奖金总额落在绿色部分
if exists(select 1 from member where total_award between 4000*repeat_num and 4000*repeat_num+3600)
begin
insertintoaward_day(turns,days,m_ID,award_num)
-- 批量的一次性插入需要扣除的奖金纪录
select @turns,@days,member.m_ID,(-1)*(400*repeat_num /*(A1)*/
+(case when award_numis
null then 0 else award_num end))
from member left join awardRepeaton(member.m_ID=awardRepeat.m_ID)
where total_award between 4000*repeat_num + 1 and 4000*repeat_num+3600
and(-1)*(400*repeat_num+(case when award_numis null then 0 else award_num end))<0
-- 确保扣除金额为 0 的纪录不被插入
end
第二种情况：奖金总额落在×××部分
if exists( select 1 from member where total_award between 4000*repeat_num+3600+1 and 4000*(repeat_num+1))
begin
insert into award_day(turns,days,m_ID,award_num)
select @turns, @days, member.m_ID,(-1)*(400*repeat_num + total_award-4000 * repeat_num-3600 /*A2*/
+(case when award_numis null then 0 else award_num end))
from member left join awardRepeaton(member.m_ID=awardRepeat.m_ID)
where total_award between 4000*repeat_num +3600+1and 4000*(repeat_num+1)
and(-1)*(400*repeat_num + total_award -4000* repeat_num-3600+(case when award_numis null then 0 else award_numend))<0
-- 确保扣除金额为 0 的纪录不被插入
end
实验结果： (award_day) 表的一部分 | award_day_id | turns | days | m_ID | award_num | | 181 | 5 | 13 | m000000000 | -20 | | 199 | 6 | 16 | m000000000 | -380 | | 252 | 9 | 25 | m000000000 | -330 | | 305 | 10 | 28 | m000000000 | -70 | | 332 | 11 | 31 | m000000000 | -400 | | 415 | 15 | 45 | m000000000 | -800 |
结论：在数据库中研究和实现算法有着相当大的困难，同时也是一种挑战。随着现实世界中业务规则的日益复杂，相应的数据库应用软件实现业务规则需要的算法也日益复杂，把复杂的算法应用在数据库中需要找到一个统一的方式，在熟悉业务规则的前提下，根据数据库的特点和相应的执行命令的能力，找到一种适合数据库批量计算的步骤是解决问题的关键。
----------------------------
原文链接:https://blog.51cto.com/tianli/32042
作者：凌辉
程序猿的技术大观园：www.javathinker.net
[这个贴子最后由 sunweiqin 在 2020-03-15 19:53:21 重新编辑]
|
|
Java技术网站 → 『 Java开发技术 』 → 『 数据结构和算法专题 』 → 基于SQL的数据库算法研究
消息
查看
搜索
好友
邮件
复制
引用
IP: 已设置保密