□□ 陳俊祺

(武警山西總隊參謀部，山西 太原 030012)

引言

隨著越來越多的信息被存儲、交換和使用XML呈現(xiàn)，查詢XML數(shù)據(jù)源的能力變得越來越重要。為解決這一能力需求，W3C XML查詢工作組設(shè)計了XQuery程序語言。它是一種函數(shù)式語言，查詢簡便，易于理解，應(yīng)用靈活，可以查詢廣泛的XML信息源，包括數(shù)據(jù)庫和文檔。XML近年來已經(jīng)成為Web上數(shù)據(jù)表示和交換的事實標(biāo)準，對XQuery處理效率的要求也越來越高。在XQuery的研究領(lǐng)域中，已經(jīng)開發(fā)出一些新技術(shù)，用于提高處理效率，但在這一領(lǐng)域中很少用到“部分評估”的優(yōu)化技術(shù)。為了找到一種提高XQuery處理效率的新方法，擴展了“部分評估”技術(shù)的應(yīng)用范圍，進一步研究了XQuery語言的部分評價技術(shù)。

部分評估，也稱為“程序?qū)ｉT化”，是一種專門的程序轉(zhuǎn)換技術(shù)。給定一個源程序和一個稱為“靜態(tài)輸入”的輸入數(shù)據(jù)一部分，部分評估根據(jù)在使用靜態(tài)輸入分析程序后提取程序中的不變量，生成一個剩余程序。當(dāng)應(yīng)用到剩余輸入數(shù)據(jù)時稱為“動態(tài)輸入”，剩余程序產(chǎn)生的結(jié)果與源程序在應(yīng)用于所有輸入時所產(chǎn)生的結(jié)果相同，通常情況下，剩余程序運行比原始程序快。第一個關(guān)于程序?qū)I(yè)化的應(yīng)用出現(xiàn)在1980年代早期，在隨后的幾年里，大多數(shù)研究人員在編譯時和源代碼中探索了該技術(shù)，但是編譯時專門化技術(shù)并不適合于應(yīng)用程序領(lǐng)域，而用于專門化程序的不變量只能在運行時處理。因此，一些研究人員在運行時開發(fā)了一些專門的程序。在XQuery的應(yīng)用程序領(lǐng)域中，動態(tài)生成的查詢被廣泛采用，如使用XQuery與Java API(XQJ)的應(yīng)用程序。在XQJ中，xqpreparedex抑制的執(zhí)行過程被分為兩個階段：準備階段和執(zhí)行階段。準備階段相當(dāng)于XQuery中的靜態(tài)分析階段，在該階段中，靜態(tài)類型檢查或其他靜態(tài)分析可以為已完成的XQuery程序完成；與動態(tài)階段相對應(yīng)的執(zhí)行階段，在這種情況下，當(dāng)“executeQuery()”方法被調(diào)用時，查詢的值會被多次評估，而不需要再次靜態(tài)地重新分析表達式。在運行XQJ時，數(shù)據(jù)源通常在準備階段被知道，這可以被看作是查詢的不變量。因此，可以使用運行時專門化(RTS)來提高查詢的執(zhí)行效率。

為此，本文設(shè)計了一種名為XQPE的XQuery編程語言的離線部分評估系統(tǒng)。XQPE在編程語言上擴大了部分評估技術(shù)的應(yīng)用范圍，使用XQuery及其應(yīng)用程序，其中包括基于RTS的XQJ應(yīng)用程序框架。

1 技術(shù)背景

Hornof L等[1]已經(jīng)為C程序開發(fā)了一個部分評估器，名為Tempo，一個離線的部分評估器。它也不會在運行時只在編譯時崩潰時專門化程序。在C程序中，有些值不能被編碼到剩余程序中，應(yīng)該作為非liftable(如C程序中的指針)進行注釋。為了確保正確的專門化，Tempo使用評估時間分析來查找那些非liftable值。

DyC是基于特定運行時間的基于注釋的C系統(tǒng)。其執(zhí)行動態(tài)編譯，在用戶控制關(guān)鍵決策的情況下，對程序轉(zhuǎn)換的靈活和系統(tǒng)的部分評估模型進行了動態(tài)編譯。他們的注釋設(shè)計是通過搜索一組靈活的原始指令來管理動態(tài)編譯的，這適用于人類程序員和工具。與Tempo相比，DyC分析處理的是標(biāo)量局部變量，但全局變量、指針或數(shù)據(jù)結(jié)構(gòu)，DyC使用特殊編譯器的專用變體，而不是像Tempo那樣在現(xiàn)有的標(biāo)準編譯器上使用。

