元組關系演算論文

導語：元組關系演算論文一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

摘要針對一些文獻存在的問題，本文指明了特性謂詞在元組關系演算中的表達形式，給出了含量詞的元組關系演算表達式到SQL語句的轉化過程，并通過具體實例加以說明。

關鍵詞元組關系演算；特性謂詞；全稱量詞；存在量詞；SQL

1引言

20世紀60年代誕生的數據庫技術，經過近半個世紀的發展，形成了堅實的理論基礎、成熟的商業產品和廣泛的應用領域。E.FCodd提出的關系數據模型為當今主流的數據庫管理系統提供了堅實的數學基礎。關系數據模型有三種等價的操作語言：關系代數、SQL、關系演算(元組關系演算和域關系演算)，它們的非過程化程度依次遞增，主要應用領域也不同。SQL是關系數據庫的標準語言，關系代數和關系演算是它的理論基礎。大多商用的DBMS先把用戶提交的SQL查詢轉化成等價的擴展關系代數表達式，在執行之前需要根據等價規則對其優化[9]。關系演算是以數理邏輯中的謂詞演算為中心的，按謂詞變元的不同，分為元組關系演算和域關系演算。在實際應用中，元組關系演算通常用來輔助生成帶量詞的SQL語句[3][4][6]，域關系演算以著名的QBE為代表，直觀易學，適合于非專業人員使用，目前在ACCESS、PowerBuilder的查詢生成器中有類似的應用。

將用戶提出的查詢要求轉化為可執行的SQL語句，是一個非形式化描述向形式化規范轉變的過程，完全借助計算機來實現是非常困難的，一般由專業技術人員根據經驗來完成。SQL語言是非過程化的，與常用的過程化的命令式語言有很大的區別。用戶要完成一個查詢，只需要用SQL語言提出要求，無須指明怎么做。在實際應用中，用戶往往提出含有“全部”、“至少”等條件的查詢，它們不容易采用SQL表達，這時可求助于元組關系演算，大致過程為：①寫出查詢的元組關系演算表達式；②根據等價轉化規則得到不含全稱量詞的元組關系演算表達式；③將元組關系演算表達式轉化為SQL語句。迄今為止，國內外有很多文獻和書籍都討論過相關的內容，然而有些理論細節并沒有詳細解釋，在一定程度上妨礙了人們對數據庫知識的理解和應用，產生了一些錯誤[1][2][5]。本文將就這一問題進行討論。

2元組關系演算與SQL

確定一個元組關系演算表達式，首先要分析需要使用的關系模式，確定相互之間的參照完整性約束。在特殊情況下，一個關系模式還有可能使用多次，則可通過引入不同的元組變量來區分。其次，將賦值和限定條件加入到元組關系演算表達式中。關于限定條件如何表示這一問題，很多數據庫教材和文獻中并沒有仔細討論，結果產生了一些問題。

在謂詞邏輯中，全總個體域包含了所有個體變元的所有個體域，它統一了個體變元的取值范圍，但不同論述對象需用不同的特性謂詞加以再刻畫[8]。對于全稱量詞，特性謂詞作為蘊涵式的前件加入；對于存在量詞，特性謂詞作為合取項加入。在元組關系演算表達式中，元組的限定條件即是特性謂詞，書寫時也必須遵循上述兩條基本規則。在文獻[1]、[2]、[5]中，對于全稱量詞，均將限定條件作為合取項，這樣造成元組關系演算表達式的語義不符合查詢要求，無法表示正確的查詢結果。我們經常會遇到這樣的情況：對于同一個查詢，從不同的角度理解，可以寫出不同的元組關系演算表達式。假定有兩個不同的表達式A和B，且A是正確的，那么根據謂詞邏輯的完備性，如果由A無法通過推理規則得到B，則A與B的語義不同，那么B一定是一個錯誤的表達式。這種方法通常被用來判斷一個元組關系演算表達式是否正確。

在上述分析的基礎上，對于含“全部”、“至少”等條件的查詢，從分析入手，得到元組關系演算表達式，再轉化為SQL語句，一般要經歷下面三個過程：

根據查詢的語義，以元組變量為主導，寫出一個“規范”的元組關系演算表達式。這里所謂的“規范”，是指針對每個元組變量，其后的原子公式均以關系模式、限定條件和賦值的順序出現，在最大的限度上保證量詞轄域收縮到最小情況。特別需要注意的是限定條件(關系模式也可認為是一種特殊的限定條件)針對全稱量詞和存在量詞的不同表示方法。

將元組關系演算表達式中的全稱量詞∀全部轉化為存在量詞∃。因為在SQL語言中不存在全稱量詞，只有與存在量詞對應的EXISTS謂詞，需要使用下列的等價式將元組關系演算表達式中的全稱量詞轉化為存在量詞。

將元組關系演算表達式轉化為SQL語句，處理的過程由外向內，依次為：

(1)將最外層的∃、本層的限定條件和最后的賦值部分轉換為SELECT、FROM、WHERE子句。

(2)內層的∃、本層的限定條件轉化為SELECT、FROM、WHERE子句，此子查詢作為EXISTS謂詞的條件加入到上一層SQL語句的WHERE子句中。

