基于SQL的数据库算法研究

简介:
算法是计算机科学中一个重要的研究方向,是解决复杂问题的关键。在计算机世界中,算法无处不在。数据库是存储数据和执行大批量计算的场所,在数据库中使用一些简单的SQL命令,进行存储、查询、统计、以解决现实世界中的问题已经是屡见不鲜。随着数据量的大幅度增加和业务规则的日益复杂,越来越需要一种专门的方法来满足效率和准确性方面的要求。如何把解决问题的复杂算法转换为数据库能够执行的命令,也是数据库应用技术研究的一个方面。本文以MSSQL中的命令来阐述例子。
       数据库中可以存储实体的数据集合,在进行运算时,数据库使用批量计算的方法来处理数据,批量的从存储设备上读取数据,处理之后又批量的写回存储设备。有的数据库提供了游标,游标可以读取出表中一行的数据中的每一个字段,对这些字段进行复杂的业务规则计算,然后再写回数据库中。与使用批量的方法比较,批量计算的方法消耗的资源相对比较少,而使用游标则占用太多的资源,速度比较慢,效率较低并且还有加锁条件等许多的限制。
比如对于数据库中存储了学生成绩student_Score(sno,cno,score,level),成绩从0分到100分不等,如果需要在分数的后面存储一个字段字level来说明成绩的优劣,90分以上的A80-90分为B60-80分的为C60分以下的为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。这些重复的更新是可以被消除的,把算法改进一下就可以省去重复更新的花费。更新后的算法是这样的,把成绩介于060分的纪录的Level字段更新为D,依次更新各个分数段的成绩。实现的这种算法的SQL语句并不难写出,使用Between…and…表达式即可以表达例如介于8090之间纪录的选择条件。
3.鉴于第二种方法最后的分析,使用between…and…表达式同时参照一个表来更新纪录,则可以方便表达分数段与相应的level信息,把这些信息存储到一个表level_about中,在更新student_score表的过程中可以参照这个表。计算的过程中,需要把level_about表的内容读出来,然后进行计算。对于整个计算过程来说,牺牲空间和部分效率来换来操作方便,,由于现在计算机的速度相当快,level_about表占用的空间又很小,这方面的损失可以忽略不记。Level_about表中的信息至少包含3个字段:start_score,记录起始分数,end_score记录终止分数,level 记录介于起始分数和终止分数之间的分数应该得到的成绩。表中的数据应该类似于这样:
Start_score
End_score
level
0
59
D
60
79
C
80
89
B
90
100
A
更新student_Score表中的纪录需要依据Start_scoreEnd_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表中满足条件F1repeat_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
图(2
结论:在数据库中研究和实现算法有着相当大的困难,同时也是一种挑战。随着现实世界中业务规则的日益复杂,相应的数据库应用软件实现业务规则需要的算法也日益复杂,把复杂的算法应用在数据库中需要找到一个统一的方式,在熟悉业务规则的前提下,根据数据库的特点和相应的执行命令的能力,找到一种适合数据库批量计算的步骤是解决问题的关键。
本文转自凌辉博客51CTO博客,原文链接http://blog.51cto.com/tianli/32042如需转载请自行联系原作者

lili00okok
相关文章
|
2天前
|
SQL 存储 安全
数据库数据恢复—SQL Server数据库出现逻辑错误的数据恢复案例
SQL Server数据库数据恢复环境: 某品牌服务器存储中有两组raid5磁盘阵列。操作系统层面跑着SQL Server数据库,SQL Server数据库存放在D盘分区中。 SQL Server数据库故障: 存放SQL Server数据库的D盘分区容量不足,管理员在E盘中生成了一个.ndf的文件并且将数据库路径指向E盘继续使用。数据库继续运行一段时间后出现故障并报错,连接失效,SqlServer数据库无法附加查询。管理员多次尝试恢复数据库数据但是没有成功。
|
7天前
|
SQL 自然语言处理 网络协议
【Linux开发实战指南】基于TCP、进程数据结构与SQL数据库:构建在线云词典系统(含注册、登录、查询、历史记录管理功能及源码分享)
TCP(Transmission Control Protocol)连接是互联网上最常用的一种面向连接、可靠的、基于字节流的传输层通信协议。建立TCP连接需要经过著名的“三次握手”过程: 1. SYN(同步序列编号):客户端发送一个SYN包给服务器,并进入SYN_SEND状态,等待服务器确认。 2. SYN-ACK:服务器收到SYN包后,回应一个SYN-ACK(SYN+ACKnowledgment)包,告诉客户端其接收到了请求,并同意建立连接,此时服务器进入SYN_RECV状态。 3. ACK(确认字符):客户端收到服务器的SYN-ACK包后,发送一个ACK包给服务器,确认收到了服务器的确
|
8天前
|
SQL 存储 关系型数据库
关系型数据库SQL Server学习
【7月更文挑战第4天】
21 2
|
13天前
|
SQL 存储 Java
SQL数据库学习指南:从基础到高级
SQL数据库学习指南:从基础到高级
|
14天前
|
SQL 弹性计算 数据管理
数据管理DMS产品使用合集之sql server实例,已经创建了数据库,登录时提示实例已存在,该怎么处理
阿里云数据管理DMS提供了全面的数据管理、数据库运维、数据安全、数据迁移与同步等功能,助力企业高效、安全地进行数据库管理和运维工作。以下是DMS产品使用合集的详细介绍。
27 1
|
1天前
|
SQL 监控 安全
数据库安全:SQL注入防御实践
【7月更文挑战第11天】SQL注入攻击作为一种常见的网络攻击手段,对数据库的安全性和业务稳定构成了严重威胁。为了有效防御SQL注入攻击,开发者和数据库管理员应采取一系列实践措施,包括输入验证与过滤、使用参数化查询、限制数据库用户权限、使用Web应用程序防火墙、定期更新和打补丁、实施实时监控和审计以及使用HTTPS协议等。通过这些措施的实施,可以显著提升数据库的安全性,降低遭受SQL注入攻击的风险。同时,开发者和数据库管理员应持续关注新的安全威胁和防御技术,不断提升自身的安全防护能力。
|
2天前
|
SQL Java 关系型数据库
Java面试题:描述JDBC的工作原理,包括连接数据库、执行SQL语句等步骤。
Java面试题:描述JDBC的工作原理,包括连接数据库、执行SQL语句等步骤。
13 0
|
2天前
|
SQL 监控 Java
Java面试题:简述数据库性能优化的常见手段,如索引优化、SQL语句优化等。
Java面试题:简述数据库性能优化的常见手段,如索引优化、SQL语句优化等。
8 0
|
7天前
|
存储 算法 C语言
软考中级之数据库系统工程师笔记总结(二)数据结构与算法
软考中级之数据库系统工程师笔记总结(二)数据结构与算法
7 0
|
10天前
|
SQL 存储 搜索推荐
SQL游标的原理与在数据库操作中的应用
SQL游标的原理与在数据库操作中的应用