數據庫關系運算

數據庫關系運算2023/2/12第一頁，共七十一頁，2022年，8月28日第二章:關系模型關系數據庫結構基本關系代數運算附加關系代數運算擴展關系代數運算空（Null）值數據庫更改2023/2/12第二頁，共七十一頁，2022年，8月28日關系例子2023/2/12第三頁，共七十一頁，2022年，8月28日基本結構假設集合A={a,b}，集合B={0,1,2}，則兩個集合的笛卡爾積為{(a,0),(a,1),(a,2),(b,0),(b,1),(b,2)}?？梢詳U展到多個集合的情況。類似的例子有，如果A表示某學校學生的集合，B表示該學校所有課程的集合，則A與B的笛卡爾積表示所有可能的選課情況。給定一組域D1，D2，…，Dn，這些域中可以有相同的。D1，D2，…，Dn的笛卡爾積為：

D1×D2×…×Dn＝｛（d1，d2，…，dn）｜diDi，i＝1，2，…，n所有域的所有取值的一個組合不能重復。一般地,給定集合D1,D2,….Dn，

關系r

是

D1xD2x…xDn

的子集。所以，關系是n-元組

(a1,a2,…,an)集合，且ai

Di2023/2/12第四頁，共七十一頁，2022年，8月28日基本結構例子:Ifcustomer_name={Jones,Smith,Curry,Lindsay,…} /*Setofallcustomernames*/customer_street={Main,North,Park,…}/*setofallstreetnames*/customer_city={Harrison,Rye,Pittsfield,…}/*setofallcitynames*/Thenr={(Jones,Main,Harrison),

(Smith,North,Rye),

(Curry,North,Rye),

(Lindsay,Park,Pittsfield)}

isarelationover customer_namexcustomer_streetxcustomer_city2023/2/12第五頁，共七十一頁，2022年，8月28日屬性類型關系的每個屬性有一個名字每個屬性允許的取值的集合叫做屬性的域屬性值（通常）要求是原子的，即，不可分的“基本項”例如：屬性值可以是一個賬號，但不能是賬號的集合如果所有域成員是原子的，則說域是原子的特殊值null

是每個可能域的成員null值造成定義很多運算的復雜性在本章主要的講解中，我們將暫時忽略null的影響2023/2/12第六頁，共七十一頁，2022年，8月28日關系模式A1,A2,…,An

是屬性R=(A1,A2,…,An)是關系模式 例子:

Customer_schema=(customer_name,customer_street,customer_city)r(R)表示關系模式R上的關系

r

例子:

customer(Customer_schema)2023/2/12第七頁，共七十一頁，2022年，8月28日關系實例關系當前值（關系實例）由一個表確定r

的一個成員是元組（tuple）,表示為表中一行關系術語/文件術語：屬性/項，元組/記錄，表/文件JonesSmithCurryLindsaycustomer_nameMainNorthNorthParkcustomer_streetHarrisonRyeRyePittsfieldcustomer_citycustomer屬性(或列)元組(或行)2023/2/12第八頁，共七十一頁，2022年，8月28日關系是無序的元組的順序無關(元組存儲順序可以是任意的)

例子:帳戶關系中的無序元組2023/2/12第九頁，共七十一頁，2022年，8月28日數據庫數據庫由多個關系組成企業(yè)信息被劃分成部分，每個關系存儲一部分信息

account:存儲帳戶信息

depositor（存款人）:存儲關于哪個客戶擁有哪個帳戶的信息

customer:存儲客戶的信息把所有信息存儲在單個關系中，如

bank(account_number,balance,customer_name,..)

導致信息重復如，如果一個客戶擁有兩個帳戶（哪個信息重復了？）需要null值如，一個沒有存儲賬戶的客戶（也許有貸款，所以是客戶）規(guī)范化理論負責處理如何設計關系模式2023/2/12第十頁，共七十一頁，2022年，8月28日customer關系2023/2/12第十一頁，共七十一頁，2022年，8月28日depositor關系2023/2/12第十二頁，共七十一頁，2022年，8月28日account關系2023/2/12第十三頁，共七十一頁，2022年，8月28日branch關系2023/2/12第十四頁，共七十一頁，2022年，8月28日loan關系2023/2/12第十五頁，共七十一頁，2022年，8月28日borrower

