关系(数据库)

时间：2022-12-23 10:30:02 | 来源：信息时代

时间：2022-12-23 10:30:02 来源：信息时代

    关系 : 用集合描述事物之间联系的数学概念,在计算机科学技术及数据库中有广泛的应用。
(1)有序对:称一对有序的元素x与y为有序对或有序2元组,记作〈x,y〉,其中x称为有序对的第一个元素,y称为有序对的第二个元素。注意:有序对的两个元素是有顺序的,〈1,a〉≠〈a,1〉;〈a,b〉=〈x,y〉,当且仅当a=x并且b=y。可以用集合的语言定义有序对: 〈x,y〉={{x},{x,y}}。
(2)有序n元组:n(n≥3)个有序的元素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)二元关系:有序对构成的集合。二元关系R中所有有序对的第一个元素组成的集合称为R的定义域,记做domR,所有有序对的第二个元素组成的集合称为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}。 空集∅也是一个关系,称为空关系,表示没有任何关系。设R是二元关系,常把〈x,y〉∈R记为xRy。
当domRA且ranRB, 即RA×B时, 称R是A到B的二元关系。特别地,A到A的二元关系称作A上的二元关系。A上的恒等关系I_A＝{〈x,x〉|x∈A}。A上的全域关系E_A＝A×A。例如,设A={a,b},则A上的恒等关系I_A＝{〈a,a〉,〈b,b〉},全域关系E_A＝{〈a,a〉,〈b,b〉,〈a,b〉,〈b,a〉}。
(5) A上二元关系的性质: ①自反性: 如果∀x∈A,〈x, x〉∈R, 则称R是自反的。R是自反的当且仅当I_AR;②反自反性:如果∀x∈A,〈x,x〉∉R,则称R是反自反的。R是反自反的当且仅当I_A∩R=∅; ③对称性: 如果∀x, y∈A, 若〈x, y〉∈R必有〈y,x〉∈R,则称R是对称的; ④反对称性: 如果∀x, y∈A, 若x≠y必有〈x,y〉与〈y,x〉不能同时属于R, 则称R是反对称的;⑤传递性: 如果∀x, y,z∈A,若〈x,y〉∈R且〈y,z〉∈R必有〈x,z〉∈R,则称R是传递的。
(6) R的逆关系:R^-1＝{〈x,y〉|〈y,x〉∈R}。
(7)关系的合成(或复合): 关系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)关系图: A中的每一个元素用一个圆点表示,对每一对〈x,y〉∈R,用从x到y的箭头表示,称这样得到的图为R的关系图,记为G_R。例如,A={a,b,c,d},R={〈a,a〉,〈a,b〉,〈b,c〉,〈c,d〉,〈c,b〉},则G_R如图1所示。

图1 一个关系图

下面是几个常用的A上二元关系。
(1)相容性关系: 自反和对称的二元关系称作相容性关系。
(2)等价关系: 自反、对称和传递的关系称作等价关系。①等价类:设R是A上的等价关系,a∈A,所有与a有关系的元素组成的集合称作a关于R的等价类,记作[a]_R,即[a]_R＝{x|xRa}。②商集:A关于R的所有等价类构成的集合称作A关于R的商集,记为A/R。例如,设整数n≥2,在整数集合Z上,定义xRy当且仅当x-y可被n整除,则R是Z上的等价关系。通常把这个商集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)偏序关系: 自反、反对称和传递的关系称作偏序关系, 常用≼表示偏序关系。 设≼是A上的偏序关系, 称〈A, ≼〉为偏序集。 若x≼y且x≠y,则记为xy。 在偏序集上, 如果x≼y或y≼x, 则称x与y是可比的;如果xy且不存在z使得xzy,则称y覆盖x。
(4)哈斯图:若xy且y覆盖x,将代表y的顶点放在代表x的顶点之上,并且在x与y之间连一条线,所得的图称为偏序关系的哈斯图。例如,设偏序集〈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 一个哈斯图

设偏序集〈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的极小元。
设偏序集〈A,≼〉, BA,y∈A。①上界: 如果∀x∈B,x≼y,则称y为B的上界;②下界:如果∀x∈B,y≼x, 则称y为B的下界;③上确界: B的所有上界中的最小元称作B的上确界,或最小上界; ④下确界: B的所有下界中的最大元称作B的下确界,或最大下界。例如,在图2所示的偏序集中,e是A的最大元(当然也是极大元)和上确界(当然也是上界),极小元为a和b,无最小元,无下界(更无下确界)。B={a,c,d}有上确界e(当然也是上界),有两个极大元c和d,无最大元,a是B的最小元(当然也是极小元)和下确界(当然也是下界)。