純XML語(yǔ)料庫(kù)語(yǔ)義緩存中輔助翻譯工具視圖的查找算法研究

摘要：詳細(xì)介紹了純XML數(shù)據(jù)庫(kù)系統(tǒng)的基礎(chǔ)知識(shí)，包括XML文檔緩存結(jié)構(gòu)、基本定義和XML文檔的解析方法等。重點(diǎn)分析了序列化XPath查詢算法，在分析純XML數(shù)據(jù)庫(kù)語(yǔ)義緩存中輔助翻譯工具視圖的快速查找算法的優(yōu)缺點(diǎn)后，給出了一種基于最長(zhǎng)視圖的補(bǔ)償查詢改進(jìn)思路。

關(guān)鍵詞：XML數(shù)據(jù)庫(kù)；語(yǔ)義緩存；計(jì)算機(jī)輔助翻譯工具；快速查找算法

中圖分類號(hào)：TP311.13 文獻(xiàn)標(biāo)志碼：A

經(jīng)過(guò)幾十年發(fā)展，數(shù)據(jù)庫(kù)系統(tǒng)經(jīng)歷了層次數(shù)據(jù)庫(kù)、網(wǎng)狀數(shù)據(jù)庫(kù)、關(guān)系數(shù)據(jù)庫(kù)三個(gè)階段的發(fā)展，在數(shù)據(jù)信息查詢優(yōu)化、數(shù)據(jù)倉(cāng)庫(kù)信息管理、數(shù)據(jù)信息挖掘、移動(dòng)數(shù)據(jù)庫(kù)打造等領(lǐng)域取得了突破性進(jìn)展，很多研究成果被成功轉(zhuǎn)化到商業(yè)應(yīng)用[1]。實(shí)際操作中，XML數(shù)據(jù)庫(kù)查詢求解過(guò)程存在和傳統(tǒng)關(guān)系查詢求解不同的操作問(wèn)題，具體實(shí)施時(shí)，依據(jù)數(shù)據(jù)自身半結(jié)構(gòu)化的特點(diǎn)，數(shù)據(jù)信息查詢往往會(huì)遇到一些困難[2]。例如，在計(jì)算機(jī)輔助翻譯工具數(shù)據(jù)查詢的過(guò)程中，如果使用了緩存物理頁(yè)的簡(jiǎn)單緩存結(jié)構(gòu)，雖然在開始運(yùn)行時(shí)能夠減少一定的I/O操作，但是無(wú)法減少最終相對(duì)的計(jì)算消耗。語(yǔ)義緩存能夠針對(duì)以上問(wèn)題給出解決方法，利用XML語(yǔ)義緩存視圖回答新查詢問(wèn)題，實(shí)現(xiàn)對(duì)數(shù)據(jù)信息的小范圍量化查詢和精準(zhǔn)判斷[3]。為實(shí)現(xiàn)XML數(shù)據(jù)語(yǔ)義緩存，需要對(duì)視圖組織結(jié)構(gòu)實(shí)施優(yōu)化設(shè)計(jì)。在客戶端緩存查詢結(jié)果的基礎(chǔ)上打造XPath級(jí)的語(yǔ)義區(qū)[4-5]；語(yǔ)義區(qū)構(gòu)造完成之后對(duì)一組語(yǔ)義相關(guān)的XPath實(shí)施最小化量化處理，目的是減少網(wǎng)絡(luò)通信負(fù)擔(dān)[6]；緩存結(jié)構(gòu)框架能夠在查詢過(guò)程中實(shí)施緩存處理，在具體實(shí)施操作過(guò)程中所牽扯到的數(shù)據(jù)信息包含XML數(shù)據(jù)片段、數(shù)據(jù)數(shù)值、根點(diǎn)到葉子結(jié)點(diǎn)的全路徑引用關(guān)系[7]。最小化、量化處理視圖和查詢之后，可以利用緩存回答數(shù)據(jù)信息處理問(wèn)題，解決數(shù)據(jù)匹配視圖中的數(shù)據(jù)信息查詢問(wèn)題。計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的快速發(fā)展也使XML數(shù)據(jù)的使用面臨更多的機(jī)遇和挑戰(zhàn)[8]。隨著時(shí)間的推移，應(yīng)用領(lǐng)域的不斷增長(zhǎng)和XML數(shù)據(jù)庫(kù)數(shù)據(jù)的日趨復(fù)雜化，各種應(yīng)用對(duì)XML數(shù)據(jù)庫(kù)數(shù)據(jù)的可查詢、可定位、可存儲(chǔ)的需求持續(xù)增加，特別是計(jì)算機(jī)輔助翻譯工具，引發(fā)了對(duì)XML數(shù)據(jù)進(jìn)行合理存儲(chǔ)和快速查詢的要求[9]。為了更好的發(fā)揮XML數(shù)據(jù)在人們社會(huì)生活中的指導(dǎo)作用，需要研究人員采取積極的措施拓寬數(shù)據(jù)庫(kù)研究領(lǐng)域[10]，強(qiáng)化對(duì)數(shù)據(jù)庫(kù)資源的開發(fā)應(yīng)用[11]。

