李宇珺，彭智勇，吳 瑕，蘭 海，彭煜瑋

武漢大學(xué) 計(jì)算機(jī)學(xué)院，武漢 430072

1 引言

面向?qū)ο竽Ｐ徒鉀Q了傳統(tǒng)關(guān)系模型難以建模復(fù)雜數(shù)據(jù)的問(wèn)題，但對(duì)象的封裝性使得其對(duì)象難以分割和重組，從而不具有關(guān)系模型的柔軟性。針對(duì)上述問(wèn)題，對(duì)象代理模型（object deputy model，ODM）應(yīng)運(yùn)而生[1]，它兼具關(guān)系模型的柔軟性和面向?qū)ο竽Ｐ偷慕Ｄ芰?。近年?lái)，ODM被廣泛應(yīng)用于數(shù)據(jù)倉(cāng)庫(kù)[2]、生物數(shù)據(jù)管理[3]、地理信息系統(tǒng)[4]、科學(xué)工作流[5]和不確定數(shù)據(jù)管理[6]等領(lǐng)域。對(duì)象代理數(shù)據(jù)庫(kù)（object deputy database，ODDB）管理系統(tǒng)圖騰[7]（Totem）已基于ODM開(kāi)發(fā)完成。它在繼承了面向?qū)ο髷?shù)據(jù)庫(kù)諸多優(yōu)點(diǎn)（如直接建模復(fù)雜對(duì)象等）的基礎(chǔ)上，使用代理對(duì)象增強(qiáng)了對(duì)象的柔軟性，允許對(duì)已有對(duì)象進(jìn)行分解、組合和擴(kuò)充，比面向?qū)ο髷?shù)據(jù)庫(kù)具有更柔軟的建模能力。

ODDB中的每個(gè)對(duì)象和其每一個(gè)源對(duì)象或代理對(duì)象都被一個(gè)雙向指針鏈接在一起，這類指針?lè)Q為雙向指針?？珙惒樵冏鳛镺DDB的主要查詢功能之一，是指基于對(duì)象間的雙向指針鏈接，從某個(gè)類的對(duì)象出發(fā)，沿著類路徑到達(dá)另一個(gè)與其存在直接或間接代理關(guān)系的類，并對(duì)該類中關(guān)聯(lián)對(duì)象進(jìn)行的查詢?？珙惒樵兪怯陕窂奖磉_(dá)式（path expression，PE）實(shí)現(xiàn)的[8]，因此優(yōu)化PE的計(jì)算效率對(duì)提升ODDB的性能有重大影響。

本文針對(duì)ODDB的PE計(jì)算提出了一種索引結(jié)構(gòu)——倒排路徑索引（inverted path index，IPI），并基于IPI設(shè)計(jì)實(shí)現(xiàn)了計(jì)算PE的方法。IPI的核心思想是物化對(duì)象間的代理關(guān)系，并允許在謂詞條件上建立索引以過(guò)濾不滿足條件的對(duì)象?；贗PI的PE計(jì)算方法，能靈活用于任意PE，同時(shí)避免計(jì)算中冗余的對(duì)象遍歷，有效地減少PE的計(jì)算開(kāi)銷?？傮w來(lái)說(shuō)，本文的主要貢獻(xiàn)如下：（1）提出一種新的針對(duì)ODDB的索引結(jié)構(gòu)（IPI），支持任意路徑/帶謂詞條件的PE計(jì)算，以極小的效率代價(jià)為跨類查詢提供更多的靈活性。（2）提出使用IPI計(jì)算PE的IPI索引方法以及維護(hù)IPI的方法。（3）通過(guò)實(shí)驗(yàn)證明了所提出的IPI索引方法的有效性。

本文組織結(jié)構(gòu)如下：第2章介紹相關(guān)工作；第3章給出ODDB中PE的基礎(chǔ)知識(shí)；第4章介紹倒排路徑索引IPI，并提出使用IPI計(jì)算PE的IPI索引方法以及維護(hù)IPI的方法；第5章討論IPI的靈活性；第6章通過(guò)實(shí)驗(yàn)證明提出的IPI索引方法的有效性；第7章進(jìn)行總結(jié)和展望。

2 相關(guān)工作

ODDB中由對(duì)象間的代理關(guān)系構(gòu)成的網(wǎng)狀結(jié)構(gòu)可以比作一個(gè)圖。圖數(shù)據(jù)庫(kù)具有管理超大規(guī)模圖的能力[9]，故其可達(dá)性問(wèn)題為PE計(jì)算提供了一種解決方案。文獻(xiàn)[10]提出Tree-Based索引來(lái)解決帶標(biāo)簽圖的可達(dá)性問(wèn)題。文獻(xiàn)[11]提出Top-Chain來(lái)解決時(shí)序圖的可達(dá)性問(wèn)題。然而，PE計(jì)算和圖數(shù)據(jù)庫(kù)的可達(dá)性問(wèn)題之間存在一個(gè)本質(zhì)的區(qū)別：前者是在一個(gè)非常大的圖中確定兩個(gè)結(jié)點(diǎn)之間是否存在由邊組成的路徑；后者則意味著在許多由對(duì)象構(gòu)成的小圖中迭代解決可達(dá)性問(wèn)題。因此，解決圖數(shù)據(jù)庫(kù)可達(dá)性問(wèn)題的方法并不適用于ODDB的PE計(jì)算。

