基于視圖的正則路徑查詢重寫

高志軍（邢臺金牛玻纖有限責任公司，河北 邢臺 054000）

1 引言

隨著XML應用領域的不斷擴展，越來越多的數據使用XML進行表示和交換，如何實現XML查詢的重寫優化相應成為查詢重寫優化研究的一個熱點。由于多數半結構化和XML查詢語言，例如Lorel[1]、Quilt[2]、XML-QL[3]和XQuery[4]等都是基于正則路徑表達式的，故對正則路徑表達式的重寫優化是實現XML查詢重寫優化的基礎。

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

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

2 基本概念

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

定義1（正則路徑表達式） 正則路徑表達式（regular path expression）由語法遞歸定義構成。其中，r、r1和r2均為正則路徑表達式，ε表示空串，a∈C表示標簽常量，_表示任意一個標簽。例如，r=(_*. movie).(*.actor.*.(Tom Cruise|Brad Pitt))為一個正則路徑表達式，其查詢結果是Gd中r能夠到達的所有節點的集合。

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

定義3（正則路徑視圖）正則路徑視圖（regular path view）是形如v:-y1r1z1，…，ynrnzn的一種查詢。與正則路徑查詢的不同之處是視圖v沒有指定查詢頭變量，而且所含正則路徑表達式ri中可以含有變量。對于圖1所示數據庫Gd上的正則路徑視圖v:-p1(movie)p2，p2(year.L)p3，p2(actor.name. "Tom Cruise")p4，其查詢結果為π(p1，p2，p3，p4，L)={(1，2，15，26，1986)， (1，3，19，26，2006)}。

定義4（查詢樹和視圖樹）正則路徑查詢q和正則路徑視圖v都可以用帶根節點的標簽圖G＝(V，E，R)表示，其中V Vq為節點集，E V×D×V為有向邊集，R∈V為根節點。由于q和v具有分支正則路徑表達式特性，故其圖表示由一個或多個無環樹構成，分別稱為查詢樹Tq和視圖樹Tv。圖2給出了對應于式（1）的查詢樹Tq和視圖樹Tv：

圖1 XML數據圖實例

3 查詢重寫

基于視圖的正則路徑查詢重寫問題可以描述為：給定式（1）中查詢q和視圖v，尋找一個符號映射集以求解訪問v且與q返回結果相同的查詢q'。

3.1 符號映射

使用正則路徑視圖重寫正則路徑查詢的首要步驟是尋找Tv到Tq的符號映射（即節點映射）。其過程如下[9]：

首先，通過廣度優先搜索在Tq中尋找一個節點，使得Tv根節點能夠映射到該節點；然后，標記該節點并遞歸尋找Tv和該節點的孩子節點間的映射；依此順序進行下去，直到遍歷完Tq中所有節點。對于Tq的一個節點w和Tv的一個節點v，如果w和v的孩子節點數分別是m和n，則在w和v之間有m!/(m-n)!個候選映射。

很明顯，在求解v到w的映射時，應滿足如下條件：

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

（2）v的孩子節點數≤w的孩子節點數。

借助于該條件，可以極大地減少候選映射的數目[9]。對于圖2所示查詢樹和視圖樹，節點q0不能映射到節點p0，因為節點q0的孩子節點數（2）大于p0的孩子節點數（1）。算法1首先找到能映射到根節點q0的節點p1和p3，然后依次遞歸尋找其孩子節點間對應的子映射，最終求得候選映射集為：{{q0→p1，q1→p2，q2→p3}，{q0→p1，q1→p3，q2→p2}，{q0→p2，q1→p4，q2→p5}，{q0→p3，q1→p5，q2→p4}}。

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

對于圖2中查詢樹Tq，使用滿足L(A)＝L(re(r))的有窮自動機替換Tq中每條標記ri的邊構造成Tq；使用L(re(ri))中的任意表達式替換視圖樹Tv中每條標記ri的邊構造成Tv，如圖3所示。這里r0=(a|b)，r1=c(d|e)，r2=c(dc)*，r3=g|h，r4=g，r5=Ld|Le，r6=(Ld)*L，其中L是標簽變量。不失一般性，可以規定有窮自動機Ai有唯一的開始狀態和終結狀態，分別對應于邊的源節點和目標節點。

圖2 查詢樹和視圖樹

圖3 基于有窮自動機的查詢樹和視圖樹

根據圖3和算法1所找到的候選映射集，算法2能夠找到一個過濾后候選映射：{((q0→p1，q1→p2，q2→p3)，c/L)}。這里，c/L表示c是變量L的一個替換。圖3中視圖和查詢之間的最終映射為{((q0→p1，q1→p2，q2→p3)，c/L)}。

3.2 重寫過程

綜上所述，使用正則路徑視圖重寫正則路徑查詢的過程為：

第一步：求解視圖樹到查詢樹的候選符號映射集П；

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

第三步：利用最終映射對視圖v進行變量替換得到v′，最后用v' 重構q得到重寫查詢q'。

4 算法分析

算法1和2介紹的僅是基于單個查詢樹和視圖樹進行的，當存在多個查詢樹和視圖樹時，重復交替使用算法1和2即可解決問題。對于重寫查詢和原始查詢的等價性問題，存在如下定理[9]：

定理 使用文中所給映射算法及映射過濾算法重寫得到的查詢q’與原始查詢q的計算結果相同。

證明：將每個子查詢視為一個謂詞，對于給定查詢q(x，y)=p1(x1，…，xi)，…，pm(y1，…，yj)和s(v，w)=r1(v1，…，vk)，…，rn(w1，…，wl)，設Q1，…，Qm是對應于謂詞p1，…，pm的關系表，R1，…，Rn是對應于謂詞r1，…，rn的關系表，則查詢q(u):-q(x，y)，s(v，w)的計算結果為πu((Q1，…，Qm)，(R1，…，Rn))。另一方面，假定在v中，q' (x，y)=p' (，…，)，…，，…，，…，是對應于1，...，p'的關系表，重寫查詢q' (u):-v，s (v，w)的計算結果為πu((，…，)，(R1，…，Rn))。根據文中映射算法1和2，有pi≡ (i =1，...，m)成立，故有(Q1，…，Qm)＝(，…，)成立。所以，q' 和q的計算結果相同，兩者等價。

5 結束語

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

[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]. 北京: 清華大學出版社, 2004: 34-36.

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