衛(wèi) 娟，戴 冬

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

1 引言

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

在關(guān)系代數(shù)運(yùn)算中，交、除法、連接、自然連接四種運(yùn)算可以用集合理論定義外，還可以用并、差、廣義笛卡爾積、投影和連接五種基本關(guān)系代數(shù)運(yùn)算表示。其中，除法運(yùn)算相對于選擇、投影、連接來說是較難的一種運(yù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)系運(yùn)算中，除法運(yùn)算可理解為笛卡爾積的逆運(yù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列的值作為商的一個元組，否則不取［3］。

2 除法定義的理解

除運(yùn)算是同時(shí)從關(guān)系的水平方向和垂直方向進(jìn)行運(yù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的具體計(jì)算過程如下:

假設(shè)關(guān)系S的屬性是關(guān)系R中后面的s個屬性，則R÷S的算法如下所示:

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

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

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

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

3 算法實(shí)例講解

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

R

圖1 表R和表S

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

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

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

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

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

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

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

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

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

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

4 新算法的提出

經(jīng)過對常用算法的介紹和舉例說明，已經(jīng)較為清楚除法的計(jì)算過程。下面提出一種相交算法。此方法相對較為簡單且容易理解，學(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é)果。由此可以看出此算法容易掌握，而且計(jì)算速度也較快，使人容易接受此種算法。

5 結(jié)語

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

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

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

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