PE的概念并不是ODDB所特有，早在XML（extensible markup language）中它就已經(jīng)存在，用于訪問(wèn)XML的嵌套文檔結(jié)構(gòu)。目前XML針對(duì)PE計(jì)算的基本索引方法有：路徑分解法[12]和樹(shù)遍歷法[13]。路徑分解法將復(fù)雜PE分解為簡(jiǎn)單PE依次進(jìn)行計(jì)算，再把計(jì)算結(jié)果連接起來(lái)，核心思想是分解再連接。由于ODDB中PE各層的連接關(guān)系包含了雙方對(duì)象實(shí)例間的所有代理關(guān)系，連接的代價(jià)過(guò)大，路徑分解法的思想并不適用于ODDB的PE計(jì)算。樹(shù)遍歷法則采用自頂向下或自底向上的方式遍歷文檔樹(shù)，該方法需要遍歷某元素通往葉子節(jié)點(diǎn)的所有路徑，其思想類似于ODDB的指針跟蹤算法（pointer tracker，PT）[14-15]。

PT是計(jì)算ODDB中PE的基本方法：首先沿著PE的導(dǎo)航路徑進(jìn)行對(duì)象遍歷，檢索滿足PE各層所定義謂詞條件的路徑實(shí)例，然后獲取這些實(shí)例上的終點(diǎn)對(duì)象，最后由PE的目標(biāo)表達(dá)式投影運(yùn)算得出結(jié)果。顯然，對(duì)象遍歷是計(jì)算中最耗時(shí)的部分，它需要遍歷起點(diǎn)類通往終點(diǎn)類的所有路徑實(shí)例，頻繁的I/O操作降低了計(jì)算效率。目前針對(duì)ODDB中PE計(jì)算的優(yōu)化方法還比較少。文獻(xiàn)[14]提出的對(duì)象代理路徑索引（object deputy path index，ODPI）針對(duì)特定的路徑建立索引，存儲(chǔ)滿足該路徑的所有路徑實(shí)例，減少了對(duì)象遍歷的時(shí)間，但它不適用于中間類帶謂詞條件的PE。路徑導(dǎo)航索引（path navigation index，PNI）[15]解決了該問(wèn)題，它基于物化的路徑實(shí)例提供了關(guān)聯(lián)檢索，以支持帶謂詞條件的PE計(jì)算。然而，由于每個(gè)ODPI/PNI索引都僅服務(wù)于其對(duì)應(yīng)的固定路徑，計(jì)算時(shí)缺乏靈活性。若待查詢PE所依賴的路徑上沒(méi)有建立索引，那ODPI/PNI索引對(duì)計(jì)算是無(wú)效的，此時(shí)只能用PT方法（即不使用索引）來(lái)計(jì)算該P(yáng)E。

針對(duì)上述問(wèn)題，本文提出的倒排路徑索引，物化了對(duì)象間的代理關(guān)系，不僅可以靈活用于任意PE，還能有效減少計(jì)算開(kāi)銷。

3 基本概念

ODM的基本概念包括源類、代理類、源對(duì)象和代理對(duì)象等，首先簡(jiǎn)單描述這些概念，其詳細(xì)定義參見(jiàn)文獻(xiàn)[1]，并在此基礎(chǔ)上給出ODDB中PE的相關(guān)定義和符號(hào)表。

在面向?qū)ο竽Ｐ椭?，所有真?shí)世界的實(shí)體都被抽象為一個(gè)對(duì)象（Object），具有相同屬性的對(duì)象構(gòu)成一個(gè)類（Class）。在邏輯層面，對(duì)象和類類似于關(guān)系數(shù)據(jù)模型中的元組和表，ODM同樣具有對(duì)象和類的概念。在ODM中，不存在父類的類稱為源類，其包含的對(duì)象稱為源對(duì)象；而存在父類的類則稱為代理類，它的對(duì)象實(shí)例稱為代理對(duì)象。

定義1（直接/間接代理關(guān)系）對(duì)任意兩個(gè)類Ci和Cj(i＜j)，若Ci是Cj的源類或代理類，則Ci和Cj之間存在直接代理關(guān)系。給定一系列類{Ci,Ci+1,…,Cj-1,Cj}，若對(duì)任意k∈[i,j)都滿足Ck和Ck+1之間存在直接代理關(guān)系，則Ci和Cj之間存在間接代理關(guān)系。同理可得對(duì)象間的直接/間接代理關(guān)系。

定義2（類網(wǎng)/對(duì)象網(wǎng)）由類之間的代理關(guān)系構(gòu)成的網(wǎng)狀結(jié)構(gòu)稱為類網(wǎng)。其中節(jié)點(diǎn)表示類，邊表示兩個(gè)節(jié)點(diǎn)間的直接代理關(guān)系。同理，由對(duì)象之間的代理關(guān)系構(gòu)成的網(wǎng)狀結(jié)構(gòu)稱為對(duì)象網(wǎng)。

