題干中含有“至少”的關系代數查詢問題探討

摘 要 本文結合筆者多年的教學研究和實踐對關系代數查詢題干中含有“至少”的這樣一類查詢問題進行了闡述和探討，希望能夠對該類問題教學研究的發展有所幫助。

關鍵詞 關系代數 “連接”運算 “除”運算 “至少”

中圖分類號：O15 文獻標識碼：A DOI：10.16400/j.cnki.kjdkz.2017.01.028

An Approach to the Problem of Algebra Query with the "Least" in the Problem

CHENG Chen

（School of Computer Science and Technology， Nantong University， Nantong， Jiangsu 226019）

Abstract This paper combined of teaching research and practice of the author's stem contains described and discussed in such a class of queries “at least" query of relational algebra， hoping to help the development of teaching and research of this kind of problem.

Keywords relational algebra； connection operation； "removal" operation； “least”

1 關系代數概述

關系數據語言可以分為三類：關系代數、關系演算、既具有關系代數的特點又具有關系演算特點的語言（主要指SQL）。其中關系代數是用對關系的運算來表達查詢的。關系代數共有八種運算，按照運算方向的不同可以分為兩類：集合運算和專門運算。集合運算包括并、交、差、笛卡爾積，這類運算把關系看成是元組的集合，運算方向是元組的方向；專門運算包括選擇、投影、連接、除。這類運算不僅涉及到元組的方向，還有可能涉及到屬性列的方向。按照是否可以由其它關系運算導出，關系代數的八種運算也可以分為兩類：基本的關系運算和非基本的關系運算。基本的關系運算包括：并、差、笛卡爾積、選擇、投影；非基本的關系運算包括：交、連接、除。

2關系“連接”運算

連接運算屬于非基本的關系運算，連接運算的本質相當于笛卡爾積+選擇。兩個表進行連接運算，相當于先對兩個表進行笛卡爾積運算，然后對于笛卡爾積的結果施加某些條件進行選擇運算，最終得到連接運算的結果。按照選擇的條件中的比較運算符是否為等號可以將連接運算分為兩類：當比較運算符為等號時稱為等值連接，不是等號時稱為非等值連接。在等值連接中又有一種特殊的連接稱為自然連接：當兩個表具有公共屬性組，并且在結果中取消重復列的等值連接稱為自然連接。在具體查詢中用到的連接大部分都是自然連接。

3關系“除”運算

關系除運算也屬于非基本的關系運算。兩個關系進行除運算，要求兩個關系具有公共屬性組。假設兩個關系為A（P，Q）和B（Q，R），Q即為公共屬性組。A和B的除運算的結果是一個新的關系C（P），C是A中滿足以下條件的元組在P屬性組上的投影，元組在P上分量值p的象集包含B在Q上的投影。除運算在所有的關系運算中是最難的一種。

4 題干中含有“至少”的關系代數查詢問題的分析和解決

有這樣一類關系代數的查詢，其查詢的題干里含有“至少”這樣一個關鍵詞。對于這樣一類查詢問題，原則上可以考慮用除運算來解決。但是否一定用到除運算，則還要考慮是否有“確定的包含關系”，因為除運算的概念里其實就有“確定的包含關系”。于是可以把這樣一類查詢問題又細分為兩類：確定的包含關系、不確定的包含關系。

4.1 確定的包含關系

確定的包含關系需要使用除運算，下面舉三個實例加以說明。在以下的關系數據庫中查詢至少選修了讀者編號為“13050220”的讀者所借閱過的全部圖書的讀者的讀者編號、姓名、部門。

圖書（書號，書名，作者，出版社，類別，定價）

讀者（讀者編號，姓名，性別，年齡，部門）

借閱（書號，讀者編號，借閱日期，歸還日期）

上述查詢里有確定的包含關系：設該讀者所借閱圖書的圖書號所構成的集合為集合1，讀者編號為“13050220”的讀者所借閱過的圖書的圖書號所構成的集合為集合2，如果集合1包含了集合2，則就說明該讀者至少選修了讀者編號為“13050220”的讀者所借閱過的全部圖書。很顯然，上述的集合1和集合2都是確定的集合，所以此查詢要用到除運算。

表式： 讀者編號，書號（借閱）€鰲∈楹牛ā《琳弒嗪？‘13050220（借閱））∞ 讀者編號，姓名，部門（讀者）

在以下的關系數據庫中查詢至少用了供應商S1所供應的全部零件的工程號。

供應商（供應商編號，供應商姓名，供應商所在城市）

零件（零件編號，零件名稱，顏色，重量）

工程（工程編號，工程名稱，工程所在城市）

供應（供應商編號，零件編號，工程編號，數量）

上述查詢里有確定的包含關系：設該工程所使用的零件編號及其供應商編號所構成的集合為集合1（此集合的每個元素都包含了零件編號、供應商編號這兩個屬性），供應商S1所供應的零件編號及其供應商編號所構成的集合為集合2（此集合的每個元素也都包含了零件編號、供應商編號這兩個屬性，只不過供應商編號的取值均為S1），如果集合1包含了集合2，則就說明該工程至少用了供應商S1所供應的全部零件。很顯然，上述的集合1和集合2都是確定的集合，所以此查詢要用到除運算。

表達式為： 工程編號，供應商編號，零件編號（供應）€鰲」┯ι癱嗪牛慵嗪牛ā」┯ι癱嗪？‘S1（供應））