1 純XML數(shù)據(jù)庫(kù)語(yǔ)義緩存中視圖快速查找算法的基本問(wèn)題

純XML數(shù)據(jù)庫(kù)系統(tǒng)（Native XML Database System，NXDS）在處理XML數(shù)據(jù)時(shí)，不需要轉(zhuǎn)換，可對(duì)數(shù)據(jù)直接進(jìn)行操作，減少了系統(tǒng)資源的消耗；其次，在NXDS中保存XML文件時(shí)，不僅能保存數(shù)據(jù)文件，還能保存與數(shù)據(jù)庫(kù)數(shù)據(jù)具體描述有所關(guān)聯(lián)的信息，如數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型信息等；最后，在NXDS中以原生的檢索形式，不通過(guò)任何文件格式轉(zhuǎn)換就能夠檢索到XML數(shù)據(jù)庫(kù)數(shù)據(jù)，檢索到二叉搜索樹中每一層的每個(gè)節(jié)點(diǎn)。利用這種特性查詢數(shù)據(jù)，為查詢優(yōu)化提供了有利條件[12]。

在計(jì)算機(jī)輔助翻譯工具中，純XML數(shù)據(jù)庫(kù)利用語(yǔ)義緩存回答查詢Q，基本步驟包含：1）緩存查找。通過(guò)緩存查找來(lái)找到緩存中可以用來(lái)回答Q的視圖V，在查詢過(guò)程中涉及到的內(nèi)容有重寫、查詢同構(gòu)和查詢最小化以及判斷關(guān)系；2）補(bǔ)償查詢的構(gòu)造。本文所使用的算法能夠提高第一步求解過(guò)程速度，在計(jì)算機(jī)輔助翻譯工具的數(shù)據(jù)庫(kù)構(gòu)建過(guò)程中能夠在第一時(shí)間尋找到適合的候選視圖，從而提升緩存查詢的性能，并為補(bǔ)償查詢的構(gòu)造做好準(zhǔn)備工作[13]。

1.1 基本定義和原則

（1）主路徑，除了謂詞節(jié)點(diǎn)以外，從根節(jié)點(diǎn)到結(jié)果節(jié)點(diǎn)的全部結(jié)點(diǎn)組成的一條路徑。

（2）主路徑長(zhǎng)度，指路徑上的結(jié)點(diǎn)個(gè)數(shù)，具體可以使用BP表示。