Lee P等[2]建議對法比尤斯的研究比DyC和Tempo更有限。在運行時，將在XML中編寫的普通程序轉(zhuǎn)換為本機代碼。但與DyC和Tempo不同的是，F(xiàn)ABIUS自動執(zhí)行所有動態(tài)編譯優(yōu)化，沒有附加注解；動態(tài)編譯過程中涉及的權(quán)衡不是用戶控制的。

Hidelhiko H等[3]提出了一種字節(jié)碼專門化(BCS)技術(shù)，該技術(shù)可以在運行時對Java虛擬機(JVM)語言程序進行專門化。其二進制時間分析算法直接處理字節(jié)碼程序，使BCS獨立于源代碼級語言和編譯器的內(nèi)部。

在部分評價技術(shù)中，特別是在運行時專門化研究的基礎(chǔ)上，研究了XQuery編程語言離線部分評價的編譯時間和運行時專門化。

2 知識準備

作為一種新的函數(shù)語言，XQuery有一些不適合程序?qū)ｉT化的特性。為了解決這些問題，引用敏感性分析(RSA)和兩相結(jié)合時間分析(BTA)，以確保精度和提高專門化的正確性。RSA和兩相BTA的詳細描述在文獻[4]和文獻[5]中都有表示。

2.1 敏感性分析

在XQuery表達式的基本構(gòu)建塊,和其值都是存儲為XML數(shù)據(jù)模型(一棵樹)實例[5]，由無約束的節(jié)點和/或原子值序列,如XML片段由節(jié)點值,表示數(shù)字“5”是由原子值5。在程序?qū)ｉT化中，通常對靜態(tài)表達式的值進行常量折疊以生成剩余程序，這意味著這些值應(yīng)該在剩余程序中進行編碼。這就很容易對一個原子值進行編碼，比如使用數(shù)字“5”來表示原子值5，但是沒有適合的形式來編碼XML節(jié)點。其原因是一個節(jié)點不僅包含XML片段的字符串值，還包含一些有用的語義信息，如節(jié)點標(biāo)識和文檔順序。為了在剩余程序中對節(jié)點進行編碼，除了使用構(gòu)造函數(shù)操作將節(jié)點重構(gòu)為XML片段之外，沒有其他選擇。然而，新的重構(gòu)XML片段僅復(fù)制了字符串值，并且丟失了原始節(jié)點的一些語義信息，但很少有表達式通過使用XQuery中的信息計算出它們的值。如節(jié)點比較操作(“《”、“》”或“is”)需要兩個參數(shù)的文檔命令來完成，計算示例見表1和表2。

表1 生成錯誤的表達式(示例1)

表2 生成正確的剩余表達式(示例2)

表1顯示了不能為節(jié)點進行專門化的情況。在表1的A示例中，“S|m”的節(jié)點比較“是”將專門用于剩余程序?！癝|m”的文檔順序已經(jīng)丟失(實際上，“S|m”的新構(gòu)造段將被視為一個新文檔，并被分配給一個新的文檔順序)，因此，比較不同文檔的節(jié)點是沒有意義的，對應(yīng)的剩余程序結(jié)果，見表1。B示例一定是一個錯誤的結(jié)果。這意味著即使它們的綁定時間是靜態(tài)的，一些表達式也不能專門化。相反，表2顯示了“S|m”的值可以按傳統(tǒng)方式進行專門化。

從表1和表2中可以發(fā)現(xiàn)，如果任意地對所有節(jié)點進行特殊化，可能會出現(xiàn)一些操作需要丟失信息錯誤的專門化；如果只是簡單地禁止節(jié)點的所有專門化，那么XQuery專門化的精度將會非常糟糕，因為大多數(shù)表達式的結(jié)果都是XQuery中的節(jié)點。

