摘 要：正則路徑查詢(xún)的重寫(xiě)是實(shí)現XML查詢(xún)重寫(xiě)優(yōu)化的基礎。通過(guò)比較正則路徑視圖和正則路徑查詢(xún)的結構信息，分析了兩者之間進(jìn)行映射應滿(mǎn)足的條件，描述了正則路徑視圖到正則路徑查詢(xún)的映射和基于有窮自動(dòng)機的映射過(guò)濾算法，并從理論上闡明了兩個(gè)算法的重寫(xiě)等價(jià)性。借助于此兩個(gè)算法，能夠極大地減少需要求解的映射數目和提高正則路徑查詢(xún)處理的效率。

    關(guān)鍵詞：正則路徑表達式；正則路徑視圖；查詢(xún)重寫(xiě)；XML

    Abstract—With the explosive increase of semi-structured data over Internet, the efficiency of XML query obtains more and more focuses. As the basic module of XML query language, the rewriting of regular path query establishes the foundation of XML query rewriting and optimizing. Based on the previous researches of query answering with multiple regular path expressions, this paper analyzed the mapping conditions that should be held between regular path view and regular path query by comparing their structural information, and described the mapping algorithm between regular path view and regular path query and the finite automata-based filtering algorithm that could eliminate those redundant and illusory mappings in all candidate mappings. At the same time, theoretic analysis showed the equivalence of original query and rewritten query using two algorithms. In addition, these two algorithms can significantly cut down the number of potential mappings and speed up the processing of regular path query.

    Keywords—regular path expression; regular path view; query rewriting; XML

    1．引言
 
    隨著(zhù)XML應用領(lǐng)域的不斷擴展，越來(lái)越多的數據使用XML進(jìn)行表示和交換，如何實(shí)現XML查詢(xún)的重寫(xiě)優(yōu)化相應成為查詢(xún)重寫(xiě)優(yōu)化研究的一個(gè)熱點(diǎn)。由于多數半結構化和XML查詢(xún)語(yǔ)言，例如Lorel[1]、Quilt[2]、XML-QL[3] 和XQuery[4]等都是基于正則路徑表達式的，故對正則路徑表達式的重寫(xiě)優(yōu)化是實(shí)現XML查詢(xún)重寫(xiě)優(yōu)化的基礎。

   目前，XML查詢(xún)重寫(xiě)取得了很大進(jìn)展，對XML數據檢索[5]和訪(fǎng)問(wèn)控制[6]中的查詢(xún)重寫(xiě)以及在已知XML文檔模式的情況下，如何使用XML查詢(xún)回答技術(shù)進(jìn)行信息搜索[7]等問(wèn)題都有比較深入的研究。同時(shí)，針對XML文檔在Oracle數據庫中的存儲和查詢(xún)，也有了更為成熟的成果^[8]。

    但是就正則路徑表達式的重寫(xiě)而言，多數研究工作仍局限于單個(gè)正則路徑表達式的重寫(xiě)[10]。由于在實(shí)際應用中，存在大量正則路徑視圖，而且用戶(hù)查詢(xún)往往含有多個(gè)正則路徑表達式，這就提出了一個(gè)如何使用正則路徑視圖重寫(xiě)含有多個(gè)正則路徑表達式的XML查詢(xún)問(wèn)題。

    2．基本概念

    一篇XML文檔可以用帶有根節點(diǎn)的標簽圖表示，稱(chēng)為XML數據圖，記為G_d。其中，XML文檔的元素和數據值分別用G_d的非葉子節點(diǎn)和葉子節點(diǎn)表示，元素—子元素、元素—屬性及引用關(guān)系用G_d中標有相同名字的邊表示。圖1給出了一個(gè)XML數據圖實(shí)例。形式上，設O為G_d的節點(diǎn)對象ID集，C為G_d的標簽常量集則有如下定義^[9]：

    定義1（正則路徑表達式） 正則路徑表達式（regular path expression）由語(yǔ)法r=ε|a|_|(r₁)|r₁.r₂|r₁|’r₂|r₁*遞歸定義構成。其中，r、r₁和r₂均為正則路徑表達式，ε表示空串，
 
                    
                                      圖1 XML數據圖實(shí)例

    a∈C表示標簽常量，_表示任意一個(gè)標簽。例如，r=(_*. movie).(*.actor.*.(Tom Cruise|Brad Pitt))為一個(gè)正則路徑表達式，其查詢(xún)結果是Gd中r能夠到達的所有節點(diǎn)的集合。

    定義2（正則路徑查詢(xún)）正則路徑查詢(xún)（regular path query）是一種形如q(X):-y1r1z1,…,ynrnzn的查詢(xún)，其中Vq={y1, z1,…,y_n,z_n}稱(chēng)為查詢(xún)體變量，這些變量可以重復；X?Vq稱(chēng)為查詢(xún)頭變量，ri(1≤i≤n)是正則路徑表達式。對于圖1所示數據庫G_d上的正則路徑查詢(xún)q(b):-a(movie)b,b(actor. Name."Tom Cruise")，其查詢(xún)結果為π_b(q) ={2,3}。

    定義3（正則路徑視圖）正則路徑視圖（regular path view）是形如v:-y₁r₁z₁,…,y_nr_nz_n的一種查詢(xún)。與正則路徑查詢(xún)的不同之處是視圖v沒(méi)有指定查詢(xún)頭變量，而且所含正則路徑表達式ri中可以含有變量。對于圖1所示數據庫G_d上的正則路徑視圖v:-p₁(movie)p₂,p₂(year.L)p₃,p₂(actor.name. "Tom Cruise")p₄，其查詢(xún)結果為π(p₁,p₂,p₃,p₄,L)={(1,2,15,26, 1986), (1,3,19,26,2006)}。

    定義4（查詢(xún)樹(shù)和視圖樹(shù)）正則路徑查詢(xún)q和正則路徑視圖v都可以用帶根節點(diǎn)的標簽圖G＝(V,E,R)表示，其中V V_q為節點(diǎn)集，E V×D×V為有向邊集，R∈V為根節點(diǎn)。由于q和v具有分支正則路徑表達式特性，故其圖表示由一個(gè)或多個(gè)無(wú)環(huán)樹(shù)構成，分別稱(chēng)為查詢(xún)樹(shù)T_q和視圖樹(shù)T_v。圖2給出了對應于式（1）的查詢(xún)樹(shù)Tq和視圖樹(shù)Tv：
   
    q(u)：-p₀r₀p₁ ，p₁r₁p₂ ，p₁r₂p₃ ，p₃r₃p₄ ， p₃r₄p₅

     v：-p₀r₅p₁ ， p₀r₆p₂

    3 查詢(xún)重寫(xiě)

    基于視圖的正則路徑查詢(xún)重寫(xiě)問(wèn)題可以描述為：給定式（1）中查詢(xún)q和視圖v，尋找一個(gè)符號映射集以求解訪(fǎng)問(wèn)v且與q返回結果相同的查詢(xún)q’。 

    3.1 符號映射

    使用正則路徑視圖重寫(xiě)正則路徑查詢(xún)的首要步驟是尋找T_v到T_q的符號映射（即節點(diǎn)映射）。其過(guò)程如下^[9]：
