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

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

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

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

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

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

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

1.1 基本定義和原則

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

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

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

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

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

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

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

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

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

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

2.1 U-ViewMatch緩存查找算法

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

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

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

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

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

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

2.2 算法的改進(jìn)

U-ViewMatch算法可以在緩存中搜尋并返回符合查詢主路徑的所有視圖。在計(jì)算機(jī)操作系統(tǒng)的從旁協(xié)助翻譯英文實(shí)用程序中，無論按照什么條件查詢，當(dāng)兩個視圖的路徑都能與查詢主路徑匹配時，如果該視圖具有更長的查詢條件，則結(jié)果更接近實(shí)際的查詢數(shù)值，視圖建立的一次性補(bǔ)償查詢更具體。具體的操作步驟簡單方便，在視圖上請求補(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更簡單。

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

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

3 結(jié)論

本文分析了計(jì)算機(jī)輔助翻譯工具中純XML數(shù)據(jù)庫系統(tǒng)中的語義緩存視圖查找問題。唯一的UDFTS輸出序列化過程是在XPath查詢上執(zhí)行的，因此使用算法U-ViewMatch快速查找與要解決的查詢主路徑匹配的所有緩存視圖，作為候選視圖集來回答查詢，并根據(jù)主路徑長度進(jìn)行排序，再根據(jù)候選視圖集的特點(diǎn)探討一種補(bǔ)償查詢方法，旨在能夠有效提升數(shù)據(jù)信息的查詢效率，減少網(wǎng)絡(luò)數(shù)據(jù)傳輸可能出現(xià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的移動數(shù)據(jù)庫緩存技術(shù)研究[D]. 武漢：華中師范大學(xué)， 2009.

［4］查達(dá)永. 一種基于XML數(shù)據(jù)庫查詢結(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ù)庫的查詢技術(shù)研究[J].江蘇技術(shù)師范學(xué)院學(xué)報(bào)，2013，19（4）：7-12.

［9］谷瑜青. XML數(shù)據(jù)庫及其應(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ù)庫結(jié)構(gòu)關(guān)系查詢技術(shù)[D]. 貴陽：貴州大學(xué)， 2009.

［13］ 郎泓鈺， 任永功. 基于Redis內(nèi)存數(shù)據(jù)庫的快速查找算法[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ù)庫轉(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)號：2021SJA2246）資助；2021年江蘇省高校哲學(xué)社會科學(xué)一般項(xiàng)目（批編號：2021SJA2246）資助。

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