在以下的關系數據庫中查詢至少參加了項目編號為2、3、5號的雇員的信息（所有屬性）。

雇員（雇員編號，姓名，性別，年齡，部門）

項目（項目編號，名稱，經費，起始時間，終止時間）

參加（雇員編號，項目編號，相應職責）

上述查詢里有確定的包含關系：設該雇員所參加的項目的項目編號所構成的集合為集合1，2、3、5這三個項目編號所構成的集合為集合2，如果集合1包含了集合2，則就說明該雇員至少參加了項目編號為2、3、5號的這三個項目。很顯然，上述的集合1和集合2都是確定的集合，所以此查詢要用到除運算。

表達式為 雇員編號，項目編號（參加）€鰲∠钅勘嗪牛ㄏ钅勘嗪？‘2v項目編號=‘3v項目編號=‘5（項目））∞雇員

4.2 不確定的包含關系

不確定的包含關系不能使用除運算，下面舉三個實例加以說明。在以下的關系數據庫中查詢至少選修了其先修課為7號課程的學生的學號。

學生（學號，姓名，性別，年齡，院系）

課程（課程號，課程名，先修課，學分）

選修（學號，課程號，成績）

上述查詢里的包含是不確定的：假定1、2、3號課程的先修課均為7號課程。設該學生所選修的課程的課程號所構成的集合為集合1，那么集合2并不是一個確定的集合，以下的集合：{1}、{2}、{3}、{1，2}、{1，3}、{2，3}、{1，2，3}，當集合1包含上述集合時，均符合此查詢的要求。因此本查詢的包含是不確定的，不需要使用除運算。

本查詢使用三個關系的連接即可，表達式： 學號（ 先修課=‘7（學生∞選修∞課程））

在以下的關系數據庫中查詢至少參加了兩個項目的雇員的雇員編號、姓名、部門。

雇員（雇員編號，姓名，性別，年齡，部門）

項目（項目編號，名稱，經費，起始時間，終止時間）

參加（雇員編號，項目編號，相應職責）

顯然以上的查詢是不確定的包含：至少參加了兩個項目，意思是參加了兩個，或者參加了三個，或者參加了四個等等；即使就是參加了兩個，到底是哪兩個，也是不確定的。所以此查詢不能使用除運算。

此查詢需要把兩個“參加”關系“拼接”起來，但是此種“拼接”不能使用自然連接，因為自然連接會取消重復的屬性列，應該使用笛卡爾積把兩個“參加”關系拼接起來。假設“參加”關系如表1所示，則參加參加如表2所示。

在“參加”關系中，雇員編號為“5”的雇員至少參加了兩個項目（正好兩個），而雇員編號為“11”的雇員只參加了一個項目。在參加參加關系中，至少存在一個元組，第一列的雇員編號取值和第四列的雇員編號取值相等，都等于“5”；而第二列的項目編號取值和第五列的項目編號取值不相等，一個取值為“2”，另一個取值為“3”。在參加參加關系中，不存在這樣一個元組：第一列的雇員編號取值和第四列的雇員編號取值相等，都等于“11”；而第二列的項目編號取值和第五列的項目編號取值不相等。因此由上述所分析的條件使用選擇運算先求出至少參加了兩個項目的雇員的雇員編號，然后再和“雇員”關系自然連接求出姓名、部門。

此查詢的表達式為： 1（ 1=4∧2<>5（參加€撞渭櫻蕖？，2，5（雇員），表達式用序號來表示相應的屬性列。

在以下的關系數據庫中查詢至少借閱過一本類別為天文類圖書的讀者的信息（全部屬性）。

圖書（書號，書名，作者，出版社，類別，定價）

讀者（讀者編號，姓名，性別，年齡，部門）

借閱（書號，讀者編號，借閱日期，歸還日期）

上述查詢中雖然有“至少”，但同時也有數字“一”，這種類型查詢里的包含往往也是不確定的：假定天文類圖書有四本，書號分別為6、7、8、9。設該讀者所借閱的圖書的書號所構成的集合為集合1，那么集合2并不是一個確定的集合，以下的這些集合：{6}、{7}、{8}、{9}、{6，7}、{7，8}、{8，9}、{6、7，8}、{7、8，9}、{6、7、8、9}等等，當集合1包含上述集合時，均符合此查詢的要求。因此本查詢的包含是不確定的，不需要使用除運算。

這種類型的查詢直接使用自然連接，表達式如下：

讀者編號，姓名，性別，年齡，部門（ 類別=‘天文（圖書∞借閱∞讀者））

5 結束語

關系代數的查詢問題有這樣一類，其題干中含有“至少”這樣一個關鍵詞，筆者根據多年的教學經驗將這樣的一類查詢問題分為兩類：確定的包含關系和不確定的包含關系，前者需要使用關系除運算，后者不能使用關系除運算，需要考慮諸如自然連接甚至是傳統的集合運算等其它關系運算。

南通大學教學改革課題《數據庫原理及應用》 課程上機實驗教學改革及質量評價指標體系的研究與實踐（2015B55）

參考文獻

[1] 王珊，薩師煊.數據庫系統概論（第五版）[M].北京：高等教育出版社，2014.

[2] 程晨.數據庫原理課程中關系代數除運算教學的探討[J].電腦知識與技術，2014（14）：3338-3339.