一種基于XML數(shù)據(jù)的高效路徑索引方法

1.?一種基于XML數(shù)據(jù)的高效路徑索引方法，其特征是通過構(gòu)建UD(k，l)索引圖，用于 執(zhí)行路徑表達(dá)式或執(zhí)行分支路徑表達(dá)式進(jìn)行查詢，具體步驟為：對(duì)源XML文檔構(gòu)建UD(k，l) 索引，將預(yù)期的向上相似度k和向下相似度l作為輸入，建立好的UD(k，l)文檔作為輸出，第 一步，對(duì)所有的數(shù)據(jù)節(jié)點(diǎn)按其標(biāo)簽進(jìn)行分類，得到一個(gè)節(jié)點(diǎn)集列表，每一個(gè)節(jié)點(diǎn)集都有一個(gè) 唯一的標(biāo)簽；然后計(jì)算每個(gè)節(jié)點(diǎn)集的向上相似度，反復(fù)分裂具有最小向上相似度的節(jié)點(diǎn)集， 直到所有節(jié)點(diǎn)集中最小的向上相似度ub不小于給定的參數(shù)k；然后，計(jì)算每個(gè)節(jié)點(diǎn)集的向下 相似度，同樣反復(fù)分裂節(jié)點(diǎn)直到所有節(jié)點(diǎn)集中最小的向下相似度db不小于給定的參數(shù)l；第 二步是建立索引節(jié)點(diǎn)及連接索引節(jié)點(diǎn)的邊：首先對(duì)每個(gè)節(jié)點(diǎn)集建立一個(gè)索引節(jié)點(diǎn)；對(duì)于XML 數(shù)據(jù)圖中任意兩個(gè)有邊相連的頂點(diǎn)u和頂點(diǎn)v，如果索引節(jié)點(diǎn)A和索引節(jié)點(diǎn)B之間沒有邊的 話，就添加上一條邊，這里節(jié)點(diǎn)A對(duì)應(yīng)的節(jié)點(diǎn)集包含u，節(jié)點(diǎn)B的對(duì)應(yīng)節(jié)點(diǎn)集包含v。
2.?根據(jù)權(quán)利要求1所述的索引方法，其特征在于利用構(gòu)建好的UD(k，l)索引圖執(zhí)行帶 分支路徑表達(dá)式，是將路徑表達(dá)式用確定有限自動(dòng)機(jī)表示，將索引數(shù)據(jù)作為確定有限自動(dòng)機(jī) 的輸入，運(yùn)行確定有限自動(dòng)機(jī)來找到那些可以驅(qū)動(dòng)確定有限自動(dòng)機(jī)到達(dá)最終狀態(tài)的節(jié)點(diǎn)。
3.?根據(jù)權(quán)利要求1所述的索引方法，其特征在于在UD(k，l)索引圖上執(zhí)行帶分支的路 徑i表達(dá)式查詢步驟如下：為帶分支路徑表達(dá)式的主路徑構(gòu)造確定有限自動(dòng)機(jī)A0，并為每個(gè) 條件路徑i構(gòu)造確定有限自動(dòng)機(jī)Ai；接著在索引圖上運(yùn)行A0，對(duì)索引進(jìn)行深度優(yōu)先遍歷，A0 根據(jù)匹配的節(jié)點(diǎn)自動(dòng)進(jìn)行狀態(tài)轉(zhuǎn)換，并為分支節(jié)點(diǎn)建立一張表來記錄它們的中間結(jié)果；當(dāng)A0 到達(dá)一個(gè)分支節(jié)點(diǎn)時(shí)，暫停其執(zhí)行，根據(jù)條件路徑i啟動(dòng)相應(yīng)的Ai；當(dāng)Ai到達(dá)最終狀態(tài)時(shí)， 停止Ai，驗(yàn)證A0停留的那個(gè)索引節(jié)點(diǎn)對(duì)應(yīng)的節(jié)點(diǎn)集，然后在中間結(jié)果表中存儲(chǔ)經(jīng)驗(yàn)證正確的 節(jié)點(diǎn)，之后繼續(xù)執(zhí)行A0；如果Ai不能到達(dá)最終狀態(tài)，A0就不能繼續(xù)往前執(zhí)行，而是要先返回 它的前一個(gè)狀態(tài)，再往下執(zhí)行；當(dāng)A0到達(dá)最終狀態(tài)時(shí)，索引圖到達(dá)某個(gè)節(jié)點(diǎn)，對(duì)這個(gè)索引的 節(jié)點(diǎn)集進(jìn)行確認(rèn)，將確認(rèn)正確的結(jié)果添加到最終結(jié)果集中。
4.?根據(jù)權(quán)利要求1所述的索引方法，其特征在于當(dāng)原文檔的數(shù)據(jù)發(fā)生變化時(shí)，對(duì)UD(k， l)索引作出增量式維護(hù)，具體操作方法如下：如果更新操作是在原文檔中節(jié)點(diǎn)θ的位置插入 一個(gè)節(jié)點(diǎn)δ，則首先分裂和重組在θ上方和θ距離為l的節(jié)點(diǎn)，然后找到合適的索引節(jié)點(diǎn)位置 插入節(jié)點(diǎn)δ；如果更新操作是在節(jié)點(diǎn)γ上插入一個(gè)子樹T，則用深度優(yōu)先的方法遍歷子樹T， 依次插入每一個(gè)節(jié)點(diǎn)；如果更新操作是刪除位于節(jié)點(diǎn)γ的一個(gè)子樹T，則首先從對(duì)應(yīng)的索引 節(jié)點(diǎn)中移去子樹T中的所有索引節(jié)點(diǎn)，然后對(duì)節(jié)點(diǎn)γ上方和γ距離為l的節(jié)點(diǎn)進(jìn)行分裂和重組。

