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

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

中圖分類號：TP311.13 文獻標志碼：A

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

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

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

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

1.1 基本定義和原則

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

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

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

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

（5）主路徑子串，對UDFTS-out的兩條查詢Qa、Qb的主要通道的父節(jié)點的數(shù)據(jù)進行處理，獲得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é)點至Sa的結(jié)果節(jié)點為Sa的主路徑子序列，則Sa能夠和Sb的數(shù)值相匹配。

1.2 緩存結(jié)構

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

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

2.1 U-ViewMatch緩存查找算法

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

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

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

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

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

21-out Q-BP：查詢Q的去掉父結(jié)點信息的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為當前視圖

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

MVS.append（Cache. curView）；}

return MVS；}

End

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

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

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

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

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

2.2 算法的改進

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

定理3 補償查詢代價判定，不考慮謂詞的情況下，可以通過考慮最長視圖來構造的補償查詢求解代價最小。

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

3 結(jié)論

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

參考文獻

［1］孟小峰，慈祥. 大數(shù)據(jù)管理：概念、技術與挑戰(zhàn)[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ù)庫緩存技術研究[D]. 武漢：華中師范大學， 2009.

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

［5］崔巖，崔婉秋，王大偉.XML查詢中相關關鍵字匹配算法研究[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ù)庫的查詢技術研究[J].江蘇技術師范學院學報，2013，19（4）：7-12.

［9］谷瑜青. XML數(shù)據(jù)庫及其應用研究[J].電腦編程技巧與維護，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é)構關系查詢技術[D]. 貴陽：貴州大學， 2009.

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

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

［15］ 陳俊林， 張文德. XML文檔的數(shù)據(jù)庫轉(zhuǎn)換技術研究[J].現(xiàn)代圖書情報技術， 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

基金項目：2021年江蘇省高?！扒嗨{工程”優(yōu)秀青年骨干教師培養(yǎng)項目（批準號：2021SJA2246）資助；2021年江蘇省高校哲學社會科學一般項目（批編號：2021SJA2246）資助。

通信作者：邢浩，女，副教授，主要研究方向為金融翻譯與翻譯技術等。E-mail： honna666@foxmail.com