關系2023/2/12第十六頁，共七十一頁，2022年，8月28日碼/鍵（key)使KR（K：一個或多個屬性集合）如果K值足以唯一地標識每個可能關系r(R)

的一個元組，則K是R的一個超碼（superkey）“可能關系r”意思是：能夠存在于我們要建模的企業(yè)的關系r例子:{customer_name,customer_street}and

{customer_name}

都是Customer的超碼（如果沒有重名客戶）實際中，諸如屬性customer_id

將用來代替customer_name去唯一地標示customers,這里為了保持例子屬性少，假定客戶名字不重復。2023/2/12第十七頁，共七十一頁，2022年，8月28日碼(Cont.)如果K

是最小超碼，則K是候選碼（candidatekey）

例子:{customer_name}是Customer的一個Customer，因為它是一個超碼而且沒有其超碼子集主碼（Primarykey）:被選為首要標識關系中元組的候選碼應該選其值不變或幾乎不變的屬性消例如：email地址是唯一的，但可能變化2023/2/12第十八頁，共七十一頁，2022年，8月28日外碼一個關系模式可以具有一個是其他關系主碼的屬性。該屬性稱為外碼（foreignkey）。如：depositor的customer_name

和account_number

屬性分別是到customer

和account

的外碼。只有被參照關系（referencedrelation

）的主碼產生值，參照關系（

referencingrelation）的外碼才可能產生值模式圖（SchemaDiagram）2023/2/12第十九頁，共七十一頁，2022年，8月28日查詢語言用戶從數據庫請求信息的語言語言分類過程的（Procedural）非過程的（Non-procedural）,或聲明式的（declarative）“純”語言:關系代數（Relationalalgebra）元組關系演算（Tuplerelationalcalculus）域關系演算（Domainrelationalcalculus）純語言為人們使用的查詢語言構成了支撐基礎2023/2/12第二十頁，共七十一頁，2022年，8月28日關系代數過程語言6個基本運算符號選擇（select）:投影（project）:并（union）:集合差（setdifference）:–

笛卡爾積（Cartesianproduct）:x更名（rename）:這些運算符以一個或兩個關系為輸入，輸出一個新的關系作為結果一元運算：選擇、投影、更名二元運算：并、集合差、笛卡爾積2023/2/12第二十一頁，共七十一頁，2022年，8月28日選擇運算–例子RelationrABCDA=B^D>5

(r)ABCD1237102023/2/12第二十二頁，共七十一頁，2022年，8月28日選擇運算符號:

p(r)p

稱為謂詞（

predicate）定義為:

p(r)={t|tr

andp(t)}

這里

p

是命題演算（propositionalcalculus）中的一個規(guī)則，由項（terms）

構成，這些項由:(and),(or),(not)連接。 每個項是以下之一: <屬性>op <屬性>or<常數>

這里op

是:=,,>,.<.例子:

A=B^D>5

(r)

branch_name=“Perryridge”(account)2023/2/12第二十三頁，共七十一頁，2022年，8月28日投影運算–例子Relationr:ABC102030401112AC1112=AC112A,C(r)2023/2/12第二十四頁，共七十一頁，2022年，8月28日投影運算符號:

這里A1,A2

是屬性名，r

是關系名。其結果定義為通過消去未列出的列而得到的具有k

列的關系。重復行被去掉（因為關系是集合）例子:去掉account的branch_name

屬性

account_number,balance(account)

2023/2/12第二十五頁，共七十一頁，2022年，8月28日并運算–例子Relationsr,s:rs:AB121AB23rsAB12132023/2/12第二十六頁，共七十一頁，2022年，8月28日并運算符號:r

s定義為:

r

s={t|trorts}為使r

s

有效

1.r,

s

同元

(屬性數目相同) 2.對所有i,r的第i個屬性和s的第i個屬性的域必須兼容（compatible

）例子:找出所有或者有帳戶或者有貸款或者二者兼有的客戶

customer_name(depositor)customer_name(borrower)2023/2/12第二十七頁，共七十一頁，2022年，8月28日集合差運算–例子Relationsr,s:r–s:AB121AB23rsAB112023/2/12第二十八頁，共七十一頁，2022年，8月28日集合差運算符號：r–s定義為:

r–s={t|t

r

andts}集合差運算必須保證是在兼容關系間進行

r,

s

同元

