天天看點

資料庫(二)—— 關系資料庫以及關系代數和關系運算五、關系資料庫的規範化理論

一、關系資料結構及形式化定義

1、關系

        關系模型的資料結構非常簡單,隻包含單一的資料結構——關系。在使用者看來,關系模型中資料的邏輯結構是一張扁平的二維表。

1.1 域

        域是一組具有相同資料類型值的集合。

1.2 笛卡兒積

        笛卡兒積是域上的一種集合運算。

        定義:給定一組域D1,D2,...,Dn,允許其中某些域是相同的,D1,D2,...,Dn的笛卡兒積為D1×D2×...Dn = {(d1,d2,...,dn)|di∈Di,i = 1,2,...,n}

        每一個元素(d1,d2,...,dn)叫做一個元組,元素中的每一個值di叫做一個分量。

        一個域允許的不同取值個數稱為這個域的基數。若Di(i = 1,2,...,n)為有限集,其基數為mi(i = 1,2,...,n)。

        笛卡兒積可表示為一張二維表,表中的每行對應一個元組,表中每一列的值來自一個域。

1.3 關系

        定義:D1×D2×...×Dn的子集叫做在域D1,D2,...,Dn上的關系,表示為R(D1,D2,...,Dn)。這裡R表示關系的名字,n是關系的目或度,關系中的每個元素是關系中的元組,通常用t表示。當n=1時,稱該關系為單元關系或一進制關系;當n=2時,稱該關系為二進制關系。

        關系是笛卡兒積的有限子集,是以關系也是一張二維表,表的每行對應一個元組,表的每列對應一個域。由于域可以相同,為了加以區分,必須對每列起一個名字,稱為屬性。n目關系必有n個屬性。

        若關系中的某一屬性組的值能唯一的辨別一個元組,而其子集不能,則稱該屬性組為候選碼。若一個關系中有多個候選碼,則標明其中一個為主碼(primary key)。候選碼的諸屬性稱為主屬性。不包含在候選碼中的屬性稱為非主屬性或非碼屬性。簡單的情況下,候選碼隻包含一個屬性。最壞情況下,關系模式的所有屬性是這個關系模式的候選碼,稱為全碼。

        一般來說,笛卡兒積是沒有實際語義的,隻有它的真子集才有實際含義。

⑴ 關系的三種類型

基本關系(基本表):是實際存在的表,是實際存儲的邏輯表示;

查詢表:查詢結果對應的表;

視圖表:是由基本一或其他視圖表導出的表,是虛表,不對應實際存儲的資料。

⑵ 關系的限定和擴充

① 無限關系在資料庫系統中是無意義的,限定關系資料模型中的關系必須是有限集合;

② 通過為關系的每個列附加一個屬性名的方法取消關系屬性的有序性。

⑶ 基本關系具備的性質

① 列是同質的,每一列中的分量是同一類型的資料,來自同一個域;

② 不同的列可出自同一個域,稱其中的每一個列為一個屬性,不同的屬性要給予不同的屬性名;

③ 列的次序可以任意交換;

④ 任意兩個元組的候選碼不能取相同的值;

⑤ 行的次序可以任意交換;

⑥ 分量必須取原子值,每一個分量都必須是不可再分的資料項。

關系模型要求關系必須是規範化的,即要求關系必須滿足一定的規範條件。規範化的關系稱為範式。

2、關系模式

        定義:關系的描述稱為關系模式,它可以表示為R(U,D,DOM,F)。R是關系名,U為組成該關系的屬性名集合,D為U中屬性所來自的域,DOM為屬性向域的映像集合(說明它們出自哪個域,常常直接說明為屬性的類型和長度),F為屬性間資料的依賴關系集合。

        關系是關系模式在某一時刻的狀态或内容,關系模式是靜态的、穩定的,而關系是動态的、随時間不斷變化的,因為關系操作在不斷的更新着資料庫中的資料。

3、關系資料庫

        所有關系的集合構成一個關系資料庫。

        關系資料庫也有型和值之分。關系資料庫的型稱為關系資料庫模式,是對關系資料庫的描述。關系資料庫的值是這些關系模式在某些時刻對應的關系的集合,通常稱作關系資料庫。

