衛(wèi) 娟，戴 冬

（河南機電高等?？茖W校計算機科學與技術系，河南 新鄉(xiāng) 453000）

1 引言

關系運算理論是施加于關系上的一組高級運算，是關系數(shù)據(jù)庫查詢語言的理論基礎。關系數(shù)據(jù)庫之所以取得了巨大成功和廣泛應用，就是因為它具有適合關系運算的集合運算、投影、連接、選擇和除法運算的數(shù)學基礎，以及以這些運算為基礎而建立起來的其他各種運算;從而可以對二維表格形式的關系進行任意的分割和組裝，構造出用戶所需的各種表格，方便實現(xiàn)對數(shù)據(jù)庫的查詢、插入、修改和刪除。

在關系代數(shù)運算中，交、除法、連接、自然連接四種運算可以用集合理論定義外，還可以用并、差、廣義笛卡爾積、投影和連接五種基本關系代數(shù)運算表示。其中，除法運算相對于選擇、投影、連接來說是較難的一種運算。

除的引入其實是一個反問題的問題，如關系表學生選課表(學號、課程號、成績)、學生表(學號、姓名、性別、年齡、籍貫)、如何查找出被全部學生都選修的課程號，則要用到除法。

除法是寫為R÷S的二元關系。其結果由 R中元組到唯一于R的屬性名字(就是說只在R表頭中而不在S表頭中的屬性)的限制構成，并且它們與S中的元組的所有組合都存在于 R中［1］。

在關系運算中，除法運算可理解為笛卡爾積的逆運算。設被除關系R為r元關系，除關系S為s元關系，那么它們的商為r-s元關系，記為R÷S。商的構成原則是:將被除關系R中的r-s列，按其值分成若干組，檢查每一組的s列值的集合是否包含除關系S，若包含則取r-s列的值作為商的一個元組，否則不?。?］。

2 除法定義的理解

除運算是同時從關系的水平方向和垂直方向進行運算。設兩個關系R和S的元數(shù)分別為r和s(r＞s＞0)，那么R÷S是一個(r-s)元的元組的集合。(R÷S)是滿足下列條件的最大關系，其中每個元組t與S中每個元組u組成的新元組必在關系R中［2］。

R÷S的具體計算過程如下:

假設關系S的屬性是關系R中后面的s個屬性，則R÷S的算法如下所示:

第一步:計算 R 的投影:T=π1，2，…，r-s(R)

第二步:計算T×S中不在R中的元組:V=(T×S)-R

第三步:計算 V 的投影:W=π1，2，…，r-s(V)

第四步:計算結果:R÷S=T-W

3 算法實例講解

例題1:已知關系R和S如圖1所示。其中，R中有屬性 A、B、C、D，S中有屬性 C、D，求 R ÷S的運算結果。

R

圖1 表R和表S

根據(jù)算法可知，r=4，s=2，所以有:

(1)計算 T=π1，2(R)，結果如圖2所示。

圖2 π1，2(R)結果集

(2)計算T×S中不在R中的元組:V=(T×S)-R，結果如圖3所示。

圖3 (T×S)-R結果集

(3)計算V的投影:W=πA，B(V)，結果如圖4所示。

圖4 πA，B(V)的結果集

(4)計算R÷S，結果集(1)如圖5所示。

圖5 R÷S結果集(1)

通過上述例題的計算過程，可以了解到，雖然此種方法步驟比較清晰，但此算法比較麻煩，求解步驟較多，每一步都必須謹慎，過程較為繁瑣，而且理解起來也比較難，算法較為費時。如果在計算過程中稍有不慎，則會造成整個計算結果錯誤的后果。

4 新算法的提出

經(jīng)過對常用算法的介紹和舉例說明，已經(jīng)較為清楚除法的計算過程。下面提出一種相交算法。此方法相對較為簡單且容易理解，學習起來較為容易。

設關系R和S的目數(shù)分別為r和s，且r＞s，S≠?。求R÷S。

算法分以下幾個步驟:

(1)∏1，2，…，s(S);

(2)按∏1，2，…，s(S)的元組求其在 R 中的映像。

(3)求映像的交集。

用上例中的例題，具體求解步驟為:

(1)S 中(C，D)的取值為{(c，d)，(e，f)}。

(2)假設{(c，d)，(e，f)}在 R 中的投影分別是M和N:

M={(a，b)，(e，d)}

N={(a，b)，(b，c)，(e，d)}

(3)求M和N的交集。

M∩N={(a，b)，(e，d)}

所以R÷S的結果集(2)如圖6所示。

圖6 R÷S結果集(2)

通過上述的算法介紹，可以看只要將每一個除數(shù)中的元組在被除數(shù)中的象集找到，然后再求象集的交集，則會很快地求出除法的結果。由此可以看出此算法容易掌握，而且計算速度也較快，使人容易接受此種算法。

5 結語

除法運算較為難理解和掌握，所以在做除法運算時，不能急于求成，要根據(jù)算法和步驟進行計算。除法的運算方法還有其他的算法，例如求象集等方法，但不論是哪種算法，都要對算法熟悉，并要熟練的掌握。要對除法有熟練的掌握，可以通過做大量的習題來達到目的。本文提出的相交算法相對于其他算法來說，學習起來比較容易理解和掌握，在一定意義上說解決了除法運算在理解難及掌握難方面的問題。

［1］李俊山.數(shù)據(jù)庫原理及應用(SQL Server)［M］.北京:清華大學出版社，2009.

［2］狄文輝.數(shù)據(jù)庫原理及應用——SQL Server［M］.北京:清華大學出版社，2008.

［3］石玉強.數(shù)據(jù)庫原理及應用［M］.北京:中國水利水電出版社，2009.