關(guān)系(數(shù)據(jù)庫)

時(shí)間：2022-12-23 10:30:02 | 來源：信息時(shí)代

時(shí)間：2022-12-23 10:30:02 來源：信息時(shí)代

    關(guān)系 : 用集合描述事物之間聯(lián)系的數(shù)學(xué)概念,在計(jì)算機(jī)科學(xué)技術(shù)及數(shù)據(jù)庫中有廣泛的應(yīng)用。
(1)有序?qū)?稱一對有序的元素x與y為有序?qū)蛴行?元組,記作〈x,y〉,其中x稱為有序?qū)Φ牡谝粋€(gè)元素,y稱為有序?qū)Φ牡诙€(gè)元素。注意:有序?qū)Φ膬蓚€(gè)元素是有順序的,〈1,a〉≠〈a,1〉;〈a,b〉=〈x,y〉,當(dāng)且僅當(dāng)a=x并且b=y?？梢杂眉系恼Z言定義有序?qū)? 〈x,y〉={{x},{x,y}}。
(2)有序n元組:n(n≥3)個(gè)有序的元素x₁,x₂,…,x_n稱作有序n元組,記作〈x₁,x₂,…,x_n〉。可以遞歸定義如下:有序3元組〈x₁,x₂,x₃〉=〈x₁,x₂〉,x₃〉。一般地,有序n元組〈x₁,x₂,…,x_n〉=〈〈x₁,x₂,…,x_n-1〉,x_n〉,n≥3。
(3)笛卡兒積:{〈x,y〉|x∈A且y∈B}稱為集合A與B的笛卡兒積,簡稱卡氏積,記作A×B。更一般地,n維卡氏積A₁×A₂×…×A_n-1×A_n＝{〈x₁,x₂,…,x_n〉|x₁∈A₁,x₂∈A₂,…,x_n∈A_n}。例如,A={1,2},B={a,b,c},則A×B={〈1,a〉,〈1,b〉,〈1,c〉,〈2,a〉,〈2,b〉,〈2,c〉}。又如,A={a},B={1,2},C={α,β},則A×B×C={〈a,1,α〉,〈a,1,β〉,〈a,2,α〉,〈a,2,β〉}。
(4)二元關(guān)系:有序?qū)?gòu)成的集合。二元關(guān)系R中所有有序?qū)Φ牡谝粋€(gè)元素組成的集合稱為R的定義域,記做domR,所有有序?qū)Φ牡诙€(gè)元素組成的集合稱為R的值域,記做ranR。兩者合在一起domR∪ranR稱為R的域,記做fldR。例如,R={〈b,2〉,〈c,3〉,〈1,2〉},則domR={1,b,c},ranR={2,3}, fldR={1, 2, 3, b, c}。 空集∅也是一個(gè)關(guān)系,稱為空關(guān)系,表示沒有任何關(guān)系。設(shè)R是二元關(guān)系,常把〈x,y〉∈R記為xRy。
當(dāng)domRA且ranRB, 即RA×B時(shí), 稱R是A到B的二元關(guān)系。特別地,A到A的二元關(guān)系稱作A上的二元關(guān)系。A上的恒等關(guān)系I_A＝{〈x,x〉|x∈A}。A上的全域關(guān)系E_A＝A×A。例如,設(shè)A={a,b},則A上的恒等關(guān)系I_A＝{〈a,a〉,〈b,b〉},全域關(guān)系E_A＝{〈a,a〉,〈b,b〉,〈a,b〉,〈b,a〉}。
(5) A上二元關(guān)系的性質(zhì): ①自反性: 如果∀x∈A,〈x, x〉∈R, 則稱R是自反的。R是自反的當(dāng)且僅當(dāng)I_AR;②反自反性:如果∀x∈A,〈x,x〉∉R,則稱R是反自反的。R是反自反的當(dāng)且僅當(dāng)I_A∩R=∅; ③對稱性: 如果∀x, y∈A, 若〈x, y〉∈R必有〈y,x〉∈R,則稱R是對稱的; ④反對稱性: 如果∀x, y∈A, 若x≠y必有〈x,y〉與〈y,x〉不能同時(shí)屬于R, 則稱R是反對稱的;⑤傳遞性: 如果∀x, y,z∈A,若〈x,y〉∈R且〈y,z〉∈R必有〈x,z〉∈R,則稱R是傳遞的。
(6) R的逆關(guān)系:R^-1＝{〈x,y〉|〈y,x〉∈R}。
(7)關(guān)系的合成(或復(fù)合): 關(guān)系R與S的合成RoS={〈x,y〉|存在t使得〈x,t〉∈S且〈t,y〉∈R)}。也有定義為RoS={〈x,y〉|存在t使得〈x,t〉∈R且〈t,y〉∈S)}。例如,R={〈1,2〉,〈1,3〉,〈3,4〉},S={〈3,1〉,〈2,5〉},則RoS={〈3,2〉,〈3,3〉},而SoR={〈1,1〉,〈1,5〉}。
(8)關(guān)系圖: A中的每一個(gè)元素用一個(gè)圓點(diǎn)表示,對每一對〈x,y〉∈R,用從x到y(tǒng)的箭頭表示,稱這樣得到的圖為R的關(guān)系圖,記為G_R。例如,A={a,b,c,d},R={〈a,a〉,〈a,b〉,〈b,c〉,〈c,d〉,〈c,b〉},則G_R如圖1所示。