定義3（路徑）給定類網(wǎng)CN，式（1）中的路徑P是類網(wǎng)CN的一條路徑，當(dāng)且僅當(dāng)：（1）Ci∈CN(1≤i≤n)；（2）對(duì)任意i∈[1,n)都滿足Ci和Ci+1之間存在直接代理關(guān)系。其中C1和Cn分別指起點(diǎn)類和終點(diǎn)類，路徑P中的其他類則指中間類。

定義4（路徑實(shí)例）給定式（1）的路徑P，式（2）中的由n個(gè)對(duì)象組成的對(duì)象序列PI稱為P的一個(gè)實(shí)例，當(dāng)且僅當(dāng)：（1）oi是Ci的一個(gè)實(shí)例 (1≤i≤n)；（2）oi與oi+1之間存在直接代理關(guān)系 (1≤i＜n)。其中o1為起點(diǎn)對(duì)象，on為終點(diǎn)對(duì)象。

定義5（PE）給定式（1）的路徑P，式（3）中的PE′是在P上定義的PE當(dāng)且僅當(dāng)：（1）pri是定義在Ci上的謂詞條件（pri可為空，1≤i≤n）；（2）expr是由Cn的屬性和常量通過(guò)算術(shù)或邏輯運(yùn)算符組成的表達(dá)式。其中C1{pr1}→C2{pr2}→…→Cn{prn}稱為PE′的導(dǎo)航路徑，expr則稱為PE的目標(biāo)表達(dá)式。

定義6（PE實(shí)例）給定式（3）的PE′，式（4）中的由n個(gè)對(duì)象組成的對(duì)象序列PEI稱為PE′的一個(gè)實(shí)例當(dāng)且僅當(dāng)：（1）oi是Ci的一個(gè)實(shí)例 (1≤i≤n)；（2）oi與oi+1之間存在直接代理關(guān)系 (1≤i＜n)；（3）oi滿足定義于Ci上的pri(1≤i≤n)。

定義7（跨類查詢）給定式（3）的PE′，針對(duì)PE′的跨類查詢表示從起點(diǎn)類C1的對(duì)象出發(fā)，沿著PE′的導(dǎo)航路徑到達(dá)終點(diǎn)類Cn，對(duì)PE′所有PE實(shí)例的終點(diǎn)對(duì)象進(jìn)行查詢。

圖1給出了一個(gè)教學(xué)管理數(shù)據(jù)庫(kù)的模式，由上述定義可知該數(shù)據(jù)庫(kù)模式是一個(gè)類網(wǎng)，而Course→Cou_Stu→Student是該類網(wǎng)上的一條路徑，(Course{cid=“1”}→Cou_Stu→Student).sid是定義在該路徑上的一個(gè)PE，其中Course是起點(diǎn)類，Student是終點(diǎn)類，{cid=“1”}是定義在Student類上的謂詞條件。

表1總結(jié)了幾個(gè)本文經(jīng)常出現(xiàn)的符號(hào)和術(shù)語(yǔ)。

Fig.1 Schema of teaching management database圖1 教學(xué)管理數(shù)據(jù)庫(kù)模式

Table 1 Symbol table表1 符號(hào)表

4 倒排路徑索引IPI

本章介紹一種靈活高效的索引結(jié)構(gòu)——倒排路徑索引(IPI)。IPI建立在類之上，由Inverted-Object-Index和Predicate-Index組成。前者存儲(chǔ)對(duì)象間的代理關(guān)系；后者則輔助它計(jì)算定義于該類的謂詞條件。IPI支持任意路徑和帶謂詞條件的PE計(jì)算，并能有效減少計(jì)算開(kāi)銷。

4.1 索引的結(jié)構(gòu)

對(duì)于一個(gè)類網(wǎng)中的每個(gè)類，Inverted-Object-Index基于對(duì)象間的雙向指針使用倒排索引來(lái)存儲(chǔ)與該類關(guān)聯(lián)的所有代理關(guān)系，其每個(gè)索引項(xiàng)對(duì)應(yīng)該類的一個(gè)對(duì)象，映射所有與之存在直接或間接代理關(guān)系的對(duì)象。每個(gè)代理關(guān)系對(duì)應(yīng)一個(gè)路徑實(shí)例，因?yàn)镺DM中對(duì)象間的代理關(guān)系不能出現(xiàn)環(huán)[16]，同一對(duì)象網(wǎng)中的任意兩個(gè)對(duì)象間有且僅有一條路徑連通。因此，Inverted-Object-Index存儲(chǔ)的每條路徑實(shí)例的終點(diǎn)對(duì)象可以唯一地標(biāo)識(shí)該路徑實(shí)例。

Inverted-Object-Index是一個(gè)存儲(chǔ)（key,object list）對(duì)集合的索引結(jié)構(gòu)，其中“key”是鍵值，由對(duì)象的唯一標(biāo)識(shí)符（OID）表示，而“object list”（對(duì)象列表）是一組與“key”存在直接或間接代理關(guān)系的對(duì)象，每個(gè)對(duì)象由“所屬類的OID:對(duì)象OID”表示。如圖2所示，Inverted-Object-Index包含一個(gè)構(gòu)建在“key”上的BTree索引（Key Tree），其內(nèi)部節(jié)點(diǎn)與普通B-Tree索引一樣，而葉子節(jié)點(diǎn)中索引項(xiàng)的指針則指向“ObjectList”或“Object Tree”的根頁(yè)面。若某個(gè)“key”的與之存在代理關(guān)系的對(duì)象數(shù)目較多，則在其對(duì)象列表（即“object list”）上創(chuàng)建一個(gè)B-Tree結(jié)構(gòu)（Object Tree）以加快查找速度。

