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

武漢大學 計算機學院，武漢 430072

1 引言

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

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

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

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

2 相關(guān)工作

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

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

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

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

3 基本概念

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

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

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

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

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

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

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

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

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

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

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

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

Table 1 Symbol table表1 符號表

4 倒排路徑索引IPI

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

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

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

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

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

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

4.2 索引的創(chuàng)建

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

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

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

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

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

4.3 索引的使用

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

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

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

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

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

（5）根據(jù)目標表達式對最終終點對象集進行投影運算得到并返回結(jié)果對象。

4.4 索引的維護

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

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

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

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

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

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

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

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

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

5 IPI的靈活性討論

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

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

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

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

6 實驗

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

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

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

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

6.1 路徑長度對PE計算的影響

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

6.2 謂詞條件對PE計算的影響

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

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

Fig.3 Influence of path length on PE evaluation圖3 路徑長度對PE計算的影響

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

6.4 IPI索引的存儲空間開銷

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

6.5 IPI索引的維護時間與效率討論

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

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

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

Fig.6 Storage space of IPI圖6 IPI的存儲空間開銷

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

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

7 結(jié)論和展望

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

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