圖1 一個(gè)關(guān)系圖

下面是幾個(gè)常用的A上二元關(guān)系。
(1)相容性關(guān)系: 自反和對稱的二元關(guān)系稱作相容性關(guān)系。
(2)等價(jià)關(guān)系: 自反、對稱和傳遞的關(guān)系稱作等價(jià)關(guān)系。①等價(jià)類:設(shè)R是A上的等價(jià)關(guān)系,a∈A,所有與a有關(guān)系的元素組成的集合稱作a關(guān)于R的等價(jià)類,記作[a]_R,即[a]_R＝{x|xRa}。②商集:A關(guān)于R的所有等價(jià)類構(gòu)成的集合稱作A關(guān)于R的商集,記為A/R。例如,設(shè)整數(shù)n≥2,在整數(shù)集合Z上,定義xRy當(dāng)且僅當(dāng)x-y可被n整除,則R是Z上的等價(jià)關(guān)系。通常把這個(gè)商集Z/R記作Z_n,[x]_R記作[x]_n,Z_n＝{[0]_n,[1]_n,…,[n-1]_n},其中[x]_n＝{x+kn|k∈Z},x=0,1,…,n-1。
(3)偏序關(guān)系: 自反、反對稱和傳遞的關(guān)系稱作偏序關(guān)系, 常用≼表示偏序關(guān)系。 設(shè)≼是A上的偏序關(guān)系, 稱〈A, ≼〉為偏序集。 若x≼y且x≠y,則記為xy。 在偏序集上, 如果x≼y或y≼x, 則稱x與y是可比的;如果xy且不存在z使得xzy,則稱y覆蓋x。
(4)哈斯圖:若xy且y覆蓋x,將代表y的頂點(diǎn)放在代表x的頂點(diǎn)之上,并且在x與y之間連一條線,所得的圖稱為偏序關(guān)系的哈斯圖。例如,設(shè)偏序集〈A, ≼〉, 其中A={a,b,c,d,e,},≼={〈a,c〉,〈a,d〉,〈b,c〉,〈b,d〉,〈c,e〉,〈d,e〉,〈a,e〉,〈b,e〉} ∪I_A,其哈斯圖如圖2所示。

圖2 一個(gè)哈斯圖

設(shè)偏序集〈A, ≼〉,BA, y∈B。①最大元: 如果∀x∈B, x≼y, 則稱y為B的最大元; ②最小元:如果∀x∈B,y≼x,則稱y為B的最小元;③極大元:如果在B中除y外不存在x使得y≼x, 則稱y為B的極大元; ④極小元: 如果在B中除y外不存在x使得x≼y, 則稱y為B的極小元。
設(shè)偏序集〈A,≼〉, BA,y∈A。①上界: 如果∀x∈B,x≼y,則稱y為B的上界;②下界:如果∀x∈B,y≼x, 則稱y為B的下界;③上確界: B的所有上界中的最小元稱作B的上確界,或最小上界; ④下確界: B的所有下界中的最大元稱作B的下確界,或最大下界。例如,在圖2所示的偏序集中,e是A的最大元(當(dāng)然也是極大元)和上確界(當(dāng)然也是上界),極小元為a和b,無最小元,無下界(更無下確界)。B={a,c,d}有上確界e(當(dāng)然也是上界),有兩個(gè)極大元c和d,無最大元,a是B的最小元(當(dāng)然也是極小元)和下確界(當(dāng)然也是下界)。