（3）帶結(jié)果結(jié)點(diǎn)的唯一深度在第一時(shí)間出現(xiàn)在序列的首要位置，根據(jù)查詢樹中唯一的深度最優(yōu)順序標(biāo)識(shí)，查詢的構(gòu)造節(jié)點(diǎn)，生成具有結(jié)果節(jié)點(diǎn)的唯一深度并優(yōu)先遍歷。實(shí)踐操作中，順序運(yùn)算相對(duì)于樹形運(yùn)算更方便快捷，在特定的分析中，把XPath的查詢模式轉(zhuǎn)換為UDFTS-out。在數(shù)據(jù)信息的處理中，為了避免由于分支條件的相對(duì)位置不同而導(dǎo)致的不同順序之間的差異限制，在將查詢轉(zhuǎn)化為順序前，對(duì)其進(jìn)行正規(guī)化處理。

（4）假設(shè)兩個(gè)查詢Qa和Qb的根結(jié)點(diǎn)Ra和Rb能夠滿足同根主路徑判斷條件，可以將Qb的主路徑看作是Qa主路徑的同根主路徑，判斷條件見(jiàn)表1。

（5）主路徑子串，對(duì)UDFTS-out的兩條查詢Qa、Qb的主要通道的父節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行處理，獲得Sa和Sb的序列，其中，序列Sa為A1、A2、A3、…、Am，序列Sb為B1、B2、…、Bn。

（6）同根主路徑子串，若兩個(gè)查詢的UDFTS-out主路徑Sa及Sb符合同一根主路徑的串行要求，則Sb為Sa的同根主路徑子串。

（7）主路徑匹配，若兩條主要路徑的Sa、Sb能使Sb的絕對(duì)值超過(guò)Sa的絕對(duì)值，則Sb主路徑中從根節(jié)點(diǎn)至Sa的結(jié)果節(jié)點(diǎn)為Sa的主路徑子序列，則Sa能夠和Sb的數(shù)值相匹配。

1.2 緩存結(jié)構(gòu)

在計(jì)算機(jī)輔助翻譯工具中，針對(duì)不同查詢語(yǔ)言和查詢實(shí)際的表示方法，在數(shù)據(jù)信息匯總分析時(shí)存在兩種不同的緩存系統(tǒng)組織方式，與之對(duì)應(yīng)的緩存查找算法也不同。本文根據(jù)序列的XPath查詢，緩存主要結(jié)構(gòu)見(jiàn)表2，在視圖的具體分析中，No為存放緩存文件的視圖編號(hào)，BP為刪除父節(jié)點(diǎn)的查詢主路徑，UDFTS-out是視圖查詢的序列模式，RS是結(jié)果節(jié)點(diǎn)集合。緩存可以填充數(shù)據(jù)，選擇相應(yīng)的用戶行為分析挖掘數(shù)據(jù)，挖掘用戶頻繁查詢的信息和數(shù)據(jù)，進(jìn)而收集實(shí)體信息和數(shù)據(jù)，保存到緩存系統(tǒng)中。在此過(guò)程中，為了加速對(duì)緩存文件的搜索速度，設(shè)置了索引。索引的基本結(jié)構(gòu)中，Item是一個(gè)索引項(xiàng)，具體情況涵蓋直系后代軸，不區(qū)分大小寫。Position是緩存中視圖的序號(hào)，即緩存系統(tǒng)中的No值。確定緩存和索引結(jié)構(gòu)后，如果有新的查詢信息，系統(tǒng)會(huì)對(duì)這些數(shù)據(jù)信息實(shí)施規(guī)范化的指引和UDFTS-out緩存查找，經(jīng)過(guò)一系列的協(xié)調(diào)分析能夠找到匹配新查詢主路徑的候選視圖。

2 純XML數(shù)據(jù)庫(kù)語(yǔ)義緩存中視圖的快速查找算法

2.1 U-ViewMatch緩存查找算法

緩存的查找算法由緩存的組織結(jié)構(gòu)決定。XML語(yǔ)義緩存查找的方法由查詢模式樹實(shí)現(xiàn)的，將查詢樹與緩存中的視圖模式樹進(jìn)行比較會(huì)消耗大量的時(shí)間[14]，所以在計(jì)算機(jī)輔助翻譯工具實(shí)施操作時(shí)，序列化XPath查詢的目的是減少搜索算法的時(shí)間。結(jié)合定理1，搜索過(guò)程中要先進(jìn)行主路徑匹配分析，通過(guò)找到適合的匹配路徑，才能有效排除不匹配的視圖。