參考敏感性分析(RSA)發(fā)現(xiàn)并注釋了計算將滿足重建后語義信息丟失問題的表達式。在RSA之后，specializer將會得到表1中“S|m”的信息，不能專門化，但是表2中的“S|m”可以專門化，這意味著專門化的正確性和精確性可以在一定程度上得到保證。RSA的詳細信息幫助專家實現(xiàn)了高效專業(yè)化[4]。

2.2 兩個階段綁定時間分析

RSA給出了信息，這些狀態(tài)對每個被稱為“引用-敏感狀態(tài)(RSA)”的表達式進行了注釋，以指出當(dāng)它的綁定時間為靜態(tài)時，表達式是否可以專門化。這意味著傳統(tǒng)的BTA需要擴展。因此，設(shè)計了兩個階段的綁定時間分析，前一個階段是BTA1，在這個階段中，表達式被識別并標(biāo)注了綁定時間分析狀態(tài)(BTAS)，它只依賴于配置中可用的靜態(tài)參數(shù)值，以及程序中可用的靜態(tài)信息(如常量)；后一階段是BTA2，用于根據(jù)BTA1給出的RSA和BTAS對表達式進行修改。

在表1中，在做了RSA之后，“S|m”被標(biāo)注為RSA—FALSE，這意味著這個變量不能專門化。在執(zhí)行BTA1之后，“$m”被注釋到BTAS(靜態(tài)的)，然后在執(zhí)行BTA2之后，BTAS“S|m”將會修改到最后的BTAS，即根據(jù)注釋的RSA和BTAS保留。相反，表2中的“S|m”將被注釋到最終的BTAS-STATIC，在完成RSA之后，它給出了RSA—TURE、BTA1、BTAS-STATIC。因此，表1中的變量“S|m”不能專門化，但它的對等物可以專門用于表2。

示例1和示例2的正確結(jié)果見表3。

表3 示例1和示例2的正確結(jié)果

3 運行時專門化

特定編譯(compile-time specialization)目前已經(jīng)被成功應(yīng)用。試驗結(jié)果表明，XQuery程序的效率可以顯著提高。在特定編譯中，不變量或靜態(tài)配置被接受用于專門化；但在運行時應(yīng)用程序可以在執(zhí)行過程中給出信息。如在XQJ應(yīng)用程序中，數(shù)據(jù)源和XQuery程序都是在準備階段實現(xiàn)的，可以提取這些信息進行專門化處理。因此，為了在此場景中擴展XQuery專門化，將相應(yīng)地研究運行時專門化技術(shù)。

3.1 運行時專門化

在預(yù)處理之后，解析的抽象語法樹(AST)中的每個表達式都帶有一個綁定時間。在特定運行時間中，對靜態(tài)狀態(tài)的表達式進行了評估，并在AST中完成了相應(yīng)的結(jié)果，最后將AST轉(zhuǎn)換為剩余代碼，即Java字節(jié)碼級別。設(shè)計以下步驟來實現(xiàn)特定運行時間：

(1)解析XQuery源代碼到AST。

(2)評價AST中靜態(tài)表達式的值。

(3)在全局環(huán)境中存儲這些值。

(4)使用特殊的數(shù)據(jù)攣縮，稱為孔洞，代替AST中評估的表達式。

(5)在全局環(huán)境中添加對孔的綁定和相應(yīng)的值。

(6)用Java字節(jié)碼來編譯AST，Java字節(jié)碼可以直接在Java虛擬機(JVM)上運行。

完成這些任務(wù)后，即完成了專門化并生成字節(jié)碼級別的剩余程序。在JVM上運行剩余程序時，需要從全局環(huán)境中加載所需的孔值。

表4顯示了運行時專門化和編譯時專門化的比較。為了簡單地表示，將使用PSEUDO代碼來表示運行時專門化的結(jié)果。在表4的A中，“OP:CON”是AST中的一個表達式。參數(shù)“S|m”被一個洞取代，這里是孔(2)?？字械膮?shù)“2”表示綁定值的索引。當(dāng)執(zhí)行剩余表達式時，JVM將從這個孔獲取索引值。在表4的B中，編譯時專門化顯示了“OP:CON”與“S|m”的值應(yīng)該編碼到XQuery代碼。

表4 運行時專門化和編譯時專門化

XQuery運行時特殊化原型系統(tǒng)如圖1所示，其包括三個部分：

圖1 XQuery RTS模型系統(tǒng)