首先，通過(guò)廣度優(yōu)先搜索在T_q中尋找一個(gè)節點(diǎn)，使得T_v根節點(diǎn)能夠映射到該節點(diǎn)；然后，標記該節點(diǎn)并遞歸尋找T_v和該節點(diǎn)的孩子節點(diǎn)間的映射；依此順序進(jìn)行下去，直到遍歷完T_q中所有節點(diǎn)。對于T_q的一個(gè)節點(diǎn)w和T_v的一個(gè)節點(diǎn)v，如果w和v的孩子節點(diǎn)數分別是m和n，則在w和v之間有m!/ (m-n)!個(gè)候選映射。
很明顯，在求解v到w的映射時(shí)，應滿(mǎn)足如下條件：

    （1）v的深度≤w的深度；

    （2）v的孩子節點(diǎn)數≤w的孩子節點(diǎn)數。

    借助于該條件，可以極大地減少候選映射的數目^[9]。對于圖2所示查詢(xún)樹(shù)和視圖樹(shù)，節點(diǎn)q0不能映射到節點(diǎn)p₀，因為節點(diǎn)q₀的孩子節點(diǎn)數（2）大于p₀的孩子節點(diǎn)數（1）。算法1首先找到能映射到根節點(diǎn)q₀的節點(diǎn)p₁和p₃，然后依次遞歸尋找其孩子節點(diǎn)間對應的子映射，最終求得候選映射集為：{{q0→p1,q1→p2,q2→p3},{q₀→p₁,q₁→p₃,q₂→p₂}, {q₀ →p₂,q₁→p₄,q₂→p₅},{q₀→p₃,q₁→p₅,q₂→p₄}}。

    算法1只是根據正則路徑視圖和正則路徑查詢(xún)的結構信息尋找到所有可能的符號映射^[9]。這些映射并非都是正確可行的，故需要驗證映射中對應正則路徑表達式的語(yǔ)言等價(jià)性。算法2使用有窮自動(dòng)機實(shí)現了不等價(jià)映射的濾除[9]。由于正則路徑視圖中的正則路徑表達式可能含有變量，所以需要對變量進(jìn)行合一操作[^11]。

    對于圖2中查詢(xún)樹(shù)T_q，使用滿(mǎn)足L(Ai)＝L(re(ri))的有窮自動(dòng)機Ai[12]替換Tq中每條標記ri的邊構造成T_q；使用L(re(ri))中的任意表達式替換視圖樹(shù)Tv中每條標記ri的邊構造成Tv，如圖3所示。這里r₀=(a|b), r₁=c(d|e), r₂=c(dc)*, r₃=g|h, r₄=g, r₅=Ld|Le, r₆=(Ld)*L，其中L是標簽變量。不失一般性，可以規定有窮自動(dòng)機Ai有唯一的開(kāi)始狀態(tài)和終結狀態(tài)，分別對應于邊的源節點(diǎn)和目標節點(diǎn)。

                    
                                      圖2 查詢(xún)樹(shù)和視圖樹(shù)

                   
                              圖3 基于有窮自動(dòng)機的查詢(xún)樹(shù)和視圖樹(shù)
                  
               
              

    根據圖3和算法1所找到的候選映射集，算法2能夠   找到一個(gè)過(guò)濾后候選映射：{((q₀→p₁,q₁→p₂,q₂→p₃),c/L)}。這里，c/L表示c是變量L的一個(gè)替換。圖3中視圖和查詢(xún)之間的最終映射為{((q₀→p₁,q₁→p₂,q₂→p₃),c/L)}。

    3.2 重寫(xiě)過(guò)程

    綜上所述，使用正則路徑視圖重寫(xiě)正則路徑查詢(xún)的過(guò)程為：

    第一步：求解視圖樹(shù)到查詢(xún)樹(shù)的候選符號映射集П；

    第二步：驗證П中候選映射的正確性和等價(jià)性，求得最終映射；

    第三步：利用最終映射對視圖v進(jìn)行變量替換得到v′，最后用v′重構q得到重寫(xiě)查詢(xún)q’。

    4 算法分析

    算法1和2介紹的僅是基于單個(gè)查詢(xún)樹(shù)和視圖樹(shù)進(jìn)行的，當存在多個(gè)查詢(xún)樹(shù)和視圖樹(shù)時(shí)，重復交替使用算法1和2即可解決問(wèn)題。對于重寫(xiě)查詢(xún)和原始查詢(xún)的等價(jià)性問(wèn)題，存在如下定理^[9]：

    定理 使用文中所給映射算法及映射過(guò)濾算法重寫(xiě)得到的查詢(xún)q’與原始查詢(xún)q的計算結果相同。

    證明：將每個(gè)子查詢(xún)視為一個(gè)謂詞，對于給定查詢(xún)q(x,y)=p₁(x₁,…,x_i),…,p_m(y₁,…,y_j)和s(v,w)=r₁(v₁,…,v_k),…,r_n (w₁,…,w_l)，設Q₁,…,Q_m是對應于謂詞p₁,…,p_m的關(guān)系表，R₁,…,R_n是對應于謂詞r1,…,r_n的關(guān)系表，則查詢(xún)q(u):-q(x,y),s(v,w)的計算結果為πu((Q₁?…?Q_m)?(R₁?…?R_n))。另一方面，假定在v中，q’(x,y)=p’( ,…, ),…, ( ,…, )， ,…, 是對應于 ,..., 的關(guān)系表，重寫(xiě)查詢(xún)q′(u):-v,s (v,w)的計算結果為πu(( ?…? )?(R₁?…?R_n))。根據文中映射算法1和2，有p_i≡ (i=1,...,m)成立，故有(Q₁?…?Q_m)＝( ?…? )成立。所以，q′和q的計算結果相同，兩者等價(jià)。

    5 結束語(yǔ)

    正則路徑查詢(xún)的重寫(xiě)是XML查詢(xún)重寫(xiě)優(yōu)化的一個(gè)基礎問(wèn)題。本文通過(guò)比較正則路徑視圖和正則路徑查詢(xún)的結構信息，分析了兩者之間進(jìn)行映射應滿(mǎn)足的條件，并在此基礎上描述了正則路徑視圖到正則路徑查詢(xún)的映射算法及基于有窮自動(dòng)機的映射過(guò)濾算法。理論分析表明這兩個(gè)算法是正確的，而且借助于這兩個(gè)算法能夠極大地減少需要求解的映射數目，提高正則路徑查詢(xún)處理的效率。

    參考文獻

    [1] ABITEBOUL S, QUASS D, MCHUGH J, et al. The Lorel query language for semistructured data [J].Journal of Digital Libraries, 1997, 1(1):68-88.

    2] CHAMBERLIN D, ROBIE J, FLORESCU D. Quilt: An XML query language for heterogeneous data sources[C]. In: Suciu D, Vossen G, eds. Proc. of the Int'l Workshop on the Web and Databases. Dallas: Springer, 2000:1-25.

    [3] DEUTSCH A, FERNANDEZ M, FLORESCU D, et al. XML-QL: a query language for XML[C/OL]. World Wide Web Consortium. http://www.w3.org/TR/NOTE-xml-ql/,1998.

    [4] SCOTT B, CHAMBERLIN D, FERNANDEZ F. Mary, et al. XQuery1.0: an XML query language [EB/OL]. W3C Working Draft. http://www.w3.org/TR/xquery/, 2002. [5] MIHAJLOVI´C V, HIEMSTRA D, BLOK Ernst Henk. Vague element selection and query rewriting for XML retrieval [A]. In: Proc. of the 6th Dutch Belgian Information Retrieval workshop. Delft: Neslia Paniculata, 2006.11-18.

   [6] MOHAN S, SENGUPTA A, WU Yuqing, et al. Access control for XML-a dynamic query rewriting approach [A]. In: Proc. of the 14th ACM International Conference on Information and