Fig.2 Index structure of Inverted-Object-Index圖2 Inverted-Object-Index的索引結(jié)構(gòu)

第2章提到PT方法在對(duì)象遍歷時(shí)，對(duì)每個(gè)對(duì)象都要進(jìn)行兩步操作：（1）判斷是否匹配路徑；（2）判斷是否滿足定義于該類的謂詞條件。通過(guò)Inverted-Object-Index，能快速找到該類中匹配路徑的對(duì)象實(shí)例，并獲取其所在的路徑實(shí)例上的終點(diǎn)對(duì)象，但無(wú)法判斷這些路徑實(shí)例是否滿足可能定義于PE的謂詞條件。Predicate-Index是針對(duì)謂詞條件計(jì)算設(shè)計(jì)的索引，它通過(guò)OID將滿足謂詞條件的對(duì)象映射到Inverted-Object-Index的“key”上，輔助Inverted-Object-Index過(guò)濾不滿足條件的對(duì)象。Predicate-Index是一個(gè)存儲(chǔ)（predicate,result）對(duì)集合的索引結(jié)構(gòu)，其中鍵值“predi?cate”表示謂詞條件，而“result”（結(jié)果集）是一組滿足“predicate”的對(duì)象。Predicate-Index包含一個(gè)構(gòu)建在“predicate”上的B-Tree索引，葉子節(jié)點(diǎn)的索引項(xiàng)指針指向?qū)?yīng)結(jié)果集（即“result”）。

4.2 索引的創(chuàng)建

算法1和算法2描述了IPI創(chuàng)建的過(guò)程，包括Inverted-Object-Index和Predicate-Index。

算法1Inverted-Object-Index的創(chuàng)建

算法1描述了Inverted-Object-Index的創(chuàng)建過(guò)程，目標(biāo)類的每個(gè)對(duì)象對(duì)應(yīng)其一個(gè)索引項(xiàng)，包括鍵值和對(duì)象列表。需要順序掃描目標(biāo)類的對(duì)象，對(duì)每個(gè)對(duì)象進(jìn)行如下操作（第2到3行代碼）：根據(jù)OID填充鍵值，再把所有與鍵值存在代理關(guān)系的對(duì)象以“類OID:對(duì)象OID”的形式存入對(duì)象列表。目標(biāo)類掃描完畢后，其Inverted-Object-Index也創(chuàng)建完成。

算法2Predicate-Index的創(chuàng)建

算法2描述了Predicate-Index中一個(gè)索引項(xiàng)的創(chuàng)建過(guò)程，每個(gè)謂詞條件對(duì)應(yīng)一個(gè)索引項(xiàng)，包括鍵值和結(jié)果集。第2行代碼根據(jù)謂詞條件填充鍵值。結(jié)果集包含所有滿足鍵值的對(duì)象，需要順序掃描目標(biāo)類的對(duì)象把滿足條件的OID存入結(jié)果集（第3到7行代碼）。Predicate-Index沒(méi)有規(guī)定行數(shù)，可為空，按查詢需求把頻繁查詢的謂詞條件創(chuàng)建完畢即可。

4.3 索引的使用

創(chuàng)建完IPI索引，接下來(lái)介紹使用該索引計(jì)算PE的IPI索引方法。對(duì)于一個(gè)給定PE，使用IPI計(jì)算的流程按如下步驟進(jìn)行：

（1）進(jìn)行謂詞條件檢查和PE劃分。首先需要判斷PE是否帶謂詞條件。如果PE帶謂詞條件，就把PE按謂詞條件所在類進(jìn)行劃分；否則就直接在起點(diǎn)類的Inverted-Object-Index中進(jìn)行路徑匹配。

（2）謂詞條件計(jì)算。為了計(jì)算定義于某特定類Ci的謂詞條件pred，首先需要在predicCi中掃描pred，若找到了，就把對(duì)應(yīng)的結(jié)果集保存在該類的一個(gè)臨時(shí)的謂詞條件結(jié)果集prCi()；否則，需要重新掃描classCi，把滿足pred的對(duì)象OID加入prCi()。

（3）路徑匹配。若PE帶謂詞條件，就依次從prCi()中獲取OID，分別找到它們?cè)趇nvertCi中對(duì)應(yīng)的索引項(xiàng)。對(duì)每個(gè)索引項(xiàng)，判斷其對(duì)象列表中是否包括了PE的所有類，若是則說(shuō)明該索引項(xiàng)能夠匹配路徑，獲取對(duì)象列表中終點(diǎn)對(duì)象OID，加入該類的一個(gè)臨時(shí)的終點(diǎn)對(duì)象集resCi()。若PE不帶謂詞條件，則順序掃描起點(diǎn)類的Inverted-Object-Index，對(duì)其每個(gè)索引項(xiàng)的操作和帶謂詞條件的情況相同。

