【正文】 果重建。在關(guān)系數(shù)據(jù)庫中對(duì)于查詢重寫問題的研究已經(jīng)很廣泛。由于XML的復(fù)雜特性，它的查詢重寫問題比關(guān)系數(shù)據(jù)庫面臨更多的挑戰(zhàn)。在文獻(xiàn)[42,43]中的研究表明XML查詢包含問題是XML查詢重寫中一個(gè)很重要的步驟，但它是一個(gè)CoNP問題，特別是當(dāng)XPath查詢只支持有限的幾個(gè)定位符，包括{//,/,*,[]}的時(shí)候。至今，提出了許多用于處理基于XML視圖的查詢重寫的方法。在文獻(xiàn)[35]中研究了服務(wù)器端的XPath查詢重寫。如果可以把索引認(rèn)為是XML物化視圖的特殊情況，它能處理基于XPath視圖的XPath查詢重寫。它將在多項(xiàng)式時(shí)間內(nèi)產(chǎn)生可靠的但是不完全的基于XPath{//,/,*,[]}的計(jì)劃(plan)。它擴(kuò)展了文獻(xiàn)[41]中提出的查詢包含測(cè)試，提出了一個(gè)不完全的但是有效的XPath查詢重寫算法。但是，它沒有考慮多種視圖存在的情況。在文獻(xiàn)[36]中研究了客戶端的查詢重寫問題，它提出了一種在多項(xiàng)式時(shí)間內(nèi)處理XPath查詢重寫的方法，前提條件是查詢重寫計(jì)劃可靠而且正確，并且XPath的定位符是有限的。文獻(xiàn)[44]中研究了數(shù)據(jù)集成中基于視圖的查詢重寫。提出了MPTree 和 PPLattice來管理多種XML視圖，并提出了相關(guān)算法來有效地產(chǎn)生查詢重寫計(jì)劃。由于不同的頻繁的查詢模式，可能會(huì)在客戶端貯存多個(gè)XML視圖。在文獻(xiàn)[45]中研究了基于上百個(gè)視圖的XPath視圖的選擇問題。雖然可以通過使用union操作符合并基于每個(gè)視圖的查詢重寫結(jié)果來擴(kuò)展文獻(xiàn)[36]中提出的方法來支持多種視圖，但是整個(gè)處理過程的性能將會(huì)受很大影響。每一個(gè)視圖必須分別獨(dú)立用來產(chǎn)生候選計(jì)劃。另外，每一個(gè)視圖必須花費(fèi)時(shí)間來對(duì)重寫計(jì)劃進(jìn)行確認(rèn)。文獻(xiàn)[11]中研究了基于XML安全視圖的查詢。提出了將基于安全視圖的XPath查詢重寫為基于原始文檔的等價(jià)查詢的rewrites算法，此算法避免了視圖的物化和保存，提高了運(yùn)行的效率。但是，rewrites算法不能處理遞歸視圖。文獻(xiàn)[12]中研究了XML訪問控制——一種動(dòng)態(tài)的查詢重寫算法。提出了將用戶的基于安全視圖的XPath查詢重寫為一個(gè)等價(jià)的XQuery查詢表達(dá)式的動(dòng)態(tài)查詢重寫算法。這個(gè)表達(dá)式可以在原始數(shù)據(jù)上運(yùn)行。而且保證用戶只看到視圖中的信息并且不能推斷出非授權(quán)訪問的數(shù)據(jù)。但是，它不能處理含有遞歸的模式，而且只能是模式存在的情況下才能應(yīng)用。但是，它不能處理含有遞歸的模式，而且只能是模式存在的情況下才能應(yīng)用。 基本概念和問題定義 DTD簡(jiǎn)介DTD[46,47]是指一類和XML文檔聯(lián)系起來的、專門定義符合本DTD的XML文檔應(yīng)有的數(shù)據(jù)結(jié)構(gòu)的文檔。它為一個(gè)XML文檔或者文檔集合創(chuàng)建一套規(guī)則。它本身不是獨(dú)立的技術(shù)規(guī)范，而是屬于規(guī)范的一部分，XML文檔中的文檔類型聲明既可以是標(biāo)記約束，也可以是帶有標(biāo)記約束的外部文檔。這兩種約束的總和就是DTD。它規(guī)定了XML文檔的構(gòu)建方式。XML文檔里一定要有什么，一定沒有什么，或是什么可出現(xiàn)可不出現(xiàn)，甚至什么元素該出現(xiàn)多少次，這一切都可以在DTD里體現(xiàn)出來。因此，可以把一個(gè)DTD看成是XML文檔的結(jié)構(gòu)模板，DTD是一種保證XML文檔格式正確的有效方法，可以比較XML文檔和DTD文件來看文檔是否符合規(guī)范，元素和標(biāo)簽使用是否正確。一個(gè)DTD文檔包含：元素的定義規(guī)則，元素間關(guān)系的定義規(guī)則，元素可使用的屬性，可使用的實(shí)體或符號(hào)規(guī)則。DTD可以是一個(gè)完全獨(dú)立的文件，也可以在XML文件中直接設(shè)定。也就是說XML文檔有兩種和DTD產(chǎn)生關(guān)聯(lián)的方法：一是直接在文檔里列出DTD的內(nèi)容，二是在文檔里指出所引用DTD的路徑，具體DTD的內(nèi)容在該文檔里。顯然，第二種方法更具有一般性和通用性，而且維護(hù)起來更加容易，也不會(huì)顯著地加大XML文檔的長度。DTD可以是一個(gè)完全獨(dú)立的文件，也可以在XML文件中直接設(shè)定。也就是說XML文檔有兩種和DTD產(chǎn)生關(guān)聯(lián)的方法：一是直接在文檔里列出DTD的內(nèi)容，二是在文檔里指出所引用DTD的路徑，具體DTD的內(nèi)容在該文檔里。顯然，第二種方法更具有一般性和通用性，而且維護(hù)起來更加容易，也不會(huì)顯著地加大XML文檔的長度。在XML文檔里面有一條用于與DTD建立關(guān)聯(lián)的聲明DOCTYPE。當(dāng)XML解析器讀到這條聲明的時(shí)候，如果這個(gè)解析器要驗(yàn)證文檔合法性的話(有些解析器默認(rèn)情況下不會(huì)檢查文檔是否符合DTD定義的結(jié)構(gòu))，它就會(huì)獲得并讀取DTD，根據(jù)它里面的定義來檢驗(yàn)文檔。為了不失一般性，本文用(Ele,Rg,r)表示一個(gè)DTD。其中Ele是元素類型(element types)的有限集合；是中與其他元素不同的類型，稱為根元素；Rg定義元素類型，對(duì)任何中的，正則表達(dá)式為：::＝ str | E |||* (31)其中，表示PCDATA，E表示空集，是Ele中的一種類型(稱作的子元素類型)，“+”、“,”和“*”各自表示disjunction、concatenation和Kleene star。稱為的產(chǎn)生式(production)。所有的DTD都能用這個(gè)形式表示。：一個(gè)XML文檔樹，如果滿足以下四個(gè)條件，則它符合一個(gè)DTD 。四個(gè)條件為：(1) 有唯一獨(dú)一無二的節(jié)點(diǎn)，根節(jié)點(diǎn)，在中用標(biāo)記；(2) 中每個(gè)節(jié)點(diǎn)要么標(biāo)記為一個(gè)類型(稱為元素)，要么標(biāo)記為(稱為文本節(jié)點(diǎn))；(3) 每個(gè)元素有一個(gè)孩子序列，孩子序列是有序的元素或文本節(jié)點(diǎn)，用定義的正則表達(dá)式表示；(4) 每個(gè)文本節(jié)點(diǎn)為字符串值(PCDATA)，是樹的葉子節(jié)點(diǎn)。如果符合，則稱為的一個(gè)實(shí)例。DTD 可以用一個(gè)圖表示，稱為DTD圖。：如圖31所示，描述了一個(gè)hospital的DTD圖。中每個(gè)元素類型為一個(gè)節(jié)點(diǎn)，稱為節(jié)點(diǎn)，每條邊描述父/子關(guān)系。具體地，對(duì)每個(gè)產(chǎn)生式，有一條邊從節(jié)點(diǎn)到中節(jié)點(diǎn)。如果，那么邊用一個(gè)“*”標(biāo)記，表示一個(gè)元素中可以直接嵌套零個(gè)或多個(gè)元素。如果是disjunction，邊用虛線表示，與concatenation相區(qū)別。在上下文中，可以將DTD稱為，將元素類型稱為節(jié)點(diǎn)。一個(gè)DTD圖可以是一個(gè)有向無環(huán)圖(DAG)，也可以是有環(huán)圖。當(dāng)DTD中含有遞歸時(shí)，即直接或間接依據(jù)自己定義，則DTD圖為有環(huán)圖。與文獻(xiàn)[5]相比，本文方法考慮了DTD的disjunction和遞歸。這里沒有考慮屬性，但可以很容易被添加進(jìn)去。hospitaldurationpatientstaffInfotypestafftreatmentnursedoctorclinicalTrialpatientInfodept**billwardNonameregulartesttrialphonemedication*圖31 文檔DTD示例Fig. 31 Example Document DTD XPath簡(jiǎn)介XPath[46,48]是W3C關(guān)于查詢部分XML文檔的通用標(biāo)準(zhǔn)，XPath 。在W3C的XML查詢標(biāo)準(zhǔn)系列中，還有XPointer等。XPath的設(shè)計(jì)同時(shí)也是為了XPointer服務(wù)的。它給XPointer和XSLT[49]提供了一套定位XML文檔和其他文檔的通用機(jī)制。這套機(jī)制在XML文件中的作用就像是URL在Internet上的作用一樣。為了更方便更靈活地定位XML文檔，XPath也提供了針對(duì)字符串、數(shù)字和布爾值的基本函數(shù)。XPath把整個(gè)XML文檔看成一個(gè)節(jié)點(diǎn)樹，節(jié)點(diǎn)可能有多種類型，如元素節(jié)點(diǎn)、屬性節(jié)點(diǎn)和文本節(jié)點(diǎn)等。對(duì)每種節(jié)點(diǎn)，XPath都定義了如何把該類型節(jié)點(diǎn)轉(zhuǎn)換成字符串。一般地，XML文檔里的節(jié)點(diǎn)可以分成以下七類：根節(jié)點(diǎn)(root node)、元素節(jié)點(diǎn)(element node)、文本節(jié)點(diǎn)(text node)、屬性節(jié)點(diǎn)(attribute node)、命名空間節(jié)點(diǎn)(namespace node)、處理節(jié)點(diǎn)(processing instruction node)、注釋節(jié)點(diǎn)(ment node)。XPath是為了定位XML文檔或是其他文檔而設(shè)計(jì)的。因此，可以說XPath中最核心的就是如何表示某一資源的位置[50]，這就用到表達(dá)式的概念。XPath中的表達(dá)式可以返回節(jié)點(diǎn)集(nodeset)、布爾值(boolean)、數(shù)字值(number)、字符串(string)等四種基本類型之一。一類比較簡(jiǎn)單的表達(dá)式叫做定位路徑(location path)。定位路徑依次由以下三部分組成。(1) 軸(axis) 軸[51]用來確定與當(dāng)前節(jié)點(diǎn)相對(duì)位置而得到一個(gè)節(jié)點(diǎn)集。(2) 節(jié)點(diǎn)測(cè)試(node test) 在從“軸”確定的節(jié)點(diǎn)集中按照節(jié)點(diǎn)名稱或是節(jié)點(diǎn)類型選擇對(duì)應(yīng)的節(jié)點(diǎn)，從而得到一個(gè)節(jié)點(diǎn)的子集。(3) 謂詞(predicate) 在節(jié)點(diǎn)測(cè)試選出的節(jié)點(diǎn)集中根據(jù)定義的謂詞再進(jìn)一步篩選得到最后的結(jié)果，謂詞是可選的。下面介紹一種XPath查詢集，稱為C，定義如下：p::= E | l | * | p/p | //p | p∪p | p[q] (32)其中E、l和*分別表示空路徑、Ele中一個(gè)標(biāo)記和通配符；“∪”、“/”、“//”表示union、childaxis、descendantorselfaxis；稱為限定符，定義如下：q::= p | p=c | q∧q | q∨q | q (33)其中定義如式(32)，是一個(gè)常量，“∧”、“∨”、“”分別表示conjunction，disjunction和negation。對(duì)于p=p1/p2，如果p2=//，則p= p1//。如果用216。表示一個(gè)特殊的查詢，基于給定的XML樹返回空集，則216?！萷為p，p/216。/為216。在XML樹T上，XPath查詢p在一個(gè)上下文節(jié)點(diǎn)(context node)v被賦值，查詢結(jié)果是T中從v點(diǎn)所能訪問的節(jié)點(diǎn)集或字符數(shù)據(jù)，用v[p]表示。限定符操作可以解釋為：在一個(gè)上下文節(jié)點(diǎn)v，如果v[p]非空，謂詞[p]有效，也就是說存在一個(gè)節(jié)點(diǎn)對(duì)于從v點(diǎn)被賦值的查詢p是可訪問的。如果v[p]包含一個(gè)文本節(jié)點(diǎn)，值等于常量c，則[p=c]為真。 問題定義給定安全視圖V：S→Dv，當(dāng)安全視圖V的用戶群組提出查詢時(shí)，視圖提供給用戶群組。一個(gè)基本的賦值方法是：給定一個(gè)文檔DTD D的實(shí)例T，計(jì)算并存儲(chǔ)Tv，然后直接在Tv上查詢。但這就帶來了視圖物化和保存的代價(jià)問題，尤其是當(dāng)一個(gè)大型文檔的多個(gè)視圖同時(shí)物化時(shí)，問題更為嚴(yán)重。而且，在多種訪問策略存在的情況下，因?yàn)閄ML文檔中的數(shù)據(jù)經(jīng)常變化，這就使得物化每一個(gè)安全視圖要付出很大代價(jià)。當(dāng)這種物化視圖用來處理安全問題時(shí)，安全模型必須保證在物化視圖的同時(shí)生成的查詢返回給用戶的結(jié)果必須準(zhǔn)確無誤。這時(shí)，安全問題的實(shí)現(xiàn)變得更加困難。因此，需要采用一種不同的策略來繞過視圖的物化和保存，這就產(chǎn)生了查詢重寫。對(duì)于一個(gè)給定的安全視圖上的查詢p，查詢重寫算法自動(dòng)將基于安全視圖的查詢p轉(zhuǎn)化為一個(gè)基于原始文檔的查詢pt，對(duì)任何文檔T，p與pt產(chǎn)生同樣的查詢結(jié)果，即pt (T)=p(Tv)，這樣就消除了視圖物化及其所帶來的問題。考慮存在遞歸的安全視圖，給定一個(gè)基于遞歸安全視圖的查詢p，要找到一種能處理遞歸視圖的查詢重寫算法，能把p轉(zhuǎn)化為基于原始文檔的等價(jià)的查詢pt。在上述背景下，本文改進(jìn)了文獻(xiàn)[11]中的rewrite算法，針對(duì)此算法不能處理遞歸安全視圖的缺點(diǎn)，提出了一種能處理遞歸安全視圖的查詢重寫算法。 rewrite算法 rewrite算法概述rewrite算法[11]是W. Fan等人于SIGMOD 2004上提出的。它是用來對(duì)基于安全視圖的XPath查詢進(jìn)行重寫，把它轉(zhuǎn)化為基于原始文檔的等價(jià)查詢，避免了視圖的物化和保存。 rewrite算法思想rewrite算法的輸入是一個(gè)安全視圖和一個(gè)基于視圖DTD的查詢p，在算法的執(zhí)行過程中，首先把p分成多個(gè)子查詢，分別對(duì)每個(gè)子查詢進(jìn)行等價(jià)轉(zhuǎn)化，再合并轉(zhuǎn)化之后的子查詢，最后輸出一個(gè)基于原始文檔的與p等價(jià)的查詢pt。對(duì)任何P的子查詢和每個(gè)視圖DTD Dv中的節(jié)點(diǎn)A，在算法中用rw(,A)表示在A點(diǎn)的局部轉(zhuǎn)化，也就是說當(dāng)在上下文節(jié)點(diǎn)A處賦值時(shí)，基于Dv的查詢與等價(jià)。因此算法最后要計(jì)算出的是rw(,A)=Pt。用reach(,A)表示Dv中從A點(diǎn)出發(fā)通過查詢所能到達(dá)的節(jié)點(diǎn)。最后，用N表示Dv中的所有節(jié)點(diǎn)的列表，用Q升序表示所有P的子查詢。rewrite算法具體的實(shí)現(xiàn)過程如下。第一步，計(jì)算查詢p的多個(gè)子查詢列表Q。計(jì)算查詢p的子查詢，將子查詢放入列表Q中。第二步，計(jì)算rw(,A)。對(duì)每個(gè)P的子查詢的子查詢Pi和每個(gè)可能在視圖DTD中的節(jié)點(diǎn)A下的節(jié)點(diǎn)Bi計(jì)算rw(Pi, Bi)， 然后將這些計(jì)算的結(jié)果合并，就得到rw(,A)。也就是把查詢轉(zhuǎn)化為了基于原始文檔的查詢。第三步，通過反復(fù)嵌套自底向上的執(zhí)行，最后合并所有的子查詢的等價(jià)轉(zhuǎn)化結(jié)果，得到pt= rw(p,r)。該算法的時(shí)間復(fù)雜度為O(│p│*│Dv│2)。該算法的時(shí)間復(fù)雜度為O(│p│*│Dv│2)。該算法的時(shí)間復(fù)雜度為O(│p│*│Dv│2)。該算法的時(shí)間復(fù)雜度為O(│p│*│Dv│2)。該算法的時(shí)間復(fù)雜度為O(│p│*│Dv│2)。 查詢重寫實(shí)例下面，我們通過一個(gè)實(shí)例來理解查詢重寫的具體含義。如圖32所示：(a)為文檔DTD，(b)為安全視圖。abcedgbeag(a) 文檔類型定義DTD (b) 安全視圖DTD Dv(a) Document type define DTD (b) Security view DTD Dv圖32 非遞歸視圖中的查詢重寫Fig. 32 Query Rewriting in nonrecursive view給定基于圖32(a)所示DTD的XPath查詢/b//g，算法重寫產(chǎn)生的等價(jià)查詢?yōu)镻1／P2，其中，P1=a／(c∪ε)／bP2=(d∪e)／g查詢重寫算法和安全視圖提供了普通的訪問控制機(jī)制，經(jīng)過查詢算法產(chǎn)生的查詢是安全的，不需要經(jīng)過進(jìn)一步的安全處理就能直接在原始文檔上運(yùn)行。 rewrite算法的局限性通過對(duì)rewri