(1)XQuery解析器，其輸入是XQuery源代碼，并輸出相應(yīng)的AST。

(2)XQuery部分評估核心，其輸入是由配置和AST提供的不變量，其輸出是具有漏洞的AST和存儲索引值的全局環(huán)境。

(3)字節(jié)碼編譯器將AST編譯成Java字節(jié)碼，它使用全局環(huán)境在JVM上運行時獲得索引。

3.2 代碼爆炸控制

在專門化過程中，展開循環(huán)可能導(dǎo)致代碼爆炸，這是部分評估中的一個關(guān)鍵問題，至今還沒有一個簡單有效的方法來解決該問題。在運行時專門化中，值將不會被編碼到XQuery代碼中，并且只保留它們的內(nèi)存實例，因此在執(zhí)行遞歸函數(shù)調(diào)用和多級“FLWOR”表達式時，會發(fā)生代碼爆炸。擬使用保守的策略在一定程度上控制代碼爆炸。該策略包括兩個主要方面：

(1)遞歸函數(shù)調(diào)用的控制。使用一個動態(tài)分支狀態(tài)(DBS)來標(biāo)記遞歸函數(shù)調(diào)用，如果它屬于一個“if”表達式的一個分支(也包含“typeswitch”表達式)，并且它的條件綁定時間不是靜態(tài)的，那么將這個函數(shù)標(biāo)記為一個真實的狀態(tài)，否則標(biāo)記為FALSE。這意味著當(dāng)為遞歸函數(shù)調(diào)用進行專門化時，專門化器首先檢測DBS，如果DBS為真，那么它生成一個專門的函數(shù)，但不會在剩余程序中展開這個遞歸函數(shù)。

(2)多級“FLWOR”表達式的控制。使用閾值來控制“FLWOR”表達式是否應(yīng)該展開。當(dāng)專門化一個多級別的“FLWOR”時，首先檢查“FLWOR”中的每個“for”子句的值，如果該值的長度大于閾值，則該“for”子句的專門化將被取消；擴展了該子句來進行專門化處理。

4 應(yīng)用示例

4.1 XQJ應(yīng)用程序框架

Java的XQuery API目前在Java Community Process的開發(fā)中作為JSR 225，提供了應(yīng)用程序開發(fā)人員使用XQuery進行XML處理和數(shù)據(jù)集成應(yīng)用程序的機會，并充分支持Java SE和Java EE平臺。XQJ允許Java程序連接到XML數(shù)據(jù)源，準備和執(zhí)行XQuery程序，并將查詢結(jié)果作為XML文檔進行處理。這個功能類似于SQL的JDBC Java API，但是XQJ的查詢語言是XQuery。

用Java語言描述的程序代碼見表5。此代碼段僅限于表述XQJ API的使用方法，不是詳盡或完整的程序段。如假設(shè)“xqds”表示一個給定數(shù)據(jù)源的“XQDataSource”對象。它說明了Java應(yīng)用程序執(zhí)行XQuery表達式的基本步驟(第12和17行)，并在給定的XQuery實現(xiàn)中執(zhí)行第8和第13行調(diào)用的綁定變量。

表5 一個XQL示例

這是一個典型的應(yīng)用場景，在只有一些輸入值改變的情況下，該應(yīng)用程序可以多次執(zhí)行一個查詢。XQJ給出了準備表達式的概念，只有一次靜態(tài)分析時可以多次執(zhí)行，而不需要每次都靜態(tài)分析一遍(見代碼形式4～10行)。所以，XQPreparedExpression的準備階段可以用于做專業(yè)化。而XQuery中的外部變量，通過使用接口bindXXX()綁定到動態(tài)值，可以看作是專門化的動態(tài)輸入。比較第11～14行和第16～18行的代碼段，只有bindInt()中的值是不同的，其他代碼是相同的。在XQPrapredExpression中，“fn:doc('catalog.xml')”、“/prince”和“/name”的表達式在運行時不會再次發(fā)生變化，這些都被視為專門化的不變量。顯然“XQPreparedExpression”的處理非常適合做部分評估。此外，在Java應(yīng)用程序中，查詢可能是動態(tài)接受的(如來自網(wǎng)絡(luò)、I/Os，甚至是程序創(chuàng)建的)。

