從算法入手講解如何在資料庫中實作最優最簡

　　算法是計算機科學中一個重要的研究方向，是解決複雜問題的關鍵。在計算機世界中，算法無處不在。資料庫是存儲資料和執行大批量計算的場所，在資料庫中使用一些簡單的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

　　比較以上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紀錄。

　　結論：在資料庫中研究和實作算法有着相當大的困難，同時也是一種挑戰。随着現實世界中業務規則的日益複雜，相應的資料庫應用軟體實作業務規則需要的算法也日益複雜，把複雜的算法應用在資料庫中需要找到一個統一的方式，在熟悉業務規則的前提下，根據資料庫的特點和相應的執行指令的能力，找到一種适合資料庫批量計算的步驟是解決問題的關鍵。

引用：http://database.ctocio.com.cn/tips/277/7807277.shtml