4、關系模型的存儲結構

        表是關系資料的邏輯模型。

        在關系資料庫的實體組織中,有的一個表對應一個作業系統檔案,将實體資料組織交給作業系統來完成;有的從作業系統那裡申請若幹個大的檔案,自己劃分檔案空間,組織表、索引等存儲結構,并進行存儲管理。

二、關系操作

1、基本的關系操作

        關系模型中常用的關系操作包括查詢(query)操作和插入(insert)、删除(delete)、修改(update)操作兩大部分。

        查詢操作又可以分為選擇(select)、投影(project)、連接配接(join)、除(divide)、并(union)、差(except)、交(intersection)、笛卡兒積等。其中選擇、投影、并、差、笛卡兒積是5種基本操作,其他操作可以用基本操作來定義和導出。

2、關系資料語言的分類

        關系資料語言可以分為三類:關系代數語言(如ISBL),關系演算語言,具有關系代數和關系演算雙重特點的語言(如SQL)。

2.1 關系代數語言

        關系代數用對關系的運算來表達查詢要求。

2.2 關系演算語言

        關系演算用謂詞來表達查詢要求。它可按謂詞變元的基本對象是元組變量還是域變量分為元組關系演算和域關系演算。

        一個關系資料語言能夠表示關系代數可以表示的查詢,稱為具有完備的表達能力,簡稱關系完備性。已經證明關系代數、元組關系演算和域關系演算三種語言在表達能力上是等價的,都具有完備的表達能力。

2.3 結構化查詢語言

        它是一種具有關系代數和關系演算雙重特點的語言,是集查詢、資料定義語言、資料操縱語言和資料控制語言于一體的關系資料語言。

三、關系的完整性

        關系模型中有三類完整性限制:實體完整性、參照完整性和使用者定義的完整性,其中實體完整性和參照完整性是關系資料模型必須滿足的完整性限制條件,被稱作是關系的兩個不變性,應該由關系系統自動支援。

1、實體完整性

1.1 實體完整性規則

        若屬性(一個或一組屬性)A是基本關系R的主屬性,則A不能取空值。

1.2 實體完整性規則說明

⑴ 一個基本表通常對應現實世界的一個實體集;

⑵ 實體在現實世界中是可區分的,它們具有某種唯一性的辨別,關系模型中以主碼作為唯一性辨別;

⑶ 主碼中的屬性即主屬性不能取空值。

2、參照完整性

2.1 參照完整性規則

        若屬性(一個或一組屬性)F是基本關系R的外碼,它與基本關系S的主碼相對應(R和S有可能是相同的關系),則對于R中每個元組在F上的值必須:或者取空值,或者等于S中某個元組的主碼值。

        參照完整性規則就是定義外碼和主碼之間的引用規則。

2.2 參照完整性規則說明

⑴ 不僅兩個或兩個以上的關系間存在引用關系,同一關系内部屬性間也可能存在引用關系(如學生(學員,...,班長));

⑵ 如果F是關系R的一個或一組屬性,但不是關系R的主碼,K是基本關系S的主碼。如果F與K相對應,則稱F是R的外碼,并稱基本關系R為參照關系,基本關系S為被參照關系。關系R和S有可能是相同的關系。

⑶ 外碼并不一定發與相對應的主碼同名,但實際應用中為了友善識别,一般使用同名;

⑷ 當參照完整性限制和實體完整性限制無法同時滿足時,優先滿足實體完整性限制,如成績關系中學号和課程号分别參照學生關系和課程關系中的主碼,此時由于學号和課程号是成績關系中的主屬性,則它們不能取空值,隻能取被參照關系中已經存在的主碼值。

3、使用者定義的完整性

        使用者定義的完整性限制就是針對某一具體關系資料庫的限制條件,它反映某一具體應用所涉及的資料必須滿足的語義要求,如某個屬性必須取唯一值、某個非主屬性不能取空值。

四、關系代數

        關系代數是一門抽象的查詢語言,它用對關系的運算來表達查詢。

        運算對象、運算符、運算結果是運算的三大要素。關系代數的運算對象是關系,運算結果也是關系,運算符包括:集合運算符和關系運算符。

資料庫(二)—— 關系資料庫以及關系代數和關系運算五、關系資料庫的規範化理論