運行時專門化非常適合為XQJ應(yīng)用程序進行優(yōu)化。為此開發(fā)了一個XQJ應(yīng)用程序框架如圖2所示，其中XQuery處理是通過運行時XQuery專門化來優(yōu)化的。

圖2 基于RTS的XQJ應(yīng)用程序框架

圖2描述了基于RTS的XQJ應(yīng)用程序框架。該框架有三個主要部分：

(1)XQJ接口。它接受java對象實例，其中存儲了XQuery源代碼。它的輸出包括凈化XQuery程序和外部變量，這些變量的值將被視為動態(tài)輸入。所有這些對于用戶都是透明和自動處理的。它還接受由JVM返回的Java對象實例的最終結(jié)果，并將結(jié)果輸出。

(2)RTS專業(yè)化系統(tǒng)。它接受自動凈化的XQuery程序進行專門化。在專門化之后，它會輸出剩余程序(Java字節(jié)碼)和相應(yīng)的全局環(huán)境。

(3)JVM。它使用被接受的剩余程序和全局環(huán)境來完成計算和返回查詢結(jié)果。

4.2 結(jié)果驗證

測試條件：分節(jié)的標(biāo)題應(yīng)該是新羅馬12點的粗體，只有首字母大寫(注：對于子分段和次子分段，像the或者a等單詞不大寫，除非是分段頭的第一個單詞才大寫。)

基于運行時專門化的XQJ已經(jīng)實現(xiàn)，并進行了一系列的驗證，以測試該工作是否能夠真正提高XQJ的執(zhí)行效率。下面使用14個案例在三個不同的XQJ實現(xiàn)中運行：

A組：在XQJ實現(xiàn)中，當(dāng)執(zhí)行exectueQuery()方法時，XQuery程序由一個解釋器執(zhí)行；

B組：在XQJ實現(xiàn)中，XQuery程序是在準備階段編譯的，然后在調(diào)用executeQuery()方法時執(zhí)行它；

C組：在XQJ實現(xiàn)中，XQuery程序在準備階段通過RTS進行優(yōu)化，然后在調(diào)用exectueQuery()方法時執(zhí)行。

所有的案例都運行在一個具有1 GB物理內(nèi)存的Inter Pentium PIV-1.6處理器上。執(zhí)行時間如圖3所示，C組大多數(shù)病例的執(zhí)行時間均小于其他兩組。C組的平均執(zhí)行時間為23.9%，B組為40.5%。這意味著RTS可以顯著提高XQJ的處理效率。

圖3 三組執(zhí)行時間比較

5 結(jié)語

全面介紹了一種用于XQuery編程語言的運行時專門化技術(shù)。在運行時專門化的預(yù)處理階段，使用引用敏感性分析來發(fā)現(xiàn)和注釋值將參與計算的表達式，這些表達式需要語義，并且這些表達式不應(yīng)該在剩余程序中專門化和編碼，即使它是一個靜態(tài)表達式。相應(yīng)地，綁定時間分析不僅根據(jù)配置參數(shù)和其他靜態(tài)信息對表達式進行注釋，而且根據(jù)引用敏感性分析狀態(tài)對表達式進行重新注釋。在專門化階段，首先在AST中添加了一個帶有索引的漏洞，以專門化靜態(tài)表達式，生成一個全局環(huán)境，該環(huán)境存儲被索引的專門化值，然后將此AST編譯成Java字節(jié)碼。一個保守策略用于防止遞歸函數(shù)的無限特殊化，并使用閾值來控制“for”子句的展開。開發(fā)了一個XQuery運行時專門化原型系統(tǒng)。

在應(yīng)用領(lǐng)域，基于運行時專門化設(shè)計并實現(xiàn)了XQJ應(yīng)用程序框架。測試結(jié)果表明，RTS可以顯著提高XQJ應(yīng)用的執(zhí)行效率。XQuery程序的運行時專門化的研究并成功地將其應(yīng)用于XQJ接口，從而擴大了部分評估的應(yīng)用范圍。為大多數(shù)應(yīng)用程序需求提供了XQuery程序的編譯時和運行時專門化。但是也有一些重要的后續(xù)工作要做，如利用XQuery表達式的類型信息來提高綁定時分析的精度，這可以從XML文檔的XML模式中推斷出來。