定理1 在具體的匹配分析中，如果查詢Qa主路徑和Qb主路徑不匹配，則Qa和Qb不匹配。

證明：由主路徑匹配、同根主路徑子串和查詢匹配的定義能夠證明定理1。

算法U-ViewMatch是一種緩存查找算法。

輸入：CVS：Cached View Set緩存視圖集，為指向緩存區(qū)的指針；

21-out Q-BP：查詢Q的去掉父結(jié)點(diǎn)信息的UDFTS-out序列的主路徑；

輸出：MVS：Matched View Set，能夠匹配Q主路徑的候選視線圖集

Begin

IndexMatch（rootU-out Q-BP）//索引中Item信息。

if（item==null）

return null；

else{MVS=null

S=Index[item] //Position中position的個(gè)數(shù)

for（i=0，i＜s；i＋＋）{

curView_BP = Index[itme] // Position[i]的主路徑； curView為當(dāng)前視圖

if （BPM （U-out_Q_BP， curView_BP）） //判斷Q主路徑是否與V主路徑匹配

MVS.append（Cache. curView）；}

return MVS；}

End

計(jì)算機(jī)輔助翻譯時(shí)，在U-ViewMatch方法中，首先檢索，以檢驗(yàn)新的Q的根結(jié)點(diǎn)能否用作緩存中的一個(gè)視圖的根結(jié)點(diǎn)。在運(yùn)行期間，若發(fā)生問(wèn)題導(dǎo)致查詢運(yùn)算失效，則表示快取中沒(méi)有相應(yīng)Q的查詢。此時(shí)可以利用數(shù)據(jù)庫(kù)實(shí)現(xiàn)對(duì)數(shù)據(jù)的檢索，能夠加速計(jì)算機(jī)從旁協(xié)助翻譯工具中數(shù)據(jù)信息的查詢和應(yīng)用，并盡快確認(rèn)無(wú)法匹配查詢的情況，完成搜索緩存的所有區(qū)域。在分析查詢索引的過(guò)程中，如果信息搜索成功，則結(jié)合查詢序號(hào)，將查詢主路徑和當(dāng)前序號(hào)對(duì)應(yīng)的顯示主路徑一一比較，顯示對(duì)應(yīng)的指標(biāo)項(xiàng)。在for循環(huán)完成時(shí)，傳回MVS視圖。這時(shí)，MVS中有相應(yīng)的Q的主路徑的視圖。此期間，MVS可能被認(rèn)為是一個(gè)空白集合，因?yàn)镼的根和若干個(gè)執(zhí)行圖表中的根節(jié)點(diǎn)不匹配導(dǎo)致了此情況。

定理2 當(dāng)視圖V的主路徑長(zhǎng)度超出Q的主路徑的長(zhǎng)度時(shí)，V自身無(wú)法被用來(lái)建立一個(gè)可以用來(lái)求解Q值的補(bǔ)償查詢。

證明：結(jié)合主路徑匹配、查詢匹配和補(bǔ)償查詢的定義能夠證明定理2。

結(jié)合定理2，比較視圖主路徑和查詢主要路徑的長(zhǎng)度，若視圖主路徑長(zhǎng)度大于查詢主路徑長(zhǎng)度，說(shuō)明視圖和查詢信息不匹配，此時(shí)，需要及時(shí)采取措施，盡快停止對(duì)主路徑匹配查詢的操作[15]。

如果查詢主路徑的長(zhǎng)度大于視圖主路徑的長(zhǎng)度，需要將每條視圖主路徑進(jìn)行比較，查詢它們的結(jié)點(diǎn)信息。根據(jù)表1中的Y條件，視圖主路徑的“//”結(jié)點(diǎn)可以與查詢主路徑上除“//”之外的多個(gè)連續(xù)節(jié)點(diǎn)匹配。