技術(shù)領(lǐng)域\n本發(fā)明屬數(shù)據(jù)庫技術(shù)領(lǐng)域，具體涉及一種新穎高效的對(duì)XML數(shù)據(jù)進(jìn)行索引的方法。\n背景技術(shù)\n近年來，XML(可擴(kuò)展標(biāo)記語言)已經(jīng)成為因特網(wǎng)上數(shù)據(jù)分發(fā)和交換的主要標(biāo)準(zhǔn)。隨 著XML文檔的大量出現(xiàn)，針對(duì)XML數(shù)據(jù)的查詢也得到了人們?cè)絹碓蕉嗟年P(guān)注。各種各樣 的查詢語言紛紛被提出。其中，執(zhí)行路徑表達(dá)式是XML查詢的重要方面。最簡(jiǎn)單路徑表 達(dá)式的執(zhí)行方法是直接在整個(gè)XML文檔上進(jìn)行詳盡的查找，這顯然是很低效的。路徑索 引通過將查找限制在僅與查詢有關(guān)的XML部分文檔上來提高路徑表達(dá)式的執(zhí)行效率。因 此，如何從半結(jié)構(gòu)化數(shù)據(jù)中抽取路徑索引結(jié)構(gòu)近來被廣泛關(guān)注。\n已提出的路徑索引結(jié)構(gòu)有DataGuide，1-index，F(xiàn)abric索引和A(k)索引等。DataGuide 及其后續(xù)工作提出的方法是建立一個(gè)帶標(biāo)簽的有向圖形式的結(jié)構(gòu)摘要。意圖是用盡可能少 的節(jié)點(diǎn)和邊來保存數(shù)據(jù)圖中所有的路徑信息。然而，這種類型的索引大小甚至是原始數(shù)據(jù) 的幾倍。這是因?yàn)樗鼈兪蔷_索引：從XML數(shù)據(jù)的根節(jié)點(diǎn)開始，所有的路徑包括那些極 少用到的很長的路徑都被記錄了下來，而且在DataGuide中，每個(gè)數(shù)據(jù)節(jié)點(diǎn)出現(xiàn)的機(jī)會(huì)可 能不止一次。A(k)索引通過考慮數(shù)據(jù)節(jié)點(diǎn)的局部近似度來降低索引大小，所以能夠有效的 支持簡(jiǎn)單(無分支)路徑查詢。可是它僅僅考慮了節(jié)點(diǎn)的向上相似度而忽視了它們的向下 相似度。所以這種節(jié)點(diǎn)在處理帶分支路徑查詢時(shí)是低效的。\n發(fā)明內(nèi)容\n本發(fā)明的目的在于提出了一種基于XML數(shù)據(jù)的高效的索引方法，該方法引入了叫做 UD(k，l)的新型近似索引結(jié)構(gòu)來高效執(zhí)行路徑表達(dá)式，尤其是帶分支的路徑表達(dá)式。\n本發(fā)明全面利用了XML數(shù)據(jù)節(jié)點(diǎn)的向上局部相似度和向下局部相似度的信息，雖然 索引的存儲(chǔ)空間比A(k)索引略大一些，但在處理帶分支的路徑表達(dá)式時(shí)比A(k)索引和 1-index都要快得多。\n1.與本發(fā)明有關(guān)的一些概念和定義。\n【1】XML文檔：\n本發(fā)明中，XML文檔被模式化為一個(gè)有向標(biāo)簽圖G＝(VG，EG，∑G，lab，oid，val，root)， 叫做XML數(shù)據(jù)圖。這里，VG是節(jié)點(diǎn)的集合，EG是邊的集合，其中每條邊表示一個(gè)元素的 父子關(guān)系或者元素-數(shù)值關(guān)系。∑G是XML文檔中所有標(biāo)簽的集合。lab，oid和val是三種 映射函數(shù)，lab是映射VG中的一個(gè)節(jié)點(diǎn)到∑G中的一個(gè)標(biāo)簽的函數(shù)，oid是映射VG中的一個(gè) 節(jié)點(diǎn)到一個(gè)唯一標(biāo)示符的函數(shù)，而val則是映射數(shù)據(jù)值到一個(gè)沒有輸出邊的葉子節(jié)點(diǎn)上。 最后root是VG中標(biāo)記為ROOT的唯一的根節(jié)點(diǎn)。\n圖1是用XML數(shù)據(jù)圖的方式顯示了英格蘭頂級(jí)足球聯(lián)盟的部分信息。節(jié)點(diǎn)中的數(shù)字 代表oid。實(shí)心線代表元素間的父子關(guān)系。XML圖中的葉子元素有數(shù)據(jù)值。虛線邊表示元 素間的一般性鏈接。\n【2】標(biāo)簽路徑和節(jié)點(diǎn)路徑：\n一條標(biāo)簽路徑表示由分割符“/”分開的一系列的標(biāo)簽l1...lp(p≥1)。一條數(shù)據(jù)路徑則表 示由分割符“/”分開的一系列的節(jié)點(diǎn)n1...np(p≥1)，并且對(duì)于1≤i＜p，ni是ni+1的父節(jié)點(diǎn)。\n【3】正則路徑表達(dá)式：\n由分隔符“/”、二分符“|”循環(huán)符“*”和替代符“？”來定義基本正則路徑表達(dá)式R， 如下所示：R::＝ε|l|_|R/R|R|R|(R)|R？|R*。這里，l∈EG，‘_’是一個(gè)能匹配EG中 任意一個(gè)標(biāo)簽的特殊符號(hào)。\n進(jìn)一步，可以定義帶分支的路徑表達(dá)式，如下所示：BR::＝R[R]|R/BR|BR/BR|BR/R。 這里R是一個(gè)基本正則路徑表達(dá)式。對(duì)于帶分支的路徑表達(dá)式R1[R2]來說，分支路徑出現(xiàn) 在路徑R1的最后一個(gè)標(biāo)簽上。這個(gè)標(biāo)簽被稱為分支點(diǎn)。一個(gè)帶分支的路徑表達(dá)式由一條主 路徑和若干條條件路徑這兩種路徑構(gòu)成。主路徑是指去掉帶分支的路徑表達(dá)式中的所有中 括號(hào)括起來的部分(包括中括號(hào)本身)后得到的路徑表達(dá)式，而一條條件路徑則是指一個(gè) 中括號(hào)括起來的那部分路徑。不帶任何分支點(diǎn)的路徑表達(dá)式稱為簡(jiǎn)單路徑表達(dá)式。\n【4】相似關(guān)系和相似度：\n我們把VG上的一種對(duì)稱的二元關(guān)系≈u稱為向上相似關(guān)系，對(duì)于任意兩個(gè)數(shù)據(jù)節(jié)點(diǎn)u 和v，如果他們存在關(guān)系u≈uv，則有a)u和v有著相同的標(biāo)簽，并且有b)對(duì)于u的任一 個(gè)子節(jié)點(diǎn)u’，存在v的一個(gè)子節(jié)點(diǎn)v’，使得u’≈uv’，反之亦然。G中的兩個(gè)節(jié)點(diǎn)u和v之 間如果存在關(guān)系u≈uv，我們就說這兩個(gè)節(jié)點(diǎn)是向上相似的。\n我們把VG上的一種對(duì)稱的二元關(guān)系≈d稱為向下相似關(guān)系，對(duì)于任意兩個(gè)數(shù)據(jù)節(jié)點(diǎn)u 和v，如果他們存在關(guān)系u≈dv，則有a)u和v有著相同的標(biāo)簽，并且有b)對(duì)于u的任一 個(gè)子節(jié)點(diǎn)u’，存在v的一個(gè)子節(jié)點(diǎn)v’，使得u’≈dv’，反之亦然。G中的兩個(gè)節(jié)點(diǎn)u和v之 間如果存在關(guān)系u≈dv，我們就說這兩個(gè)節(jié)點(diǎn)是向下相似的。\n如果一個(gè)對(duì)稱二元關(guān)系既是向上相似關(guān)系也是向下相似關(guān)系，我們就稱它為上下相似 關(guān)系，記為≈d u。如果G中的兩個(gè)節(jié)點(diǎn)u和v既是向上相似的，也是向下相似的，則稱它們 是上下相似的。\n≈l k(k-l-相似度)須符合以下三個(gè)條件a)對(duì)于任意兩個(gè)節(jié)點(diǎn)u和v，$u{\approx }_0^{0}v$當(dāng)且僅當(dāng)u 和v具有相同的標(biāo)簽；b)$u{\approx }_l^{k}v$當(dāng)且僅當(dāng)$u{\approx }_l^{0}v$并且對(duì)于節(jié)點(diǎn)u的任一個(gè)父節(jié)點(diǎn)u’，存在節(jié) 點(diǎn)v的一個(gè)父節(jié)點(diǎn)v’使得$u^{,}{\approx }_l^{k-1}{v}^{,},$反之亦然；c)$u{\approx }_l^{k}v$當(dāng)且僅當(dāng)$u{\approx }_0^{k}v$并且對(duì)于節(jié)點(diǎn)u 的任一個(gè)子節(jié)點(diǎn)u’，存在節(jié)點(diǎn)v的一個(gè)子節(jié)點(diǎn)v’使得$u^{,}{\approx }_{l-1}^k{v}^{,},$反之亦然。\n【5】UD(k，l)索引結(jié)構(gòu)及其構(gòu)建\nUD(k，l)索引根據(jù)節(jié)點(diǎn)的長度為k的輸入路徑和長度為l的輸出路徑來對(duì)數(shù)據(jù)圖中的節(jié) 點(diǎn)進(jìn)行分類。k-l相似度定義了數(shù)據(jù)圖節(jié)點(diǎn)上的一個(gè)等價(jià)關(guān)系，我們稱之為k-l相似關(guān)系。 我們先為每個(gè)這樣的等價(jià)類建立一個(gè)索引節(jié)點(diǎn)，將等價(jià)類里的節(jié)點(diǎn)看成是這個(gè)索引節(jié)點(diǎn)的 一個(gè)擴(kuò)展，如果索引節(jié)點(diǎn)記為X的話，對(duì)應(yīng)的等價(jià)類就記為ext[X]。然后，如果在圖G中 ext[A]中的某個(gè)節(jié)點(diǎn)和ext[B]中的某個(gè)節(jié)點(diǎn)之間存在邊的話，就將索引節(jié)點(diǎn)A和索引節(jié)點(diǎn)B 用邊相連。這樣，我們就構(gòu)建出了一個(gè)基于k-l相似度的索引圖，稱為UD(k，l)索引圖。\nUD(k，l)索引具有如下一些性質(zhì)。\n性質(zhì)1：對(duì)于節(jié)點(diǎn)u和v，如果$u{\approx }_l^{k}v,$則它們所有長度為m(m≤k+1)的輸入標(biāo)簽路徑 都是相同的，所有長度為n(n≤l)的輸出路徑也都是相同的。\n性質(zhì)2：UD(k，l)索引對(duì)于任意一條長度為m(m≤k+1)的簡(jiǎn)單路徑表達(dá)式和長度為n (n≤l)的條件路徑表達(dá)式的查詢結(jié)果都是精確的。\n性質(zhì)3：對(duì)于長度為m(m≥k+1)的簡(jiǎn)單路徑和長度為n(n≥l)的條件路徑，UD(k，l)的 查詢結(jié)果是近似的。它返回的結(jié)果集只是一個(gè)可能的結(jié)果集，并不一定是真正的結(jié)果集， 需要到源數(shù)據(jù)圖上驗(yàn)證結(jié)果集中的數(shù)據(jù)節(jié)點(diǎn)。\n性質(zhì)4：UD(k，l)索引是安全的，也就是說，對(duì)于任何路徑表達(dá)式，它返回的結(jié)果集 總是包含了在源數(shù)據(jù)圖中執(zhí)行這個(gè)查詢應(yīng)該返回的結(jié)果集。這樣，就保證了即使返回的結(jié) 果集不是真正需要的結(jié)果集，也可以通過在源數(shù)據(jù)圖上進(jìn)行驗(yàn)證來彌補(bǔ)。\n性質(zhì)5：UD(k+1，l)索引要么和UD(k，l)索引保持一致，要么是UD(k，l)索引的一個(gè) 細(xì)分。類似的，UD(k，l+1)索引要么和UD(k，l)索引保持一致，要么是UD(k，l)索引的一 個(gè)細(xì)分。\n根據(jù)UD(k，l)的上述性質(zhì)，可以將UD(k，l)索引結(jié)構(gòu)圖用于執(zhí)行路徑表達(dá)式，特別是用 于執(zhí)行分支路徑表達(dá)式，進(jìn)行查詢。具體步驟為：首先對(duì)源XML文檔構(gòu)建UD(k，l)索引， 將預(yù)期的向上相似度k和向下相似度l作為輸入，建立好的UD(UD(k，l)文檔作為輸出。第一步， 對(duì)所有的數(shù)據(jù)節(jié)點(diǎn)按其標(biāo)簽進(jìn)行分類，得到一個(gè)節(jié)點(diǎn)集列表，每一個(gè)節(jié)點(diǎn)集都有一個(gè)唯一 的標(biāo)簽；然后計(jì)算每個(gè)節(jié)點(diǎn)集的向上相似度，反復(fù)分裂具有最小向上相似度的節(jié)點(diǎn)集，直 到所有節(jié)點(diǎn)集中最小的向上相似度ub不小于給定的參數(shù)k；然后，計(jì)算每個(gè)節(jié)點(diǎn)集的向下 相似度，同樣反復(fù)分裂節(jié)點(diǎn)直到所有節(jié)點(diǎn)集中最小的向下相似度dp不小于給定的參數(shù)l； 第二步是建立索引節(jié)點(diǎn)及連接索引節(jié)點(diǎn)的邊：首先對(duì)每個(gè)節(jié)點(diǎn)集建立一個(gè)索引節(jié)點(diǎn)；對(duì)于 圖G中任意兩個(gè)有邊相連的頂點(diǎn)u和頂點(diǎn)v，如果索引節(jié)點(diǎn)A和索引節(jié)點(diǎn)B之間沒有邊的 話，就添加上一條邊，這里節(jié)點(diǎn)A對(duì)應(yīng)的節(jié)點(diǎn)集包含u，節(jié)點(diǎn)B的對(duì)應(yīng)節(jié)點(diǎn)集包含v。\n一個(gè)正則路徑表達(dá)式能夠被轉(zhuǎn)換為一個(gè)DFA(確定有限自動(dòng)機(jī))?？梢园裍ML數(shù)據(jù) 作為這個(gè)DFA的輸入，運(yùn)行該DFA來找到那些可以驅(qū)動(dòng)DFA到達(dá)最終狀態(tài)的節(jié)點(diǎn)。這些 節(jié)點(diǎn)匹配了該正則路徑表達(dá)式。一個(gè)帶分支的路徑表達(dá)式可以轉(zhuǎn)換成一系列DFA?？梢酝?過為數(shù)據(jù)圖不斷選擇相應(yīng)的DFA來執(zhí)行帶分支的路徑表達(dá)式。如果存在索引圖的話，可以 將索引圖代替數(shù)據(jù)圖作為DFA的輸入進(jìn)行查詢，以減少查詢代價(jià)。在一個(gè)UD(k，l)索引圖 上執(zhí)行帶分支的路徑表達(dá)式查詢步驟如下：\n為帶分支路徑表達(dá)式的主路徑構(gòu)造DFA?A0，并為每個(gè)條件路徑i構(gòu)造DFA?Ai；接著在 索引圖上運(yùn)行A0，對(duì)索引進(jìn)行深度優(yōu)先遍歷，自動(dòng)機(jī)根據(jù)匹配的節(jié)點(diǎn)自動(dòng)進(jìn)行狀態(tài)轉(zhuǎn)換， 并為分支節(jié)點(diǎn)建立一張表來記錄它們的中間結(jié)果；當(dāng)A0到達(dá)一個(gè)分支節(jié)點(diǎn)時(shí)，暫停其執(zhí)行， 根據(jù)條件路徑啟動(dòng)相應(yīng)的Ai；當(dāng)Ai到達(dá)最終狀態(tài)時(shí)，停止Ai，驗(yàn)證自動(dòng)機(jī)A0停留的那個(gè) 索引節(jié)點(diǎn)對(duì)應(yīng)的節(jié)點(diǎn)集，然后在中間結(jié)果表中存儲(chǔ)經(jīng)驗(yàn)證正確的節(jié)點(diǎn)，之后繼續(xù)執(zhí)行自動(dòng) 機(jī)A0；如果Ai不能到達(dá)最終狀態(tài)，自動(dòng)機(jī)A0就不能繼續(xù)往前執(zhí)行了，而是要先返回它的 前一個(gè)狀態(tài)，再往下執(zhí)行；當(dāng)A0到達(dá)最終狀態(tài)時(shí)，此時(shí)索引圖到達(dá)某個(gè)節(jié)點(diǎn)，對(duì)這個(gè)索引 的節(jié)點(diǎn)集進(jìn)行確認(rèn)，將確認(rèn)正確的結(jié)果添加到最終結(jié)果集中。\n附圖說明\n圖1為描述英格蘭頂級(jí)足球聯(lián)盟的部分信息的XML文檔。\n圖2為一個(gè)UD(2，2)索引的構(gòu)建過程。\n圖3表示節(jié)點(diǎn)的插入過程。\n具體實(shí)施方式\n【1】UD(k，l)索引圖的構(gòu)建：\nUD(k，l)索引圖分兩步來構(gòu)造。第一步，對(duì)所有的數(shù)據(jù)節(jié)點(diǎn)按其標(biāo)簽進(jìn)行分類，也就是 將具有相同標(biāo)簽的節(jié)點(diǎn)歸為一類，這樣可以得到一個(gè)節(jié)點(diǎn)集列表，每一個(gè)節(jié)點(diǎn)集都有一個(gè) 唯一的標(biāo)簽。然后計(jì)算每個(gè)節(jié)點(diǎn)集的向上相似度，反復(fù)分裂具有最小向上相似度的節(jié)點(diǎn)集， 直到所有節(jié)點(diǎn)集中最小的向上相似度ub不小于給定的參數(shù)k。然后計(jì)算每個(gè)節(jié)點(diǎn)集的向下 相似度，同樣反復(fù)分裂節(jié)點(diǎn)直到所有節(jié)點(diǎn)集中最小的向下相似度dp不小于給定的參數(shù)l。 k和l的值需要由實(shí)驗(yàn)來確定，對(duì)于不同的源數(shù)據(jù)集和查詢路徑集，使性能達(dá)到最優(yōu)的k 和l值可能是不一樣的。第二步，建立索引節(jié)點(diǎn)及連接索引節(jié)點(diǎn)的邊。首先對(duì)每個(gè)節(jié)點(diǎn)集 建立一個(gè)索引節(jié)點(diǎn)。對(duì)于圖G中任意兩個(gè)有邊相連的頂點(diǎn)u和v，如果索引節(jié)點(diǎn)A(其對(duì) 應(yīng)的節(jié)點(diǎn)集包含u)和索引節(jié)點(diǎn)B(其對(duì)應(yīng)的節(jié)點(diǎn)集包含v)之間沒有邊相連，則添加一條 邊。\n當(dāng)l取0時(shí)，UD(k，l)索引圖退化為A(k)索引圖，不同的是，每個(gè)節(jié)點(diǎn)集都保留了它自 己的向上相似度ub和向下相似度dp。因此在需要反復(fù)進(jìn)行分裂構(gòu)造的時(shí)候，可以直接找 到ub或dp值最小的索引節(jié)點(diǎn)進(jìn)行分裂，而在構(gòu)造A(k)索引時(shí)，需要檢查每一個(gè)節(jié)點(diǎn)集來 觀察它是否需要進(jìn)一步分裂。所以，UD(k，l)索引需要的構(gòu)建時(shí)間比A(k)索引要少許多。\n圖2是以UD(2，2)索引為例展示了索引的構(gòu)建過程。圖G為源數(shù)據(jù)的結(jié)構(gòu)圖，需要為 其建立UD(2，2)索引圖。首先，根據(jù)節(jié)點(diǎn)標(biāo)簽將節(jié)點(diǎn)分類，得到UD(0，0)索引圖；然后根 據(jù)父節(jié)點(diǎn)的不同分裂同類節(jié)點(diǎn)，例如節(jié)點(diǎn)6和7的標(biāo)簽都是E，但因?yàn)樗鼈兊母腹?jié)點(diǎn)一個(gè) 是B，另一個(gè)是C，所以被分裂開來，這樣就得到了UD(1，0)索引圖；當(dāng)要求所有同類節(jié) 點(diǎn)的祖父節(jié)點(diǎn)的標(biāo)簽也相同時(shí)，即要求同類節(jié)點(diǎn)的向上相似度為2時(shí)，就得到了UD(2，0) 索引圖?，F(xiàn)在，節(jié)點(diǎn)的向上相似度已經(jīng)符合要求了，為了提高向下相似度，需要繼續(xù)分裂 部分索引節(jié)點(diǎn)。根據(jù)各自子節(jié)點(diǎn)的不同，區(qū)分開節(jié)點(diǎn)2和3，得到UD(2，1)索引圖。最后， 當(dāng)要求所有同類節(jié)點(diǎn)的向下相似度為2時(shí)，就得到了UD(2，2)索引圖。\n【2】UD(k，l)索引用于帶分支的路徑表達(dá)式查詢：\n為帶分支路徑表達(dá)式的主路徑構(gòu)造DFAA，并為每個(gè)條件路徑構(gòu)造DFAAi；接著在索 引圖上運(yùn)行A，對(duì)索引進(jìn)行深度優(yōu)先遍歷，自動(dòng)機(jī)根據(jù)匹配的節(jié)點(diǎn)自動(dòng)進(jìn)行狀態(tài)轉(zhuǎn)換，并 為分支節(jié)點(diǎn)建立一張表來記錄它們的中間結(jié)果；當(dāng)A到達(dá)一個(gè)分支節(jié)點(diǎn)時(shí)，暫停其執(zhí)行， 根據(jù)條件路徑啟動(dòng)相應(yīng)的Ai；當(dāng)Ai到達(dá)最終狀態(tài)時(shí)，停止Ai，驗(yàn)證自動(dòng)機(jī)A停留的那個(gè)索 引節(jié)點(diǎn)對(duì)應(yīng)的節(jié)點(diǎn)集，然后在中間結(jié)果表中存儲(chǔ)經(jīng)驗(yàn)證正確的節(jié)點(diǎn)，之后繼續(xù)執(zhí)行自動(dòng)機(jī) A；如果Ai不能到達(dá)最終狀態(tài)，自動(dòng)機(jī)A就不能繼續(xù)往前執(zhí)行了，而是要先返回它的前一 個(gè)狀態(tài)，再往下執(zhí)行；當(dāng)A到達(dá)最終狀態(tài)時(shí)，此時(shí)索引圖到達(dá)某個(gè)節(jié)點(diǎn)，對(duì)這個(gè)索引的節(jié) 點(diǎn)集進(jìn)行確認(rèn)，將確認(rèn)正確的結(jié)果添加到最終結(jié)果集中。\nUD(k，l)索引自身的性質(zhì)決定了，不論是一個(gè)分支節(jié)點(diǎn)的中間結(jié)果還是索引圖返回的 最終結(jié)果都只是一個(gè)可能的結(jié)果集。所以，對(duì)于較長的查詢路徑需要在數(shù)據(jù)圖上驗(yàn)證結(jié)果 集中的節(jié)點(diǎn)。\n\n帶分支的路徑表達(dá)式被分支節(jié)點(diǎn)分割成幾部分。若索引節(jié)點(diǎn)N在分支節(jié)點(diǎn)Ai1的中間 結(jié)果中，那么ext[N]中的數(shù)據(jù)節(jié)點(diǎn)只是有可能是中間結(jié)果而已，需要對(duì)它們進(jìn)行向上和向 下方向的驗(yàn)證。如果N.db≥m1，由UD(k，l)索引的性質(zhì)2可知，不需要進(jìn)行向下驗(yàn)證。如 果N.ub+1≥n1，不需要進(jìn)行向上驗(yàn)證。否則，需要在數(shù)據(jù)圖上進(jìn)行驗(yàn)證。\n例如，在圖2所示的UD(2，2)索引圖上執(zhí)行查詢A/B[E/F]，首先啟動(dòng)從主路徑構(gòu)造的 DFA，即A→B，將索引圖以深度優(yōu)先的方式輸入，自動(dòng)機(jī)暫停在節(jié)點(diǎn)2。啟動(dòng)分支路徑的 DFA，即E→F，節(jié)點(diǎn)2沒有標(biāo)簽為E的子節(jié)點(diǎn)，故自動(dòng)機(jī)不能到達(dá)最終狀態(tài)。繼續(xù)執(zhí)行 主路徑的DFA，自動(dòng)機(jī)暫停在節(jié)點(diǎn)3，接著啟動(dòng)分支路徑的DFA，節(jié)點(diǎn)3存在與E/F匹配 的向下路徑，故自動(dòng)機(jī)能到達(dá)最終狀態(tài)，因此得到中間結(jié)果節(jié)點(diǎn)3。由于在本查詢中，B 標(biāo)簽的向上路徑長度為1，不超過該UD(k，l)索引的k值2，其向下路徑長度為2，不超過 該UD(k，l)索引的l值2。故無需在原始數(shù)據(jù)圖上進(jìn)行驗(yàn)證。\n【3】UD(k，l)索引的增量式維護(hù)：\n當(dāng)源數(shù)據(jù)發(fā)生變化時(shí)，要對(duì)UD(k，l)索引做出相應(yīng)的調(diào)整，這樣才能保證索引對(duì)查詢 表達(dá)式的有效性。因?yàn)橹匦陆⑺饕臅r(shí)間代價(jià)是很高的，所以有必要建立一個(gè)增量更新 算法。\nUD(k，l)索引定義了數(shù)據(jù)節(jié)點(diǎn)的向上相似度為k，向下相似度為l，所以對(duì)于任何索引 節(jié)點(diǎn)的更新的影響范圍限制在向上距它不超過l，向下距它不超過k的節(jié)點(diǎn)中。當(dāng)一個(gè)更新 操作產(chǎn)生時(shí)，采用如下步驟對(duì)索引圖進(jìn)行增量維護(hù)：\n如果更新操作是在節(jié)點(diǎn)υ上插入一個(gè)子樹T，深度優(yōu)先遍歷T，依次插入每一個(gè)節(jié)點(diǎn)。 當(dāng)在節(jié)點(diǎn)θ插入一個(gè)節(jié)點(diǎn)δ時(shí)，首先分裂和重組在θ上方和θ距離為l的節(jié)點(diǎn)，然后找到 合適的索引節(jié)點(diǎn)位置插入節(jié)點(diǎn)δ。如果更新操作是刪除位于節(jié)點(diǎn)γ的一個(gè)子樹T，首先從對(duì) 應(yīng)的索引節(jié)點(diǎn)中移去T中的所有索引節(jié)點(diǎn)；然后對(duì)節(jié)點(diǎn)γ上方和γ距離為l的節(jié)點(diǎn)進(jìn)行分 裂和重組。\n如圖3所示，若要在節(jié)點(diǎn)4下方插入節(jié)點(diǎn)6，其標(biāo)簽為D，則先將節(jié)點(diǎn)4和索引圖中 的節(jié)點(diǎn)5分開，然后再插入節(jié)點(diǎn)6。因?yàn)樗饕龍D要求的向下相似度為2，插入新節(jié)點(diǎn)后， 可能會(huì)影響新插入節(jié)點(diǎn)的祖先節(jié)點(diǎn)，故必須先進(jìn)行分裂。