關(guān)系代數(shù)中除法運算相交算法的探討*

衛(wèi) 娟，戴 冬

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

1 引言

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

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

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

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

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

2 除法定義的理解

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

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

假設(shè)關(guān)系S的屬性是關(guān)系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)

第四步:計算結(jié)果:R÷S=T-W

3 算法實例講解

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

R

圖1 表R和表S

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

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

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

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

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

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

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

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

圖5 R÷S結(jié)果集(1)

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

4 新算法的提出

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

設(shè)關(guān)系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)假設(shè){(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的結(jié)果集(2)如圖6所示。

圖6 R÷S結(jié)果集(2)

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

5 結(jié)語

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

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

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

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