学习基于SQL数据库的算法(1)

算法是计算机科学中一个重要的研究方向，是解决复杂问题的关键。在计算机世界中，算法无处不在。数据库是存储数据和执行大批量计算的场所，在数据库中使用一些简单的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 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