（4）合并結(jié)果。若PE帶謂詞條件，取所有非空resCi()(1≤i≤n)的交集為最終終點(diǎn)對(duì)象集；否則起點(diǎn)類終點(diǎn)對(duì)象集resC1()即最終終點(diǎn)對(duì)象集。

（5）根據(jù)目標(biāo)表達(dá)式對(duì)最終終點(diǎn)對(duì)象集進(jìn)行投影運(yùn)算得到并返回結(jié)果對(duì)象。

4.4 索引的維護(hù)

IPI和傳統(tǒng)索引一樣依賴于數(shù)據(jù)庫(kù)建立。若數(shù)據(jù)庫(kù)被修改，IPI也需要被維護(hù)。數(shù)據(jù)庫(kù)可能的修改包括：創(chuàng)建對(duì)象和類，刪除對(duì)象和類以及修改對(duì)象的屬性值。由于創(chuàng)建/刪除一個(gè)類相當(dāng)于插入/刪除該類包含的多個(gè)對(duì)象，本節(jié)主要介紹針對(duì)插入/刪除對(duì)象操作和修改對(duì)象屬性值操作的IPI索引維護(hù)。為方便討論維護(hù)時(shí)間的復(fù)雜度，假設(shè)invertCi的平均索引項(xiàng)數(shù)目為n，predicCi的平均索引項(xiàng)數(shù)目為m，m＜＜n。

（1）插入/刪除對(duì)象。當(dāng)一個(gè)對(duì)象oi被插入/刪除需要維護(hù)3處：①在invertCi中添加/刪除記錄oi；②在predicCi中找到oi所滿足的謂詞條件，分別在對(duì)應(yīng)結(jié)果集中添加/刪除記錄oi；③對(duì)所有與oi存在代理關(guān)系的對(duì)象（假設(shè)數(shù)目為常數(shù)k），在其各自Inverted-Object-Index對(duì)應(yīng)索引項(xiàng)的對(duì)象列表中添加/刪除記錄oi。其中，①相當(dāng)于在invertCi二叉樹(shù)中查找目標(biāo)對(duì)象，平均維護(hù)時(shí)間為lbn+1；②相當(dāng)于順序查找不定量的謂詞條件，平均維護(hù)時(shí)間為m+m/2；③同①，相當(dāng)于在k個(gè)二叉樹(shù)中分別查找目標(biāo)對(duì)象，平均維護(hù)時(shí)間為k×(lbn+1)。綜上該操作的維護(hù)時(shí)間如式（5）所示，時(shí)間復(fù)雜度為O(lbn)。

（2）修改對(duì)象的屬性值。對(duì)象屬性值的修改不改變對(duì)象間的雙向指針，因此invertCi不需要被維護(hù)。當(dāng)一個(gè)對(duì)象oi的屬性值被修改可能導(dǎo)致兩種情況：①一個(gè)對(duì)象修改前不滿足某謂詞條件但修改后滿足；②一個(gè)對(duì)象修改前滿足某謂詞條件但修改后不滿足。它們都會(huì)影響predicCi，具體維護(hù)操作如下：首先在predicCi中掃描定義于該屬性的謂詞條件，重新判斷oi是否滿足這些謂詞條件，然后根據(jù)判斷結(jié)果在它們的結(jié)果集中添加/刪除oi的記錄。同（1）操作中的②，該操作的維護(hù)時(shí)間T(n)=1.5m，時(shí)間復(fù)雜度為O(1)。

插入/刪除對(duì)象的操作需維護(hù)同一類網(wǎng)中大多類的Inverted-Object-Index和被修改類的Predicate-Index；而修改對(duì)象屬性值的操作也需要維護(hù)被修改類的Predicate-Index。執(zhí)行多次的單步維護(hù)操作可能導(dǎo)致冗余維護(hù)，降低了維護(hù)效率。因此，設(shè)計(jì)了op_update（表2）和op_maintain（表3）兩個(gè)系統(tǒng)表來(lái)支持批量維護(hù)操作。系統(tǒng)表op_update存儲(chǔ)對(duì)數(shù)據(jù)庫(kù)的修改操作，op_maintain存儲(chǔ)由修改操作轉(zhuǎn)換而成的針對(duì)各個(gè)類的維護(hù)指令。批量維護(hù)操作并不是當(dāng)數(shù)據(jù)庫(kù)被修改一次就立即維護(hù)IPI，而是將修改操作存入系統(tǒng)表op_update中，當(dāng)操作數(shù)超過(guò)一定閾值或所有修改操作都已讀入時(shí)，就根據(jù)緩存的修改操作來(lái)維護(hù)IPI，具體維護(hù)步驟如下：

