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

時間：2022-12-20 22:30:01 | 來源：信息時代

時間：2022-12-20 22:30:01 來源：信息時代

    泛關(guān)系 : 用戶觀念上的數(shù)據(jù)庫中的一種特殊關(guān)系。在數(shù)據(jù)庫設(shè)計時,為了使函數(shù)依賴模式不存在弊病,需要對不屬于范式的函數(shù)依賴模式進行分解,然而分解就會使函數(shù)依賴模式的數(shù)目增加,函數(shù)依賴模式越多,用戶使用就越不方便。在存儲時按分解后的函數(shù)依賴模式存儲,在使用時讓用戶仍把數(shù)據(jù)庫中所有屬性的集合想象成是一個整體的關(guān)系模式,所有函數(shù)依賴都認為是這個關(guān)系模式上的函數(shù)依賴,所有數(shù)據(jù)都理解成是這個關(guān)系模式上的單一關(guān)系中的數(shù)據(jù)。用戶的所有操作也都理解成是對這個單一關(guān)系的,這個想象中的單一關(guān)系就稱為“泛關(guān)系”。
“泛關(guān)系”的研究是在1976年Bernstein提出泛屬性集的觀點后開始的。早期的研究工作因為受了泛關(guān)系上的元組也不允許有空值這樣一個默認的假設(shè)的束縛,所以進展并不大。1980年,Honeyman、Lander及Yannakakis開始研究了含空值的泛關(guān)系的理論,提出了全投影、泛例、有效模式、元組的淹沒、關(guān)系的淹沒、代表泛例等全新概念,使“泛關(guān)系”的研究有了新起色,出現(xiàn)了許多新成果。后來,為了對泛關(guān)系進行查詢,人們還提出了窗口函數(shù)的思想。1982年,Fagin、Mendelzon及Ullman等提出了一種語義結(jié)構(gòu)窗口,這種窗口很適合于查詢語義的表達。1983年,Sagiv定義了鍵依賴,擴展連接及唯一性模式的新概念,并用唯一性模式作為查詢的一種窗口。1986年,Maeir等推廣了這個結(jié)果,允許不是鍵依賴的函數(shù)依賴集形成窗口。
由于泛關(guān)系是一種用戶觀念上想像的數(shù)據(jù)庫,所以它的可用性在歷史上曾受到置疑。Kent(1981年)、Atzeni(1982年初)及Parker(1982年初)都發(fā)表文章認為泛關(guān)系作為一種數(shù)據(jù)模型是不合適的。1982年10月,Ullman則著文給以反駁。1983年,Kent又兩次提出對泛關(guān)系的反對意見。同年Ullman又給予反駁。有趣的是關(guān)系數(shù)據(jù)庫理論的創(chuàng)始人Codd竟然也反對泛關(guān)系的思想,1988年他發(fā)表文章支持早期對泛關(guān)系的那些反對意見。特別還舉例說明泛關(guān)系領(lǐng)域中無法處理的以下查詢: 關(guān)系模式R={雇員,城市,倉庫},基本語義單位S₁＝{雇員,城市}表示雇員所居住的城市,基本語義單位S₂＝{城市,倉庫}表示倉庫所在的城市(基本語義單位請見本條目后面的說明)。查:其居住地有一個倉庫或多個倉庫的雇員。但在同年,Vardi等就給予了反駁,他們給出了基于唯一性模式窗口及語義結(jié)構(gòu)窗口的對這個查詢的查詢解釋。總體來看,現(xiàn)在大多數(shù)人還都是認為泛關(guān)系理論是適宜的。
泛關(guān)系的謂詞定義如下:設(shè)U是數(shù)據(jù)庫中全部屬性的集合,Ω={R,…,R_n}是U上的一個數(shù)據(jù)庫模式(數(shù)據(jù)庫模式請參看關(guān)系數(shù)據(jù)庫條目)。S_i＝{A_i1,…,A_it}U, 〈x_i1, …,x_it〉是S_i上的變量元組,P_i是以x_i1,…,x_it為變量的謂詞,簡稱S_i上的謂詞,記號P_i(S_i)表示相應(yīng)的謂詞公式。u是對x_i1,…,x_it的一個賦值。若u(x_i1),…,u(x_it)能使
P_i為真,則稱u使P_i(S_i)為真。如果這里的每個P_i都不能再分成兩個謂詞的合取,而且每個S_i都是某個R_j的子集,而〈x_i1,…,x_it〉是整個U上的變量元組,且u使P₁(S₁)∧…∧P_k(S_k)為真,則稱〈u(x₁),…,u(x_n)〉為U上的由謂詞公式集合P₁(S₁),…,P_k(S_k)決定的一個元組,并稱集合{〈u(x₁₎,…,u(x_n)〉|u使P₁(S₁)∧…∧P_k(S_k)為真}為U上由謂詞公式集合P₁(S₁),…,P_k(S_k)決定的泛關(guān)系。每個S_i都稱為基本語義單位,并稱Γ={S₁,…,S_k}為U上的語義結(jié)構(gòu)。
若r是U上的一個泛關(guān)系,r中允許有空值。XU, 則r在X上的全投影, 記作r[[X]], 是集合{u[X]|u∈r,u在X上沒有空值}。例如U={A,B,C,D},U上的泛關(guān)系r如表1所示。則r[[AB]]={〈a,b〉}, r[[AC]]={〈a, c〉,〈e,f〉}, r[[BD]]=∅。

表1 一個含空值的泛關(guān)系(其中丄表示空值)

A	B	C	D
a	b	c	⊥1
e	⊥2	f	⊥3

如果Ω={R,…,R_n}是u上的一個數(shù)據(jù)庫模式,ω={r₁,…,r_n}是Ω上的一個數(shù)據(jù)庫,而r是U上的一個泛關(guān)系,且對每個i都有r[[R_i]]r_i(i=1, …,n),則稱r是ω上的一個泛例。若∑是U上的函數(shù)依賴集合,ω中的關(guān)系都適合∑,而ω的泛例r也適合∑,則稱r是ω上適合∑的泛例。如果Ω的每個適合∑的數(shù)據(jù)庫都有適合∑的泛例存在,則稱(Ω,∑)為一個有效模式。h是泛關(guān)系r中所有值(包括空值)上的映射,滿足對所有非空值是恒等映射,若u₁,u₂∈r且h(u₁₎＝u₂,則稱u₂淹沒u₁。記{h(u)|u∈r}為h(r), 若h(r₁₎h(r₂₎, 則稱r₂淹沒r₁。 如果r₀是ω的一個適合∑的泛例,而且對任一個ω的適合∑的泛例r都有r淹沒r₀,則稱r₀是ω的適合∑的代表泛例。顯然,若(Ω,∑)不是有效模式,則必有Ω的某個數(shù)據(jù)庫ω沒有適合∑的代表泛例,而且同一個ω的所有代表泛例互相淹沒。構(gòu)造代表泛例的方法如下:
設(shè)全部屬性的集合為U,其上的數(shù)據(jù)庫模式為Ω={R₁,…,R_n},依賴集合為∑,Ω上的適合∑的數(shù)據(jù)庫為ω={r₁,…,r_n}。
對每個r_i中的元組u,我們都用以下方法構(gòu)造一個U上的元組v。
(1)若A_j∈R_i,則令v[A_j]=u[A_j]。
(2)若A_j∉R_i, 則令v[A_j]=丄_k。
這里,丄_k是一個尚未用到過的空值,所有r_i(i=1,…,n)中的所有元組u都做了以上的處理后,這些構(gòu)造出來的元組v的集合將是U上的一個含空值的關(guān)系,記作r⁽⁰⁾。當(dāng)然我們也可以把這個r⁽⁰⁾看作是U上的一個造型表,再用∑中的依賴對這個r⁽⁰⁾進行追趕,應(yīng)用的方法是:若依賴是元組產(chǎn)生依賴,則添加一個新元組; 若依賴是等值產(chǎn)生依賴,則將某兩個值(包括空值的情況)代換為同一個值。不過我們要求,當(dāng)需要代換的兩個值中有一個是非空值時,則將另一個空值代換成非空值; 當(dāng)兩個都是空值時,則代換成其中任何一個都可以。而且這種代換是將所有出現(xiàn)該值的地方全代換。每次應(yīng)用了一個依賴以后都檢查一下有沒有元組被其他元組淹沒,如果有,則刪掉被淹沒的元組。
追趕的結(jié)果可能有兩個:
(1)可能需要將兩個不同的非空值代換成同一個值,這時代表泛例不存在。
(2)可能一直遇不到(1)中的情況,但再應(yīng)用∑中的依賴已不能使造型表有改變了。這時,這個最后的造型表就是我們所需要的代表泛例。
將對泛關(guān)系的查詢轉(zhuǎn)換為對具體真實關(guān)系的查詢的任務(wù)稱為泛關(guān)系的查詢解釋。查詢解釋請見參考文獻[1]。