1、傳統的集合運算

傳統的集合運算是二目運算,包括并、交、差、笛卡兒積四種運算。以下以oracle為例:

1.1 并(union)

R∪S

其結果仍為n目關系,由屬于R或屬于S的元組組成。

--結果:2條記錄
select * from emp where empno=7369
union
select * from emp where empno=7788
           
--結果:11條記錄
select * from emp where sal < 2000 --隻有2個20号部門的人,一共8條記錄
union 
select * from emp where deptno = 20 --20号部門共有5個人,一共5條記錄
           

1.2 差(except)

R-S

其結果關系仍為n目關系,由屬于R而不屬于S的所有元組組成。

--結果:1條記錄
select * from emp where deptno=30 --30号部門共有6個人,一共6條記錄
minus 
select * from emp where deptno=30 and mgr=7698 --部門經理為7698的員工有5個,一共5條記錄
           

1.3 交(intersection)

R∩S

其結果仍為n目關系,由既屬性R又屬于S的元組組成。交可以用差來表示,即R∩S=R-(R-S)。

--結果:5個
select * from emp where deptno=30 --6個
intersect
select * from emp where deptno=30 and mgr=7698 --5個
           

1.4 笛卡兒積

        關系R和S的笛卡兒積是一個(n+m)列的元組的集合,元組的前n列是關系R的一個元組,後m列是關系S的一個元組。若R有x個元組,S有y個元組,則關系R和S的笛卡兒積有x*y個元組。

--笛卡兒積(若關系R有n列x行,關系S有m列y行,則R和S的笛卡兒積為列n+m,行x*y)
select a.*,b.* from emp a,dept b --第一種
select * from emp cross join dept --第二種
           

2、專門的關系運算

        專門的關系運算包括選擇、投影、連接配接、除運算等。以下以oracle為例:

2.1 選擇(selection)

        選擇的邏輯表達式的基本形式為:XθY。其中θ代表比較運算符,它可以是比較運算符。X、Y是屬性名或常量或簡單函數。它是從行的角度進行的運算。

select * from emp where sal > 3000
           

2.2 投影(projection)

        關系R上的投影是從關系R中選出若幹屬性列組成新的關系。它是從列的角度進行的運算。由于投影取消了某些列之後可能出現重複的行,應取消這些完全相同的行。

select distinct deptno from emp
           

2.3 連接配接(join)

也稱θ連接配接,它是從兩個關系的笛卡兒積中選取屬性間滿足一定條件的元組。

--向dept中添加列(平均工資)設定10、20、30号部門的平均工資并送出
alter table dept add (avgsal number(10))
update dept set avgsal=3000 where deptno = 10;
update dept set avgsal=2000 where deptno = 20;
update dept set avgsal=1500 where deptno = 30;
commit;
--向emp中添加一條沒有部門的員工資訊記錄并送出
insert into emp(empno,ename,job,mgr,hiredate,sal,comm,deptno) values(8888,'ZHANG','ENGINEER',7788,sysdate,3000,2000,null);
commit;
           

⑴ 非等值連接配接

θ不為“=”的連接配接稱為非等值連接配接

select * from emp e join dept d on e.sal > d.avgsal
           

⑵ 等值連接配接

        θ為“=”的連接配接稱為等值連接配接,它是從關系R和S的笛卡兒積中選取A、B屬性值相等的那些元組。等值連接配接的屬性名可以相同也可以不相同。

select * from emp e join dept d on e.sal = d.avgsal
select * from emp e join dept d on e.deptno = d.deptno
           

⑶ 自然連接配接

        自然連接配接是一種特殊的等值連接配接,它要求兩個關系進行比較的分量必須是同名的屬性組,并且在結果中把重複的屬性列去掉。一般的連接配接是從行的角度進行操作,自然連接配接需要取消重複列,是以它是從行和列的角度進行操作。

select * from emp natural join dept
           

⑷ 外連接配接

        兩個關系R和S在做自然連接配接時,選擇兩個關系在公共屬性上值相等的元組構成新的關系。此時,關系R和S可能有在公共屬性上不相等的元組,進而造成R或S中元組的舍棄,這些舍棄的元組被稱為懸浮元組。如果把懸浮元組也儲存在結果關系中,而在其他屬性上填空值,那麼這種連接配接就叫做外連接配接。