2.2 算法的改進(jìn)

U-ViewMatch算法可以在緩存中搜尋并返回符合查詢主路徑的所有視圖。在計(jì)算機(jī)操作系統(tǒng)的從旁協(xié)助翻譯英文實(shí)用程序中，無(wú)論按照什么條件查詢，當(dāng)兩個(gè)視圖的路徑都能與查詢主路徑匹配時(shí)，如果該視圖具有更長(zhǎng)的查詢條件，則結(jié)果更接近實(shí)際的查詢數(shù)值，視圖建立的一次性補(bǔ)償查詢更具體。具體的操作步驟簡(jiǎn)單方便，在視圖上請(qǐng)求補(bǔ)償查詢也更快。例如查詢Q=A[D]/B/C[T]，視圖V1=A[D]/B/C，視圖V2=A[D]/B，參照結(jié)合V1的內(nèi)部結(jié)構(gòu)一次性補(bǔ)償查詢CQ1=//C[T]，參照結(jié)合V2基本結(jié)構(gòu)一次性補(bǔ)償查詢CQ2=//B/C[T]，參照結(jié)合V2基本結(jié)構(gòu)一次性補(bǔ)償查詢，CQ1V1內(nèi)部結(jié)構(gòu)比CQ2更簡(jiǎn)單。

定理3 補(bǔ)償查詢代價(jià)判定，不考慮謂詞的情況下，可以通過(guò)考慮最長(zhǎng)視圖來(lái)構(gòu)造的補(bǔ)償查詢求解代價(jià)最小。

證明：設(shè)視圖主路徑的長(zhǎng)度為m，查詢主路徑的長(zhǎng)度為n，結(jié)合上文的具體描述和分析，視圖主路徑匹配查詢。若兩者為一次性補(bǔ)償狀態(tài)，則一次性補(bǔ)償查詢的主路徑為當(dāng)前查詢文件從k個(gè)葉子節(jié)點(diǎn)Qk開始的子串，實(shí)際長(zhǎng)度為（n-k+1），m越大，k值越大，反之亦然。從某種角度來(lái)說(shuō)，對(duì)于可查詢的XPath，查詢深度越小，計(jì)算成本越小。但是，參考最長(zhǎng)時(shí)間匹配的基本原則，結(jié)合主路徑的長(zhǎng)度最長(zhǎng)原則，所構(gòu)建的查詢最優(yōu)解成本是最小的。圖1顯示了查詢、視圖、補(bǔ)償查詢主路徑的長(zhǎng)度，參考定理3，對(duì)U-ViewMatch算法進(jìn)行一些必要的改進(jìn)，在具體實(shí)施操作中，可以根據(jù)主路徑的長(zhǎng)度進(jìn)行排序。

3 結(jié)論

本文分析了計(jì)算機(jī)輔助翻譯工具中純XML數(shù)據(jù)庫(kù)系統(tǒng)中的語(yǔ)義緩存視圖查找問(wèn)題。唯一的UDFTS輸出序列化過(guò)程是在XPath查詢上執(zhí)行的，因此使用算法U-ViewMatch快速查找與要解決的查詢主路徑匹配的所有緩存視圖，作為候選視圖集來(lái)回答查詢，并根據(jù)主路徑長(zhǎng)度進(jìn)行排序，再根據(jù)候選視圖集的特點(diǎn)探討一種補(bǔ)償查詢方法，旨在能夠有效提升數(shù)據(jù)信息的查詢效率，減少網(wǎng)絡(luò)數(shù)據(jù)傳輸可能出現(xiàn)的性能問(wèn)題。

參考文獻(xiàn)

［1］孟小峰，慈祥. 大數(shù)據(jù)管理：概念、技術(shù)與挑戰(zhàn)[J]. 計(jì)算機(jī)研究與發(fā)展，2013，50（1）：146-169.

