面向?qū)ο笏饕?數(shù)據(jù)庫)

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

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

    面向?qū)ο笏饕?: 在面向?qū)ο髷?shù)據(jù)庫(OODB)中所建立的索引。與傳統(tǒng)的關(guān)系數(shù)據(jù)庫在一個(gè)屬性或一組屬性上建立一個(gè)索引有所不同,OODB引入新的索引: 類層次索引和嵌套屬性索引等。
類層次索引(class level index): 類C的屬性A的類層次索引,是以C為根的類層次上所有類的屬性A的一個(gè)單一索引。索引屬性是建立在其上的屬性,而索引類是建立在這些類屬性上的類層次的根。例如,可以在圖1的車輛類及其重量屬性上建立一個(gè)類層次索引,則重量是該索引的索引屬性,而車輛是索引類。在面向?qū)ο髷?shù)據(jù)模型下,一個(gè)類既可能是一個(gè)類層次的根,也可能是一個(gè)類復(fù)合層次的根。一個(gè)類從它的超類繼承屬性,它的所有直接和間接的子類共享相同的屬性。

圖1 類層次和類復(fù)合層次

類層次索引和單一類索引的實(shí)現(xiàn)采用B⁺-樹。在這兩種索引文件中,內(nèi)結(jié)點(diǎn)的格式是相同的。每個(gè)索引項(xiàng)由鍵的長度、鍵、指向下一層結(jié)點(diǎn)的指針組成,如圖2(a)所示。類層次索引的葉結(jié)點(diǎn)格式和單一類索引的葉結(jié)點(diǎn)格式分別如圖2(b)和圖2(c)所示。
對于類層次索引,其存儲(chǔ)要求索引頁可以足夠地保留以索引類為根的類的所有實(shí)例對象的oids;而在相應(yīng)類層次上每個(gè)類的單一類索引集合的存儲(chǔ)要求,是每個(gè)單一類索引的索引頁總數(shù)之和。
嵌套屬性索引(nested-attribute index):在面向?qū)ο髷?shù)據(jù)模型中,允許一個(gè)對象的屬性值是一個(gè)對象或一組對象,構(gòu)成嵌套對象。盡管一個(gè)查詢返回一個(gè)目標(biāo)類的實(shí)例對象集合,但查找謂詞可以指定在該類的任意嵌套屬性上。一個(gè)類的嵌套屬性上的索引稱為嵌套屬性索引。在類的嵌套屬性索引中,對屬性的索引是間接的,是針對類的嵌套屬性的。換句話說,對屬性的索引并不針對索引類的屬性。嵌套屬性索引使我們能夠通過遍歷一個(gè)單一索引來計(jì)算復(fù)雜的對象查詢。嵌套屬性索引特別適合于嵌套查詢類型,這類查詢包含了關(guān)于索引類的多重嵌套屬性的謂詞。

圖2 結(jié)點(diǎn)格式

給定一個(gè)類復(fù)合層次C₁,C₂,…,C_n。A₁,A₂,…,A_n(n≥1)作為復(fù)合層次上的路徑,提供了對象數(shù)據(jù)庫的一種查找能力。這里C₁是類復(fù)合層次上的類,A₁是類C₁的屬性,A_i是類復(fù)合層次上類C_i的屬性,C_i是類C_i-1的屬性A_i-1的值域,1<i≤n。合成路徑上類的個(gè)數(shù)等于路徑長度?？梢钥闯?必須遍歷包括C₁在內(nèi)的n個(gè)類才能到達(dá)嵌套屬性A_n。這里,除了路徑中最后一個(gè)屬性的值域可以是原子類或非原子類,路徑上其他所有的類必須是非原子類。
將一條合成路徑表示成n+1個(gè)對象組成的一個(gè)序列:O₁,O₂,…,O_n,O_n+1。這里,O₁是類C₁的實(shí)例對象,O_i是對象O_i-1的屬性A_i-1的值,1<i≤n+1。對象O_i是類C_i的實(shí)例。在圖3中,O₁,O₂,…,O_n,O_n+1表示一條合成路徑。正向遍歷路徑表示從O_i開始,沿路徑依次訪問對象O_i+1,O_i+2,…,O_n-1,O_n,O_i通過復(fù)合屬性A_i引用O_i+1,O_n-1通過復(fù)合屬性A_n-1引用O_n。路徑上的對象也可以反向遍歷,但路徑上的對象之間必須設(shè)置反向引用; 否則,一般不能使用嵌套索引。

圖3 合成路徑O₁,O₂,…,O_n,O_n+1

圖4 C₁.A₁.A₂上的對象

為說明起見,將合成路徑上的嵌套索引NX表示成一組偶對(O,S)。這里,S={O′,存在一條合成路徑O₁,O₂,…,O_n,O_n+1,并且,O′=O₁,O=O_n+1},(O,S)偶對的元素O是索引鍵。嵌套索引NX將路徑上的末端對象O_n+1和起始對象O₁關(guān)聯(lián)在一起。在圖4中表示一組路徑C₁.A₁.A₂上的對象, 路徑上的嵌套索引將屬性A₂的值與C₁的一組oids關(guān)聯(lián)在一起,類C₂的屬性A₂是索引鍵。該嵌套索引包括以下偶對: (O₃,{O₁″})和(O₃′,{O₁,O₁′})。