① 左外連接配接

如果隻保留左邊關系R中的懸浮元組就叫做左外連接配接。

select * from emp e left join dept d on e.deptno = d.deptno --員工8888沒有部門,隻保留左表的懸浮元組,其他屬性為null
           

② 右外連接配接

如果隻保留右邊關系S中的懸浮元組就叫做右外連接配接。

select * from emp e right join dept d on e.deptno = d.deptno --40号部門沒有人,隻保留右表的懸浮元組,其他屬性為null
           

③ 全外連接配接

如果保留兩邊關系R和S中的所有懸浮無級就叫做全外連接配接。

select * from emp e full join dept d on e.deptno = d.deptno --保留兩邊的懸浮元組,左表和右表各有一條懸浮元組記錄,一共16行
           

⑸ 自連接配接

select * from emp e1 join emp e2 on e1.empno = e2.mgr
           

2.4 除運算(division)

        設關系R除以關系S的結果為關系T,則關系T包含所有在R但不在S中的屬性及其值,且T的元組與S的元組的所有組合都在R中。

⑴ 象集

給定一個關系R(X,Z),X和Z為屬性組。它表示R中屬性組X上值為x的若幹元組在Z上分量的集合。

例:關系R

x1 y1
x1 y2
x1 y3
x2 y3
x2 y1

x1在R中的象集Z1={y1,y2,y3}

x2在R中的象集Z2={y3,y1}

⑵ 用象集來定義除法

① 給定關系R(X,Y)和S(Y,Z),其中X、Y、Z為屬性組,R中的Y與S中的Y可以有不同的屬性名,但必須出自相同的域集;

② 元組在X上的分量值x的象集K要包含S在Y上投影的集合,滿足前面條件的元組在X屬性上的投影就是R除以S的結果關系;

③ 除操作是同時從行和列角度進行的操作。

例:

關系R

X Y
x1 y1
x1 y2
x1 y3
x2 y3
x2 y5

關系S

Y Z
y1 z1
y3 z2

R÷S=P,P如下:

X
x1

分析:

① S在(Y)上的投影的集合是:{(y1),(y3)};

② 元組在X上的分量值x的象集有兩組;

x1的象集K1={(y1),(y2),(y3)}

x2的象集K2={(y3),(y5)}

③ 從①②得知隻有象集K1包含了S在(Y)上的投影;

④ 滿足以上條件的象集K1在X屬性上的投影為{(x1)}。

小結:

        在關系代數運算中,并、差、笛卡兒積、選擇和投影這5種運算為基本的運算,其他三種運算交、連接配接、除,均可使用這5種基本運算來表達。它些運算經過有限次複合後形成的表達式稱為關系代數表達式。

五、關系資料庫的規範化理論

1、關系模式中可能存在的備援和異常問題

① 資料備援

        資料備援是指同一資料反複被存取的情況。

② 更新異常

        資料備援将導緻存儲空間的浪費和潛在資料不一緻性以及修改麻煩等問題。

③ 插入異常

        資料的插入操作異常是指應該插入到資料庫中的資料不能執行插入操作的情形。

④ 删除異常

        資料的删除操作異常是指不應該被删除的資料被删去的情形。

小結:

        關系模式産生上述問題的原因,以及消除這些問題的方法,都與資料依賴的概念密切相關。資料依賴是可以作為關系模式的取值的任何一種關系所必須滿足的一種限制條件,是通過一個關系中各個元組的某些屬性之間的相等與否展現出來的互相關系。這是現實世界屬性間互相聯系的抽象,是資料内在的性質,是語義的展現。

        資料依賴,其中最重要的是函數依賴和多值依賴。

2、函數依賴與關鍵字

函數依賴是指關系中屬性間的對應關系。

定義一:

        設R為任一給定關系,如果對于R中屬性X的每一個值,R中的屬性Y隻有唯一值與之對應,則稱X函數決定Y或稱Y函數依賴于X,記作X → Y,其中X稱為決定因素。反之,對于關系R中的屬性X和Y,若X不能函數決定Y,則其符号記作X →× Y。

