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

1 引言

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

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

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

2 基本概念

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

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

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

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

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

圖1 XML數(shù)據(jù)圖實例

3 查詢重寫

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

3.1 符號映射

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

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

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

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

（2）v的孩子節(jié)點數(shù)≤w的孩子節(jié)點數(shù)。

借助于該條件，可以極大地減少候選映射的數(shù)目[9]。對于圖2所示查詢樹和視圖樹，節(jié)點q0不能映射到節(jié)點p0，因為節(jié)點q0的孩子節(jié)點數(shù)（2）大于p0的孩子節(jié)點數(shù)（1）。算法1首先找到能映射到根節(jié)點q0的節(jié)點p1和p3，然后依次遞歸尋找其孩子節(jié)點間對應(yīng)的子映射，最終求得候選映射集為：{{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只是根據(jù)正則路徑視圖和正則路徑查詢的結(jié)構(gòu)信息尋找到所有可能的符號映射[9]。這些映射并非都是正確可行的，故需要驗證映射中對應(yīng)正則路徑表達式的語言等價性。算法2使用有窮自動機實現(xiàn)了不等價映射的濾除[9]。由于正則路徑視圖中的正則路徑表達式可能含有變量，所以需要對變量進行合一操作[11]。

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

圖2 查詢樹和視圖樹

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

根據(jù)圖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' 重構(gòu)q得到重寫查詢q'。

4 算法分析

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

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

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

5 結(jié)束語

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

[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] 蔡自興, 徐光佑. 人工智能及其應(yīng)用 (第三版)[M]. 北京: 清華大學(xué)出版社, 2004: 34-36.

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