(屬性數目相同)對所有i,r的第i個屬性和s的第i個屬性的域必須兼容（compatible

）2023/2/12第二十九頁，共七十一頁，2022年，8月28日笛卡爾積運算–例子Relationsr,s:rx

s:AB12AB11112222CD1010201010102010EaabbaabbCD10102010Eaabbrs2023/2/12第三十頁，共七十一頁，2022年，8月28日笛卡爾積運算符號：

rxs定義為:

rxs={tq|trandqs}

假設r(R)和s(S)的屬性不相交(即，RS=)。如果r(R)

和s(S)的屬性相交,則必須使用更名。2023/2/12第三十一頁，共七十一頁，2022年，8月28日組合運算能夠使用多個運算符建立表達式例如:A=C(rxs)rxsA=C(rxs)AB11112222CD

1010201010102010EaabbaabbABCDE122101020aab2023/2/12第三十二頁，共七十一頁，2022年，8月28日更名運算允許我們通過命名來引用（referto）關系代數表達式結果。允許我們通過多個名字引用一個關系。例子:

x(E)

返回表達式E，并賦予名字X如果一個關系代數表達式E有n元,則

返回表達式E，并賦予名字X，同時將屬性更名為

A1,A2,….,An.2023/2/12第三十三頁，共七十一頁，2022年，8月28日銀行例子branch(branch_name,branch_city,assets)

customer(customer_name,customer_street,customer_city)account(account_number,branch_name,balance)loan(loan_number,branch_name,amount)depositor(customer_name,account_number)borrower

(customer_name,loan_number)2023/2/12第三十四頁，共七十一頁，2022年，8月28日查詢例子找到貸款金額大于$1200的所有元組

找到金額大于$1200的所有貸款的貸款號碼

amount

>1200(loan)loan_number(amount

>1200(loan))找到有貸款或賬戶或二者的所有客戶的名字customer_name(borrower)customer_name(depositor)2023/2/12第三十五頁，共七十一頁，2022年，8月28日查詢例子（cont.）找到在Perryridge支行有貸款的所有客戶的名字找到在Perryridge支行有貸款但在任何分行沒有賬戶的所有客戶的名字customer_name(branch_name=“Perryridge”(borrower.loan_number=loan.loan_number(borrowerxloan)))–

customer_name(depositor)customer_name(branch_name=“Perryridge”(borrower.loan_number=loan.loan_number(borrowerxloan)))2023/2/12第三十六頁，共七十一頁，2022年，8月28日查詢例子（cont.）找到在Perryridge支行有貸款的所有客戶的名字

Query2

customer_name(loan.loan_number=borrower.loan_number(

branch_name=“Perryridge”(loanxborrower)))Query1

customer_name(branch_name=“Perryridge”

(

borrower.loan_number=loan.loan_number(borrowerxloan)))2023/2/12第三十七頁，共七十一頁，2022年，8月28日查詢例子（cont.）找到最大的賬戶余額思路:找到不是最大的余額更名account關系為d，使得我們能夠將每個賬戶余額和另一關系d中每個賬戶余額作比較（基本關系運算中只有同元組的屬性間可以比較，見前面“選擇”運算）

使用集合差來找到前面沒有找到的賬戶余額查詢如下:balance(account)-account.balance(account.balance<d.balance

(account

x

rd

(account)))2023/2/12第三十八頁，共七十一頁，2022年，8月28日關系代數的形式化定義關系代數基本表達式由以下之一組成:數據庫中的一個關系一個常數關系，如{（A-101，Downtown，500）（A-215，Mianus，700）}設E1

和E2

是關系代數表達式，下面都是關系代數表達式:E1

E2E1

–

E2E1xE2p(E1),P

是E1的屬性上的謂詞s(E1),S

是E1中某些屬性的列表

x

(E1),x是E1的結果的新名字2023/2/12第三十九頁，共七十一頁，2022年，8月28日附加運算附加運算不增加關系代數的能力，但可以簡化常用查詢。交集（Setintersection）自然連接（Naturaljoin）除（Division）賦值（Assignment）2023/2/12第四十頁，共七十一頁，2022年，8月28日交集運算符號:r

s定義: r

s={t|t

r

and

t

s}假設:r,s

同元r

和s

的屬性的域相容注意:r