首先，對(duì)系統(tǒng)表op_update中所有操作進(jìn)行抵消和合并，該功能由記錄修改操作執(zhí)行時(shí)間的time來(lái)支持：（1）若一個(gè)插入操作和一個(gè)刪除操作作用于同一對(duì)象，且前者執(zhí)行時(shí)間比后者早，即插入一個(gè)對(duì)象后再將它刪除，那么這兩個(gè)操作的作用會(huì)相互抵消。在該情況下，這兩個(gè)操作會(huì)被清除。（2）若有兩個(gè)或兩個(gè)以上的屬性值修改操作對(duì)同一對(duì)象的同一屬性先后進(jìn)行修改，那么執(zhí)行時(shí)間最晚的一個(gè)修改操作就會(huì)覆蓋先前的。在該情況下，這些修改操作會(huì)被合并為時(shí)間最新的一條屬性值修改操作。

Table 2 Attributes of op_update表2 系統(tǒng)表op_update的屬性

接下來(lái)，把系統(tǒng)表op_update中的操作轉(zhuǎn)換成以類為單位的維護(hù)指令，填充到系統(tǒng)表op_maintain中。如表3所示，opindex決定具體要對(duì)哪部分索引進(jìn)行維護(hù)。若optype為3，則opindex只能取2，因?qū)傩灾敌薷臅r(shí)不需要維護(hù)Inverted-Object-Index，此時(shí)position表示被修改屬性的列號(hào)，value表示修改后的屬性值。屬性position的另一作用是當(dāng)optype為1或2，opindex為1時(shí)，表示維護(hù)操作作用的對(duì)象，分為兩種情況：（1）position等于opoid，即維護(hù)的是被修改對(duì)象本身，相當(dāng)于插入/刪除對(duì)象時(shí)維護(hù)的第i點(diǎn)。（2）position表示所屬于classoid并且與opoid存在代理關(guān)系的對(duì)象，相當(dāng)于插入/刪除對(duì)象時(shí)維護(hù)的第③點(diǎn)。在第（1）種情況中，構(gòu)建插入對(duì)象在Inverted-Object-Index的索引項(xiàng)時(shí)需要對(duì)象列表的信息，由表3的value屬性給出：如果opoid有源對(duì)象，value值就是其源對(duì)象的OID與源對(duì)象的對(duì)象列表的并集；否則，value值為空。

Table 3 Attributes of op_maintain表3 系統(tǒng)表op_maintain的屬性

最后，根據(jù)屬性classoid把系統(tǒng)表op_maintain中的維護(hù)指令劃分到對(duì)應(yīng)類，逐個(gè)類進(jìn)行索引維護(hù)。當(dāng)op_maintain系統(tǒng)表中的所有維護(hù)指令執(zhí)行完畢，一次批量維護(hù)操作也就完成了。

5 IPI的靈活性討論

第2章提到目前針對(duì)ODDB中PE的索引結(jié)構(gòu)（ODPI[14]、PNI[15]）都存在一個(gè)嚴(yán)重問(wèn)題，即缺乏靈活性。由于ODPI的核心思想與PNI類似，且謂詞條件計(jì)算受限制，因此本文沒(méi)有把ODPI作為對(duì)比索引（下同）。本文通過(guò)對(duì)比IPI和PNI從以下兩方面來(lái)說(shuō)明IPI在靈活性方面的優(yōu)勢(shì)：

（1）使用IPI能以較少的索引支持更全面的路徑覆蓋。假設(shè)一個(gè)類網(wǎng)有n個(gè)類，就有n×(n-1)條路徑。由于正逆路徑共用同一個(gè)PNI，覆蓋全部路徑需要n×(n-1)/2個(gè)PNI；而對(duì)于IPI，覆蓋全部路徑只需要對(duì)每個(gè)類建立索引，即n個(gè)IPI。顯然，O(n)在復(fù)雜度上遠(yuǎn)小于O(n2)。如果PNI僅建立和IPI同樣數(shù)目的索引，即只對(duì)n條路徑建立PNI，那么此時(shí)PNI的路徑覆蓋率如式（6）所示。隨著n的增加，其路徑覆蓋率會(huì)越來(lái)越小。因此，在大多情況下，需要更多的PNI才能維持和IPI同樣的需求，并且類網(wǎng)的數(shù)據(jù)規(guī)模越大，IPI的優(yōu)勢(shì)越明顯。

（2）使用IPI能更好地適應(yīng)需求變化。以圖1的教學(xué)管理數(shù)據(jù)庫(kù)模式為例，假設(shè)使用者是學(xué)生，可能的查詢需求有：查詢課程信息，查詢自己某門課程的績(jī)點(diǎn)等等，分別對(duì)應(yīng)如下的路徑：Student→Cou_Stu→Course,Student→Cou_Stu→Stu_Grade。要維持此時(shí)的需求，可以對(duì)每個(gè)類建立IPI或?qū)γ織l頻繁查詢的路徑建立PNI。若以后該數(shù)據(jù)庫(kù)的使用者變?yōu)榻處?，查詢需求則可能有：查詢課程信息，查詢自己的職稱等，分別對(duì)應(yīng)如下的路徑：Teacher→Tea_Eva→Course,Teacher→Tea_Eva。此時(shí)原先建立的PNI對(duì)新的查詢無(wú)效，而IPI索引方法則可以提供任意路徑的查詢。當(dāng)然上述例子也許過(guò)于極端，但能說(shuō)明PNI難以適應(yīng)需求變化的問(wèn)題。