例:SNO → SNAME     SNAME →× SNO(人名可能有同名同姓的,不能決定學号)

注意:函數依賴是針對關系的所有元組,即某個關系中隻要有一個元組的有關屬性值不滿足函數依賴的定義,則相對應的函數依賴就不成立。

函數依賴根據其不同性質可分為完全函數依賴、部分函數依賴和傳遞函數依賴。

① 完全函數依賴

定義二:

        設R為任一給定關系,X、Y為其屬性集,若X → Y,且任何X中的真子集X1都有X1 →× Y,則稱Y完全函數依賴于X。

例:(SNO,CNO)→ GRADE(學号和課程編号決定成績)

② 部分函數依賴

定義三:

        設R為任一給定關系,X、Y為其屬性集,若X → Y,且X中存在一個真子集X1滿足X1 → Y,則稱Y部分函數依賴于X。

例:(SNO,SNAME)→ SSEX,但其中SNO → SSEX(學号和姓名可以決定性别,但其中學号可以直接決定性别)

③ 傳遞函數依賴

定義四:

        設R為任一給定關系,X、Y、Z為其不同的屬性子集,若X → Y,Y →× X,Y → Z ,則有X → Z,稱為Z傳遞函數依賴于X。(加入條件Y →× X,是因為若Y → X,即有X ←→ Y,這實際上是X直接函數決定Z,而不是X傳遞函數決定Z)

例:BNO → PNAME (書号決定出版社)和 PNAME → PADDRESS(出版社決定出版社位址),但PNAME →× BNO(一個出版社可能出版多種書),是以有PADDRESS對BNO的傳遞函數依賴。

定義五:

        設R為任一給定關系,U為其所含的全部屬性集合,X為U的子集,若有完全函數依賴X → U,則X為R的一個候選關鍵字。作為候選關鍵字的屬性集X唯一辨別R中的元組,但該屬性集的任何真子集不能唯一辨別R中的元組。顯然,一個關系R中可能存在多個候選關鍵字,通常選擇其中之一作為主鍵,候選關鍵字中所含的屬性稱為主屬性。

例:屬性集(SNO,CNO)為候選關鍵字,SNO和CNO為主屬性

3、範式與關系規範化的過程

        關系資料庫中的關系需要滿足一定的要求,不同程度的要求稱為不同的範式。滿足最低要求的稱為第一範式,簡稱1NF,這是最基本的範式;在第一範式的基礎上進一步滿足一些新的要求稱為第二範式(2NF);以此類推,再進一步的範式是第三範式(3NF)及其改進形式BCNF。

        一個低一級範式的關系模式通過模式分解,可以轉換為若幹個高一級範式的關系模式的集合,這種過程叫做規範化。

⑴ 第一範式

定義:設R為任一給定關系,如果R中每個列與行的交點處的取值都是不可再分的基本元素,則R為第一範式。

        由此可見,第一範式是一個不含重複組的關系,其中不存在嵌套結構,不滿足第一範式的關系為非規範關系。下面是一個非規範關系,因為在學号為80154的學生資料中出現了重複組。

不滿足1NF的非規範關系SC

SNO CNO CTITLE INAME IPLACE GRADE
80152 C01 作業系統 五忠 東01 70
80153 C02 資料庫 高國 東02 85
80154 C01 作業系統 五忠 東01 86
C03 人工智能 楊凡 東03 72
80155 C04 C語言 高國 東02 92

        非規範關系轉化為1NF比較容易,可以通過重寫關系中屬性值相同部分的資料來實作,轉化後如下:

滿足1NF的關系SC