s=r–(r–s)2023/2/12第四十一頁，共七十一頁，2022年，8月28日交集運算–例子Relationr,s:r

sAB121AB23rsAB22023/2/12第四十二頁，共七十一頁，2022年，8月28日

符號:rs自然連接運算設r

和s

分別是模式R

和S

上的關系

則,rs是模式R

S

上的關系，該模式如下得到:考慮每個來自r的元組tr和來自s的元組ts組成的元組對（笛卡爾積）

如果tr和ts在R

S的所有屬性上有相同值，增加一個元組t

到結果集中,這里（選擇，投影）t

具有和r

上的tr一樣的值t具有和s上的ts一樣的值例如:R=(A,B,C,D)S=(E,B,D)結果模式=(A,B,C,D,E)r

s

定義為:

r.A,r.B,r.C,r.D,s.E(r.B=s.Br.D=s.D(rxs))2023/2/12第四十三頁，共七十一頁，2022年，8月28日自然連接運算–例子Relationsr,s:AB12412CDaababB13123DaaabbErAB11112CDaaaabEsrs2023/2/12第四十四頁，共七十一頁，2022年，8月28日除運算符號:適合包含短語“對所有”的查詢設r

和s

分別是模式R

和S

上的關系 這里S

RR=(A1,…,Am,B1,…,Bn)S=(B1,…,Bn)rs的結果是一個在模式R–S=(A1,…,Am)上的關系

rs={t|tR-S(r)us(tur)}這里tu

指連接元組t

和u

產生的單一元組。

rs

2023/2/12第四十五頁，共七十一頁，2022年，8月28日除運算–例子1Relationsr,s:r

s:BA12AB12311134612rs

rs={t|tR-S(r)us(tur)}2023/2/12第四十六頁，共七十一頁，2022年，8月28日除運算–例子2ABaaaaaaaaCDaabababbE11113111Relationsr,s:r

s:DabE11ABaaCrs2023/2/12第四十七頁，共七十一頁，2022年，8月28日除運算(cont.)性質設q=r

s則q

是滿足qxs

r的最大關系使用基本關系代數定義*

設r(R)

和s(S)

是關系,并設S

R

rs=R-S(r)–R-S((R-S

(r)xs)–R-S,S(r))

分析：R-S,S(r)是r屬性簡單重新排列

R-S((R-S

(r)xs)–R-S,S(r))給出R-S

(r)

中元組t，這里對元組

us,tur2023/2/12第四十八頁，共七十一頁，2022年，8月28日賦值運算賦值運算()提供了一條表達復雜查詢的方便之路將查詢寫為序列語句：一系列賦值，緊跟一個表達式，其值為查詢結果賦值必須指向臨時關系變量例子:寫rs

為

temp1

R-S(r)

temp2

R-S((temp1xs)–R-S,S(r))

result=temp1–temp2將右邊的表達式的結果賦值給左邊的關系變量該關系變量可以在以后表達式中使用2023/2/12第四十九頁，共七十一頁，2022年，8月28日查詢例子找到既有貸款又有賬戶的所有客戶的名字customer_name(borrower)customer_name(depositor)找到所有在銀行有貸款的客戶的名字及相應貸款號和金額customer_name,loan_number,amount(borrowerloan)2023/2/12第五十頁，共七十一頁，2022年，8月28日Query2

customer_name,branch_name

(depositor

account)

temp(branch_name)

({(“Downtown”),(“Uptown”)})注意Query2使用了常數關系查詢例子(cont.)找到至少在“Downtown”和“Uptown”支行有賬戶的客戶名字Query1customer_name(branch_name=“Downtown”(depositor

account))customer_name(branch_name=“Uptown”(depositor

account))2023/2/12第五十一頁，共七十一頁，2022年，8月28日找到在Brooklyn城市的所有支行都有賬戶的所有客戶查詢例子(cont.)

customer_name,branch_name

(depositor

account)

branch_name(branch_city=“Brooklyn”(branch))2023/2/12第五十二頁，共七十一頁，2022年，8月28日擴展關系代數操作廣義投影（GeneralizedProjection）聚集函數（AggregateFunctions）外連接（OuterJoin）2023/2/12第五十三頁，共七十一頁，2022年，8月28日廣義投影擴展投影運算，允許在投影列表中使用算術函數

E

是任何關系代數表達式每個F1,F2,…,Fn