注意：由于帶有EXISTS謂詞的子查詢只產生邏輯真假值，不返回任何數據，因此內層的SQL語句的目標列表達式通常都使用*。

3例子

下面以“供應商供應工程零件”這一數據庫模式為例[6]，對由元組關系演算表達式得到SQL語句的過程加以解釋。該數據庫模式包含四個表：供應商表S(Sno，Sname，Status，City)，各屬性分別表示供應商代碼、供應商姓名、供應商狀態、供應商所在城市；零件表P(Pno，Pname，Color，Weight)，各屬性分別代表零件代碼、零件名、顏色、重量；工程項目表J(Jno，Jname，City)，各屬性分別代表工程項目代碼、項目名、項目所在城市；供應情況表SPJ(Sno，Pno，Jno，QTY)，各屬性分別代表供應商代碼、零件代碼、工程項目代碼、供應數量，表示某供應商將某種零件以一定數量供應給某工程項目。要求查詢至少使用了供應商S1所供應的全部零件的工程號Jno分析此查詢，發現查詢結果中的工程信息來源于表J，而供應商S1供應的所有零件，工程使用所有的零件這兩種信息都來源于同一個表SPJ，在元組關系演算表達式中需要使用兩個元組變量來加以區分，可得到如下的元組關系演算表達式：

{t|∃u(J(u)∧∀v(SPJ(v)∧v[1]=''''S1''''→∃w(SPJ(w)∧w[1]=v[1]∧w[2]=v[2]∧w[3]=u[1]))∧t[1]=u[1])}

注意在上述的表達式中，蘊涵不能使用合取來替代。此查詢的元組關系演算表達式可能出現多種形式，只要是正確的，就一定可以通過謂詞邏輯的推理規則進行等價推導，得到上述“規范”的元組關系演算表達式。

根據全稱量詞向存在量詞的等價轉換公式，可以得到：

{t|∃u(J(u)∧┐∃v(SPJ(v)∧v[1]=''''S1''''∧┐∃w(SPJ(w)∧w[1]=v[1]∧w[2]=v[2]∧w[3]=u[1]))∧t[1]=u[1])}

這個元組關系演算表達式的語義為：對所求的工程，不存在這樣的零件，供應商S1供應了它，而工程沒有使用。從而在語義上也印證了上面語法推導的正確性。

根據前面的元組關系演算表達式到SQL語句的轉化規則，寫出如下SQL語句。

SELECTJno

FROMJ

WHERENOTEXISTS

(SELECT*

FROMSPJX

WHEREX.Sno=''''S1''''ANDNOTEXISTS

(SELECT*

FROMSPJY

WHEREY.Jno=J.Jno

ANDY.Pno=X.Pno

ANDY.SnoO=X.Sno))；

參考文獻[7]中的元組演算表達式和SQL語句，發現與本文有兩點區別：

文獻[7]中的元組演算表達式和SQL語句使用的關系模式不是一一對應的，而且在SQL語句中使用的關系全部為SPJ。這樣如果SPJ中沒有任何元組，查詢結果為空，而本文中的SQL語句將會從J中選擇所有的工程號。

對比本文的結果，文獻[7]中的元組演算表達式缺少了限定條件w[1]=v[1]，相應在SQL語句中缺少了Y.Sno=X.Sno。假設出現這樣的情況：若供應商S1供應的零件供應商S2也供應，工程J2使用了S2供應的所有零件，但是沒有使用S1生產的零件，那么執行文獻[7]中的SQL語句，結果將包含工程J2，而這顯然是不正確的。

4結語

數理邏輯在計算機科學中具有不可動搖的重要地位，E.W.Dijkstra就曾經說過，我現在年紀大了，搞了這么多年軟件，錯誤不知犯了多少，現在覺悟了。我想，假如我早年在數理邏輯上好好下點功夫的話，我就不會犯這么多的錯誤。數理邏輯是數據庫理論研究的基礎，同時謂詞邏輯是SQL語言的數學基礎。計算機專業人員必須完全掌握謂詞邏輯的語法、語義和推理規則，才能寫出正確、優美的SQL語句。

參考文獻：

[1]丁寶康，“SQL語言中量詞和空值的使用技術[J]”，《計算機研究與發展》，1994，31

[2]劉智斌，“關系演算運行機制的分析與研究[J]”，《計算機應用研究.》，2003，10

[3]馬林德，“淺談帶量詞的SQL語句的使用方法[J]”，《蘇州大學學報(工學版)》，2003，23

[4]宗恒，“關系演算和SQL中使用量詞和實現蘊涵的教學方法探討[J]”，《高師理科學刊》，2005，25

[5]黃德才，數據庫原理及其應用教程[M]，北京，科學出版社，2002

[6]薩師煊、王珊，數據庫系統概論[M]，北京，高等教育出版社，2000

[7]王珊、朱青，《數據庫系統概論》學習指導與習題解答[M]，北京，高等教育出版社，2003

[8]方世昌，離散數學[M]，西安，西安電子科技大學出版社，1996

[9]RamezElmasri，ShamkantB.Navathe，數據庫系統基礎[M]，北京，人民郵電出版社，2002