Management. Bremen: ACM Press, 2005.251-252.

    [7] MANDREOLI F, MARTOGLIA R. Exploiting related digital library corpora with query rewriting[C]. In: Proc. of the 12th Italian Symposium on Advanced Database Systems. Cagliari: LITHOSgrafiche, 2004.362-369.

    [8] KRISHNAPRASAD M, LIU Zhenhua, MANIKUTTY A, et al. Query rewrite for XML in oracle XML DB[A]. In: Proc. of the 30th Conference on Very Large Data Bases. Toronto: Morgan Kaufmann, 2004.1122-1133.

    [9] Tae-Sun Chung, Hyoung-Joo Kim. A two phase optimization technique for XML queries with multiple regular path expressions[J]. Journal of Systems and Software, 2002, 64(3):183-193.

    [10] CALVANESE D, GIACOMO D, LENZERINI M, et al. Rewriting of regular expressions and regular path queries[A]. In: Proc. of the 18th ACM Symposium on Principles of Database Systems. Philadelphia: ACM Press, 1999.194-204.

    [11] 蔡自興, 徐光佑.人工智能及其應用 (第三版)[M].北京:清華大學(xué)出版社,2004: 34-36.

    [12] 張立昂,劉田.計算理論基礎(第二版)[M].北京:清華大學(xué)出版社,2000: 51-53.

    作者簡(jiǎn)介：高志軍（1978），男，河北廣平人，本科，現就職于邢臺金牛玻纖有限責任公司生產(chǎn)部，主要從事企業(yè)信息化建設方面的研究。

    摘自《自動(dòng)化博覽》2011年第五期