綜上，由于一個(gè)類網(wǎng)中類的數(shù)目遠(yuǎn)小于路徑數(shù)，IPI對(duì)每個(gè)類建就能覆蓋全部路徑，并能適應(yīng)應(yīng)用需求的變化。與PNI相比，IPI能以更少的索引數(shù)量滿足需求，對(duì)需求變化的適應(yīng)性也更好。

6 實(shí)驗(yàn)

本文把IPI索引方法分別與PT[14-15]（即不使用索引）和PNI[15]索引方法進(jìn)行對(duì)比。通過(guò)實(shí)驗(yàn)證明IPI索引方法的有效性。所有實(shí)驗(yàn)都在ODDB系統(tǒng)Totem[7]中完成。

實(shí)驗(yàn)使用的測(cè)試環(huán)境是一臺(tái)PC機(jī)，其配置如下：Intel?CoreTMi5-2320 3.0 GHz CPU，4 GB內(nèi)存容量，500 GB硬盤，Ubuntu 16.04操作系統(tǒng)，Totem 2.0數(shù)據(jù)庫(kù)系統(tǒng)。實(shí)驗(yàn)采用一個(gè)教學(xué)管理數(shù)據(jù)庫(kù)為測(cè)試數(shù)據(jù)庫(kù)（數(shù)據(jù)庫(kù)模式如圖1所示），不同規(guī)模的數(shù)據(jù)集（DS1～DS6，表4）為測(cè)試數(shù)據(jù)集。在表4中，每個(gè)單元格的數(shù)據(jù)表示不同數(shù)據(jù)集中每個(gè)類的對(duì)象數(shù)目。

Table 4 Test data sets表4 測(cè)試數(shù)據(jù)集

實(shí)驗(yàn)結(jié)果表明使用IPI得到的結(jié)果和不使用索引的完全相同，即IPI的有效性得到證明。下面實(shí)驗(yàn)將分析路徑長(zhǎng)度和謂詞條件對(duì)計(jì)算效率的影響，以及IPI創(chuàng)建時(shí)間和存儲(chǔ)空間的影響因素，并討論索引維護(hù)時(shí)間、效率以及靈活性之間的權(quán)衡。

6.1 路徑長(zhǎng)度對(duì)PE計(jì)算的影響

第一組實(shí)驗(yàn)在不考慮謂詞條件的情況下，分別以路徑長(zhǎng)度為3和5的PE為測(cè)試用例，測(cè)試不同數(shù)據(jù)規(guī)模下各個(gè)方法的執(zhí)行時(shí)間。由圖3可以看出，3種方法的執(zhí)行時(shí)間都是隨著路徑長(zhǎng)度的增加而增長(zhǎng)。它們?cè)谟?jì)算過(guò)程中都依賴于路徑：IPI需要判斷是否匹配路徑中的所有類；PT是沿著路徑依次獲取每個(gè)類滿足條件的對(duì)象實(shí)例；PNI則是直接建立于固定的路徑上。整體實(shí)驗(yàn)結(jié)果表明，3種方法中PT效率最差，這是因?yàn)樗枰粩啻嫒≈虚g路徑上的對(duì)象實(shí)例，頻繁的I/O操作導(dǎo)致總的時(shí)間開(kāi)銷較大。IPI的效率比PNI略差一些，因?yàn)镮PI在獲取終點(diǎn)對(duì)象前比PNI多一步操作，即判斷對(duì)象是否匹配路徑。但該操作消耗的時(shí)間占整個(gè)計(jì)算時(shí)間的比重很小，因此二者的效率相差無(wú)幾。

6.2 謂詞條件對(duì)PE計(jì)算的影響

第二組實(shí)驗(yàn)在不考慮路徑長(zhǎng)度的情況下，分別以帶1個(gè)和2個(gè)謂詞條件的PE為測(cè)試用例，測(cè)試不同數(shù)據(jù)規(guī)模下各方法的執(zhí)行時(shí)間。由圖4可以看出，IPI和PNI的執(zhí)行時(shí)間隨謂詞條件數(shù)目的增加而增長(zhǎng)，而PT則無(wú)明顯變化。因?yàn)镻T是在遍歷路徑的同時(shí)判斷謂詞條件。一旦發(fā)現(xiàn)對(duì)象實(shí)例不滿足謂詞條件，就會(huì)提前中止該趟計(jì)算流程，因此更多的謂詞條件對(duì)PT的執(zhí)行時(shí)間影響不大，反而可能節(jié)省一些不必要的對(duì)象遍歷時(shí)間。與之相反，IPI和PNI索引方法都以謂詞條件為單位進(jìn)行計(jì)算，因此謂詞條件的數(shù)目和它們的執(zhí)行時(shí)間成正比。

6.3 IPI索引的創(chuàng)建時(shí)間

Fig.3 Influence of path length on PE evaluation圖3 路徑長(zhǎng)度對(duì)PE計(jì)算的影響