SNO CNO CTITLE INAME IPLACE GRADE
80152 C01 作業系統 五忠 東01 70
80153 C02 資料庫 高國 東02 85
80154 C01 作業系統 五忠 東01 86
80154 C03 人工智能 楊凡 東03 72
80155 C04 C語言 高國 東02 92

        然而,上面表中所示的關系存在着備援高、插入和删除操作異常等問題。比如,若作業系統這門課程被1000個同學選修,那麼該授課老師的辦公位址就要被存儲1000次,這就帶來了大量的資料“備援”;如果學校開設了一門新課程,但尚未有學生選修,則這個課程的資訊就無法存儲到關系中,此時就出現了“插入異常”的現象;如果删除上面關系中的最後一條記錄,則同時也會删除和C語言相關的授課老師的資訊,此時會面臨“删除異常的問題”。是以,在滿足1NF的基礎,需要對其進一步進行規範化。

        經分析,SC關系出現備援高、插入異常、删除異常的問題原因在于:非主屬性GRADE完全函數依賴于(SNO,CNO),其他非主屬性(CTITLE,INAME,IPLACE)都是函數依賴于CNO,即它們與(SNO,CNO)為部分函數依賴關系。那麼,解決1NF關系存在問題的方法是:将滿足部分函數依賴關系和滿足完全函數依賴關系的屬性分解并組成兩個關系,進而消除非主屬性對候選關鍵字的部分函數依賴,由此獲得更高一級的範式。按照此方法關系SC可分解為關系SG和關系CI,如下所示:

滿足2NF的關系SG

SNO CNO GRADE
80152 C01 70
80153 C02 85
80154 C01 86
80154 C03 72
80155 C04 92

滿足2NF的關系CI

CNO CTITLE INAME IPLACE
C01 作業系統 五忠 東01
C02 資料庫 高國 東02
C03 人工智能 楊凡 東03
C04 C語言 高國 東02

⑵ 第二範式

定義:設R為任一給定關系,若R為1NF,且所有非主屬性都完全函數依賴于候選關鍵字,則R為第二範式。

        然而,2NF并不能解決所有問題,在關系CI中,如果有一位新老師報到,需将其有關資料插入到CI中去,但該老師暫時還未承擔任何教學工作,則因缺失關鍵字CNO的值而不能進行插入操作。

        經分析,産生上述現象的原因在于:關系CI中存在非主屬性對主屬性的傳遞函數依賴,即CNO → INAME、INAME →× CNO、INAME → IPLACE。是以,需要将2NF的關系CI進行一步進行規範化,消除非主屬性對候選關鍵字的傳遞函數依賴。

滿足3NF的關系COURSE

CNO CTITLE INAME
C01 作業系統 五忠
C02 資料庫 高國
C03 人工智能 楊凡
C04 C語言 高國

滿足3NF的關系INSTRUCTOR

INAME IPLACE
五忠 東01
高國 東02
楊凡 東03

⑶ 第三範式

定義:設R為任一給定關系,若R為2NF,且其每一個非主屬性都不傳遞函數依賴于候選關鍵字,則R為第三範式。

        通常,第三範式的關系大多數都能解決插入和删除操作異常的問題,資料備援也能得到有效的控制,但也存在一些例外。例如如下關系中,若每一個學生可選修多門課程,每一門課程可有多個指導老師,但每個老師隻能指導一門課程,則其候選關鍵字為(SNO,CTITLE)和(SNO,TNAME),故不存在非主屬性,也就不存在非主屬性對主屬性的傳遞函數依賴。是以,該關系是一個3NF,但其中仍存在插入和删除操作異常問題。例如,一個新課程和指導老師的資料要插入到資料庫中,必須至少有一個學生選修該課程且該指導老師已被配置設定給他時才能進行。

3NF關系SCT

SNO CTITLE TNAME
S01 英語 王華
S01 數學 沈飛
S02 實體 高俊
S03 英語 袁曉
S04 英語 王華

        經分析,上述問題的原因在于:主屬性之間存在函數依賴TNAME → CTITLE,這裡需要對其進一步進行規範化,其結果如下:

BCNF關系ST

SNO TNAME
S01 王華
S01 沈飛
S02 高俊
S03 袁曉
S04 王華

BCNF關系TC

TNAME CTITLE
王華 英語
沈飛 數學
高俊 實體
袁曉 英語

⑷ BCNF

定義:設R為任一給定關系,X、Y為其屬性集,F為其函數依賴集,若R為3NF,且其F中所有函數依賴X → Y(Y不屬于X)中的X必包含候選關鍵字,則R為BCNF

        簡而言之,若R中每一個函數依賴的決定因素都包含一個候選關鍵字,則R為BCNF,其中,決定因素可以是單一屬性或組合屬性。

        根據BCNF的定義可知,在關系SCT中,有函數依賴TNAME → CTITLE,但TNAME不是候選關鍵字。