［2］TAJIMA K， FUKUI Y. Answering Xpath queries over networks by sending minimal views[C]// 30th International Conference on Very Large Data Bases. 2004： 48-59.

［3］許沛華. 基于XML的移動(dòng)數(shù)據(jù)庫(kù)緩存技術(shù)研究[D]. 武漢：華中師范大學(xué)， 2009.

［4］查達(dá)永. 一種基于XML數(shù)據(jù)庫(kù)查詢結(jié)果集緩存方案的設(shè)計(jì)與實(shí)現(xiàn)[D].武漢：華中科技大學(xué)，2016.

［5］崔巖，崔婉秋，王大偉.XML查詢中相關(guān)關(guān)鍵字匹配算法研究[J].信息通信，2016（8）：21-23.

［6］CONSENS M P， RIZZOLO F. Fast answering of XPath query workloads on web collections[C]// 5th International XML Database Symposium. Vienna， 2007： 23-24.

［7］BALMIN A， ZCAN F， BEYER K S， et al. A framework for using materialized XPath views in XML Query Processing[C]// 30th VLDB Conference.Toronto， 2004：60-71.

［8］許嫻. XML數(shù)據(jù)庫(kù)的查詢技術(shù)研究[J].江蘇技術(shù)師范學(xué)院學(xué)報(bào)，2013，19（4）：7-12.

［9］谷瑜青. XML數(shù)據(jù)庫(kù)及其應(yīng)用研究[J].電腦編程技巧與維護(hù)，2015（10）：80-81.

［10］ CHEN L， RUNDENSTEINER E. ACE-XQ： A CachE-aware XQuery answering system[C]// WebDB. 2002： 31-36.

［11］ FENG J H， LI G L， TA N. A Semantic cache framework for secure XML queries[J].? Journal of Computer Science and Technology， 2008， 23（6）： 988-997.

［12］ 汪濤. 純XML數(shù)據(jù)庫(kù)結(jié)構(gòu)關(guān)系查詢技術(shù)[D]. 貴陽(yáng)：貴州大學(xué)， 2009.

［13］ 郎泓鈺， 任永功. 基于Redis內(nèi)存數(shù)據(jù)庫(kù)的快速查找算法[J]. 計(jì)算機(jī)應(yīng)用與軟件， 2016， 33（5）： 40-43+52.

［14］ 畢玉萍， 胡世昌， 李勁華. 基于排序樹的Node-Apriori改進(jìn)算法[J]. 青島大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2020， 33（3）： 50-56.

［15］ 陳俊林， 張文德. XML文檔的數(shù)據(jù)庫(kù)轉(zhuǎn)換技術(shù)研究[J].現(xiàn)代圖書情報(bào)技術(shù)， 2006（9）： 38-42.

Algorithm Research of Auxiliary Translation Tools View in Pure XML Corpus Semantic Cache

XING Hao

（Jincheng College， Nanjing University of Aeronautics and Astronautics， Nanjing 211156， China）

Abstract： The basic knowledge of pure XML database system in detail was introduced， including XML document cache structure， basic definitions and XML document parsing methods. The serialized XPath query algorithm was emphatically analyzed. After analyzed the advantages and disadvantages of fast search algorithm for auxiliary translation tool view in pure XML database semantic cache， an improved idea of compensation query based on the longest view was proposed.

Keywords： XML database; semantic cache; computer aided translation tools; fast search algorithm

收稿日期：2022-08-20

基金項(xiàng)目：2021年江蘇省高校“青藍(lán)工程”優(yōu)秀青年骨干教師培養(yǎng)項(xiàng)目（批準(zhǔn)號(hào)：2021SJA2246）資助；2021年江蘇省高校哲學(xué)社會(huì)科學(xué)一般項(xiàng)目（批編號(hào)：2021SJA2246）資助。

通信作者：邢浩，女，副教授，主要研究方向?yàn)榻鹑诜g與翻譯技術(shù)等。E-mail： honna666@foxmail.com