第三組實(shí)驗(yàn)以教學(xué)管理數(shù)據(jù)庫(kù)模式（圖1）的Student類為例，得到不同數(shù)據(jù)規(guī)模下Student類的IPI創(chuàng)建時(shí)間（Inverted-Object-Index和Predicate-Index）。由圖5可以看出，Inverted-Object-Index和Predicate-Index的創(chuàng)建時(shí)間隨著數(shù)據(jù)規(guī)模的增大而增長(zhǎng)。二者在創(chuàng)建過(guò)程中都需要掃描其所在類的對(duì)象，數(shù)據(jù)規(guī)模越大，創(chuàng)建時(shí)間也越長(zhǎng)。此外，因?yàn)镻redicate-Index的每個(gè)索引項(xiàng)對(duì)應(yīng)一個(gè)謂詞條件，所以謂詞條件的數(shù)目是Predicate-Index創(chuàng)建時(shí)間的另一影響因素。如圖5（b）所示，謂詞條件越多，Predicate-Index的創(chuàng)建時(shí)間越長(zhǎng)。

6.4 IPI索引的存儲(chǔ)空間開(kāi)銷

第四組實(shí)驗(yàn)以教學(xué)管理數(shù)據(jù)庫(kù)模式（圖1）的Stu?dent類為例，得到不同數(shù)據(jù)規(guī)模下Student類的IPI存儲(chǔ)開(kāi)銷（Inverted-Object-Index和 Predicate-Index）。由圖6可看出，IPI的存儲(chǔ)空間隨數(shù)據(jù)規(guī)模的增大而增長(zhǎng)。因Inverted-Object-Index的每個(gè)索引項(xiàng)對(duì)應(yīng)其所在類的一個(gè)對(duì)象，顯然Inverted-Object-Index的存儲(chǔ)空間和數(shù)據(jù)規(guī)模成正比。對(duì)非空的Predicate-Index，每條記錄的結(jié)果集規(guī)模越大，所占用的存儲(chǔ)空間就越大。

6.5 IPI索引的維護(hù)時(shí)間與效率討論

由圖3和圖4可以看出，使用IPI比不使用IPI（即PT）節(jié)省的時(shí)間隨數(shù)據(jù)集的增大呈拋物線增長(zhǎng)，其復(fù)雜度約為O(n2)。第4.4節(jié)討論到IPI單次維護(hù)時(shí)間的復(fù)雜度最多是O(lbn)，維護(hù)時(shí)間代價(jià)遠(yuǎn)小于使用IPI節(jié)省的時(shí)間。因此，IPI以較小的維護(hù)時(shí)間代價(jià)換取較大的效率提升是值得的。

Fig.4 Influence of predicates on PE evaluation圖4 謂詞條件對(duì)PE計(jì)算的影響

Fig.5 Creation time of IPI圖5 IPI的創(chuàng)建時(shí)間開(kāi)銷

Fig.6 Storage space of IPI圖6 IPI的存儲(chǔ)空間開(kāi)銷

6.6 IPI索引的效率與靈活性討論

由圖3和圖4可以看出，IPI整體效率比PNI略差一些，相差的時(shí)間平均約占IPI執(zhí)行查詢時(shí)間的5%，數(shù)據(jù)規(guī)模越大，其所占比重越小。第5章討論到要覆蓋某類網(wǎng)的全部路徑，IPI需要的索引數(shù)目遠(yuǎn)小于PNI，且數(shù)據(jù)規(guī)模越大，兩者數(shù)目相差越大。因此，對(duì)于比較大的數(shù)據(jù)規(guī)模，IPI以比較小的效率代價(jià)換取較大的靈活性是值得的。

7 結(jié)論和展望

作為ODDB的主要查詢功能之一，跨類查詢由PE實(shí)現(xiàn)，故PE的計(jì)算效率對(duì)ODDB的性能有顯著影響?，F(xiàn)有的一些針對(duì)ODDB跨類查詢的索引結(jié)構(gòu)（ODPI[14]、PNI[15]）都局限于固定的路徑，缺乏靈活性。在此背景下，本文提出一種新的索引結(jié)構(gòu)——倒排路徑索引（IPI），使ODDB跨類查詢具備靈活高效的查詢性能。IPI索引物化了對(duì)象間的代理關(guān)系，并利用對(duì)象關(guān)聯(lián)檢索技術(shù)輔助進(jìn)行謂詞條件計(jì)算。物化的對(duì)象代理關(guān)系可以靈活覆蓋所有路徑實(shí)例，并減少計(jì)算中對(duì)象遍歷的開(kāi)銷；對(duì)象關(guān)聯(lián)檢索能過(guò)濾不滿足條件的代理關(guān)系，以輔助計(jì)算謂詞條件。本文通過(guò)實(shí)驗(yàn)對(duì)影響PE計(jì)算的各種因素進(jìn)行研究，分析了路徑長(zhǎng)度和謂詞條件對(duì)計(jì)算效率的影響。實(shí)驗(yàn)結(jié)果表明IPI索引方法能以不低于現(xiàn)有方法的效率支持更加靈活的PE計(jì)算。

IPI索引方法仍有一些不足。與PT[14-15]相比，建立IPI需要消耗存儲(chǔ)空間，并且隨數(shù)據(jù)庫(kù)的變化需要頻繁地維護(hù)IPI索引。因此，如何減少IPI的存儲(chǔ)占用和維護(hù)時(shí)間是下一步的工作。