是涉及常數和模式E上的屬性的算術表達式假設有關系credit_info(customer_name,limit,credit_balance),

找到每個客戶還能花多少錢：

customer_name,limit–credit_balance(credit_info)2023/2/12第五十四頁，共七十一頁，2022年，8月28日廣義投影－例子2023/2/12第五十五頁，共七十一頁，2022年，8月28日聚集函數和運算聚集函數（Aggregationfunction）輸入值的一個集合，返回單一值作為結果：

avg:averagevalue（平均值）

min:minimumvalue（最小值）

max:maximumvalue（最大值）

sum:sumofvalues（代數和）

count:numberofvalues（值的數量）關系代數中的聚集運算（Aggregateoperation）

E

關系代數表達式G1,G2…,Gn

是用于分組的屬性列表i（可以是空（empty））同一組中所有元組在G1,G2…,Gn

上的值相同不同組中元組在G1,G2…,Gn

上的值不相同每個Fi

是一個聚集函數每個Ai

是一個屬性名2023/2/12第五十六頁，共七十一頁，2022年，8月28日聚集運算–例子關系r:ABC77310g

sum(c)(r)sum(c)272023/2/12第五十七頁，共七十一頁，2022年，8月28日聚集運算–例子（Cont.）關系account

以branch-name分組:branch_name

gsum(balance)(account)branch_nameaccount_numberbalancePerryridgePerryridgeBrightonBrightonRedwoodA-102A-201A-217A-215A-222400900750750700branch_namesum(balance)PerryridgeBrightonRedwood130015007002023/2/12第五十八頁，共七十一頁，2022年，8月28日聚集函數(Cont.)聚集運算和和廣義投影運算一樣，其運算結果沒有名字可以使用更名運算指定名字為了方便，我們允許更名成為聚集運算一部分

branch_name

gsum(balance)assum_balance(account)前面廣義投影例子：

customer_name,limit–credit_balanceascredit_available(credit_info)2023/2/12第五十九頁，共七十一頁，2022年，8月28日外連接連接運算的擴展，用來避免信息丟失計算連接，然后在計算結果中加上一個關系在另一個關系中沒有匹配的元組使用null

值:null表示值是“不知道”或“不存在”根據定義，所有涉及null的比較（不精確地說）是錯誤的我們將在后面學習和null值比較的精確意思2023/2/12第六十頁，共七十一頁，2022年，8月28日外連接–例子關系loan關系borrowercustomer_nameloan_numberJonesSmithHayesL-170L-230L-155300040001700loan_numberamountL-170L-230L-260branch_nameDowntownRedwoodPerryridge2023/2/12第六十一頁，共七十一頁，2022年，8月28日外連接–例子（cont.）連接（Join）

loanborrowerloan_numberamountL-170L-23030004000customer_nameJonesSmithbranch_nameDowntownRedwoodJonesSmithnullloan_numberamountL-170L-230L-260300040001700customer_namebranch_nameDowntownRedwoodPerryridge

左（外）連接（LeftOuterJoin）loanborrower2023/2/12第六十二頁，共七十一頁，2022年，8月28日外連接–例子（cont.）loan_numberamountL-170L-230Lullcustomer_nameJonesSmithHayesbranch_nameDowntownRedwoodnullloan_numberamountL-170L-230L-260L-155300040001700nullcustomer_nameJonesSmithnullHayesbranch_nameDowntownRedwoodPerryridgenull全（外）連接（FullOuterJoin）loanborrower右（外）連接（RightOuterJoin）loanborrower2023/2/12第六十三頁，共七十一頁，2022年，8月28日Null值對元組的某些屬性可能具有空值（null不是empty）,使用null表示null

表示不知道的值或不存在的值任何涉及null

的算術表達式結果都是null聚集函數簡單忽略null值(如在SQL中)對冗余消除和和分組,null的處理類似其他值，并且兩個null值假設是一樣的(如在SQL中)2023/2/12第六十四頁，共七十一頁，2022年，8月28日Null值（cont.）和null值比較返回特殊的真值:unknown在三值邏輯運算中使用真值unknown（介乎“真假之間”）：OR:(unknown

or

true)=true,

(unknown

or

false)=unknown

(unknownorunknown)=unknownAND:

(trueandunknown)=unknown,

(falseandunkn