摘? 要: 一種使各種關(guān)系模式生成技術(shù)都可以直接利用SilkRoute中的XQuery轉(zhuǎn)換算法作為自己的查詢處理器的方法,從而省去構(gòu)造查詢處理器的復(fù)雜工作,提高查詢處理效率。
關(guān)鍵詞: XML文檔? SilkRoute框架? View Forest結(jié)構(gòu)? 共享內(nèi)嵌
?
隨著XML文檔的大量涌現(xiàn),如何有效地存儲(chǔ)和查詢這些文檔中的數(shù)據(jù)已成為業(yè)界關(guān)注的問題。通常,將XML數(shù)據(jù)映射為關(guān)系數(shù)據(jù),再利用經(jīng)典的關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)來(lái)管理XML是一種有效的解決方法。該映射過程大致分為3步:(1)產(chǎn)生關(guān)系模式,創(chuàng)建存儲(chǔ)XML數(shù)據(jù)的關(guān)系表;(2)將XML數(shù)據(jù)分片,存入相應(yīng)的關(guān)系表中;(3)處理XML的查詢,將其轉(zhuǎn)化為等價(jià)的SQL語(yǔ)句。目前通用的XML查詢語(yǔ)言是由W3C提出的XQuery,其描述功能強(qiáng)大,通常由多個(gè)子查詢合成,且?guī)в袕?fù)雜的文檔結(jié)構(gòu)信息。然而將XQuery轉(zhuǎn)換成一組等價(jià)的SQL語(yǔ)句是一項(xiàng)復(fù)雜的工作,而且這種轉(zhuǎn)換和具體的關(guān)系模式生成技術(shù)密切相關(guān)。不同的生成技術(shù)需要開發(fā)相應(yīng)的查詢處理器。
本文提出了一種有效的方法,使不同的關(guān)系模式生成技術(shù)可共享通用查詢處理器,且該查詢處理器無(wú)需自己開發(fā),可直接應(yīng)用著名的SilkRoute[1]中轉(zhuǎn)換Xquery的算法。這樣就可以大大降低開發(fā)強(qiáng)度,提高工作效率。
1? 構(gòu)造View Forest
SilkRoute是一種發(fā)布關(guān)系數(shù)據(jù)的框架。它將關(guān)系數(shù)據(jù)映射為規(guī)定格式的XML數(shù)據(jù),以便在網(wǎng)絡(luò)上傳輸和交換。它提供了一個(gè)XQuery轉(zhuǎn)換算法,可將基于XML數(shù)據(jù)的XQuery查詢轉(zhuǎn)化為基于關(guān)系數(shù)據(jù)的SQL查詢,在數(shù)據(jù)庫(kù)引擎上執(zhí)行后,再把得到的結(jié)果按照XQuery中定義的結(jié)構(gòu)組成XML文檔。
SilkRoute可通過View Forest結(jié)構(gòu)來(lái)進(jìn)行XQuery查詢到SQL語(yǔ)句的轉(zhuǎn)換。View Forest是由若干棵樹組成的森林,其每個(gè)結(jié)點(diǎn)都包含一個(gè)XML標(biāo)簽和一個(gè)SQL語(yǔ)句片斷。從語(yǔ)義角度看,View Forest定義了從關(guān)系數(shù)據(jù)庫(kù)到XML文檔的一個(gè)映射。它的結(jié)點(diǎn)、邊和結(jié)點(diǎn)的XML標(biāo)簽表示了XML文檔的結(jié)構(gòu),而結(jié)點(diǎn)的SQL語(yǔ)句片斷則表示了由關(guān)系數(shù)據(jù)產(chǎn)生XML文檔內(nèi)容的計(jì)算過程。其中,View Forest的內(nèi)部結(jié)點(diǎn)(即非葉結(jié)點(diǎn))表示XML文檔中的元素或?qū)傩?它的XML標(biāo)簽即是相應(yīng)的元素或?qū)傩缘拿Q。其SQL片斷只包含F(xiàn)rom子句和Where子句,指定該結(jié)點(diǎn)從數(shù)據(jù)庫(kù)中選取數(shù)據(jù)的范圍;邊表示XML數(shù)據(jù)間的包含關(guān)系;葉結(jié)點(diǎn)表示其父結(jié)點(diǎn)的值,它的XML標(biāo)簽為值的類型,其SQL片斷一般只包含select子句,表明具體選擇關(guān)系表中與父結(jié)點(diǎn)值相對(duì)應(yīng)的某列屬性。
SilkRoute中轉(zhuǎn)換XQuery的關(guān)鍵算法是VFCA(View Forest合成算法)。它將XQuery查詢涉及到的所有XML數(shù)據(jù)對(duì)應(yīng)的View Forest作為輸入,通過遞歸調(diào)用VFCA,對(duì)XQuery表達(dá)式逐個(gè)轉(zhuǎn)化,得到表示查詢結(jié)果的View Forest;再根據(jù)所得View Forest中每個(gè)結(jié)點(diǎn)的SQL片斷合成完整的SQL語(yǔ)句,從關(guān)系數(shù)據(jù)庫(kù)中取得準(zhǔn)確的數(shù)據(jù),最終生成查詢結(jié)果文檔。
本文的研究對(duì)象是利用關(guān)系數(shù)據(jù)庫(kù)來(lái)存儲(chǔ)和管理XML的系統(tǒng)。它將XML數(shù)據(jù)映射為關(guān)系數(shù)據(jù),與SilkRoute的工作過程正好相反。但這二個(gè)系統(tǒng)中都定義了關(guān)系數(shù)據(jù)和XML數(shù)據(jù)之間的映射關(guān)系,都需要完成轉(zhuǎn)換XQuery的任務(wù)。因此,在本文研究的系統(tǒng)中,可以將View Forest作為橋梁,應(yīng)用SilkRoute提供的算法。即在利用關(guān)系數(shù)據(jù)庫(kù)存儲(chǔ)和管理XML的系統(tǒng)中,可以先構(gòu)造出與源XML數(shù)據(jù)對(duì)應(yīng)的View Forest,然后以它作為輸入?yún)?shù),使用SilkRoute中的VFCA算法及其他輔助算法,將Xquery查詢轉(zhuǎn)化成SQL語(yǔ)句,再把查詢結(jié)果按要求組成XML文檔。這種查詢轉(zhuǎn)換方法能適用于多種關(guān)系模式生成技術(shù)。各種生成技術(shù)都可通過構(gòu)造View Forest,將SilkRoute中轉(zhuǎn)換XQuery的算法作為自己的查詢處理器,省去自行編寫查詢處理器的復(fù)雜工作。
View Forest結(jié)構(gòu)顯示了XML文檔和關(guān)系數(shù)據(jù)之間的映射關(guān)系。所以,根據(jù)XML數(shù)據(jù)的結(jié)構(gòu)信息和在關(guān)系數(shù)據(jù)庫(kù)中的存儲(chǔ)模式,可輕松地構(gòu)造View Forest。算法的基本思路如下:
(1)根據(jù)XML中的元素、屬性及它們之間的包含關(guān)系生成View Forest中所有的內(nèi)部結(jié)點(diǎn)和邊。內(nèi)部結(jié)點(diǎn)表示了XML的元素或?qū)傩?它的XML標(biāo)簽即為元素或?qū)傩缘拿Q;邊表示結(jié)點(diǎn)之間的包含關(guān)系。
(2)為View Forest中的每個(gè)屬性結(jié)點(diǎn)和每個(gè)包含文本值的元素結(jié)點(diǎn)創(chuàng)建一個(gè)子結(jié)點(diǎn),其XML標(biāo)簽為其父結(jié)點(diǎn)值的類型。該子結(jié)點(diǎn)即為View Forest中的葉結(jié)點(diǎn)。
(3)對(duì)于View Forest中的每個(gè)內(nèi)部結(jié)點(diǎn),根據(jù)其所有祖先元素的SQL片斷以及該結(jié)點(diǎn)的數(shù)據(jù)在關(guān)系數(shù)據(jù)庫(kù)中的存儲(chǔ)情況構(gòu)造它的SQL語(yǔ)句片斷。對(duì)于每個(gè)葉結(jié)點(diǎn),則根據(jù)其父結(jié)點(diǎn)值在關(guān)系表中對(duì)應(yīng)的列名構(gòu)造其SQL片斷。
對(duì)于不同的關(guān)系模式生成技術(shù),構(gòu)造View Forest的具體算法也有所不同。下面介紹利用常見的關(guān)系模式生成技術(shù)——共享內(nèi)嵌技術(shù)構(gòu)造View Forest的方法。
2?共享內(nèi)嵌關(guān)系模式下的View Forest構(gòu)造算法
作為實(shí)例分析,本節(jié)將對(duì)使用共享內(nèi)嵌(shared inline)技術(shù)生成的關(guān)系模式給出構(gòu)造View Forest的具體算法。
2.1 共享內(nèi)嵌技術(shù)
共享內(nèi)嵌技術(shù)根據(jù)XML的DTD(或Schema)創(chuàng)建適當(dāng)?shù)年P(guān)系表?，F(xiàn)以XML文檔(程序1)和其DTD(程序2)中數(shù)據(jù)為例來(lái)演示創(chuàng)建過程。
????(1)對(duì)DTD進(jìn)行簡(jiǎn)化,得到對(duì)應(yīng)的DTD圖(見圖1(a))。DTD圖中包含2類結(jié)點(diǎn):一類是表示XML元素或?qū)傩缘慕Y(jié)點(diǎn)(稱為元素結(jié)點(diǎn)或?qū)傩越Y(jié)點(diǎn));另一類是符號(hào)結(jié)點(diǎn),即‘？’或‘*’,介于父元素結(jié)點(diǎn)和子元素結(jié)點(diǎn)之間,表示子元素在父元素中的出現(xiàn)次數(shù)。
(2)遍歷DTD圖。對(duì)于DTD圖中入度為0或者入度大于1的元素結(jié)點(diǎn)(如圖1(a)中的Dep和Name)創(chuàng)建獨(dú)立的關(guān)系表存儲(chǔ)。對(duì)入度為1的元素結(jié)點(diǎn)和屬性結(jié)點(diǎn)(例如Intro),則內(nèi)嵌到存儲(chǔ)父元素的關(guān)系表中,作為某個(gè)字段存儲(chǔ)。對(duì)‘*’下面的子元素結(jié)點(diǎn)(例如Stud和Tea),也要?jiǎng)?chuàng)建獨(dú)立的關(guān)系表予以存儲(chǔ)。
每個(gè)關(guān)系表都有id字段作為主鍵。除了根元素關(guān)系表外,其他關(guān)系表中都有parentid字段作為外鍵,引用其父元素所在關(guān)系表中的id,以提供該元素與其父元素之間的鏈接。而入度大于1的元素結(jié)點(diǎn)(例如Name),由于存在多個(gè)父元素結(jié)點(diǎn),所以其對(duì)應(yīng)的關(guān)系表中增加了parentCode字段,存儲(chǔ)父表的編號(hào)。生成的關(guān)系表如圖1(b)。
?
程序1:XML文檔
??
?????????????
??
?????????????
???
???
?????????????
???
?????????????
程序2:DTD
2.2 View Forest構(gòu)造算法
將圖1(a)所示的DTD圖進(jìn)行簡(jiǎn)化,去掉所有的符號(hào)結(jié)點(diǎn),可得簡(jiǎn)化后的DTD圖(如圖1(c))。以此為基礎(chǔ)構(gòu)造View Forest的算法詳見算法1(該算法假設(shè)DTD中不存在循環(huán)結(jié)構(gòu))。
算法1:對(duì)應(yīng)于共享內(nèi)嵌關(guān)系模式生成技術(shù)的View Forest構(gòu)造算法
Generate_node(DTDGraphNode Dnode,ViewForestNode VparentNode)
1. { prefixName:=′′;/*先將prefixName(列名前綴)置空,
列名前綴為若干層祖先的名字,用′.′隔開。例如Dep
表中的Dep.Intro字段,“Dep.”就是列名前綴*/
2.? if ( Dnode is type Element ) then//若Dnode
//是元素結(jié)點(diǎn)
3. { XMLLabel:=Dnode.Name;
4. if ( Dnode is stored in a separate table from
parent ) then
5. { tName:=getTableName(Dnode);//取得存儲(chǔ)
//Dnode元素的關(guān)系表名
6. alias:=GenAlias(tName);//運(yùn)用某種規(guī)則為
//該表產(chǎn)生一個(gè)別名,不得與已有別名重復(fù)
7. SQLFragment:=′From′+tName+′as′+alias;
//待生成的View Forest結(jié)點(diǎn)的SQL片斷
8. if ( not Dnode.isRoot )? then //若Dnode不是
//根元素結(jié)點(diǎn),則需要找到parentid引用的父表
9. { tempvfnode:=VparentNode;
/*找到Form子句不為空的那個(gè)祖先,它的From子句
?????? 中的表的別名就是需要找的父表別名*/
10.? while tempvfnode.SQLFragment.From=′′do
11.???tempvfnode:=tempvfnode.parent;
12.???ptName:=tempvfnode.SQLFragment.From.alias;
//ptName為找到的父表的別名
13.???SQLFragment:=SQLFragment+′where′+alias
+′.parentid=′+ptName+′.id′;}
14.???tName:=alias;//下面引用tName時(shí),
//都引用的是其別名
15. }
16.????else//Dnode的數(shù)據(jù)和祖先元素的數(shù)據(jù)
//存在一張關(guān)系表的情況,即Dnode是內(nèi)嵌元素
17.???{ tempvfnode:=VparentNode;//尋找該Dnode
//數(shù)據(jù)存放的表
18. while tempvfnode.SQLFragment.From=′′do
19.? { tempvfnode:=tempvfnode.parent;
20.???prefixName:=tempvfnode.XMLLabel+′.′
+prefixName;}
21.???tName:=tempvfnode.SQLFragment.From.alias;
//找到存放Dnode表的別名
22.???prefixName:=tempvfnode.XMLLabel+′.′+
prefixName;//獲得正確的列名前綴
23.???SQLFragment:=′From()′;//由于是內(nèi)嵌元素,
??????? ? //所以SQL片斷為空
??? 24.??? }
??? 25.?? ?}
??? 26.? ?if ( Dnode is type Attribute ) then//如果Dnode
???????? //是屬性結(jié)點(diǎn),則一定內(nèi)嵌在元素表中
??? 27.?? ? ... //與處理內(nèi)嵌元素的方法相同,省略(惟一區(qū)別是
??????????? XMLLabel:=′@′+Dnode.Name)
??? 28.? newvfnode:=VF.new(XMLLabel,SQLFragment);
???????? //構(gòu)造View Forest中Dnode對(duì)應(yīng)的結(jié)點(diǎn)
??? 29.? newvfnode.parent:=VparentNode;//把該新結(jié)點(diǎn)
???????? //加入為VparentNode的一個(gè)子結(jié)點(diǎn)
??? 30.? if (Dnode is type element with text,or Dnode is
????????????? type attribute )? then? //構(gòu)造葉結(jié)點(diǎn)
??? 31.? { XMLLabel:=Type(Dnode.Value);//XML標(biāo)簽
?????????????????? ?//為值的類型
??? 32.??SQLFragment:=′SELECT′+tName+′.′+prefixName
???????????????????? +Dnode.Name;
??? 33.? newatomicnode:=VF.new(XMLLabel,SQLFragment);
??? 34.??newatomicnode.parent:=newvfnode;}//葉結(jié)點(diǎn)的
???????????????? //父結(jié)點(diǎn)即為剛剛構(gòu)造的newvfnode
??? 35.?for every ChildNode in Dnode.Children do
??????????????? //對(duì)于Dnode的所有子結(jié)點(diǎn),遞歸調(diào)用該函數(shù)
??? 36.?Generate_node(ChildNode,newvfnode);
??? 算法1的核心是Generate_node函數(shù),它以DTD圖中的結(jié)點(diǎn)作為輸入,創(chuàng)建與之相對(duì)應(yīng)的View Forest結(jié)點(diǎn)。函數(shù)包含2個(gè)參數(shù):Dnode和VparentNode。Dnode是DTD圖中的某個(gè)結(jié)點(diǎn),VparentNode是View Forest中與Dnode的父結(jié)點(diǎn)相對(duì)應(yīng)的結(jié)點(diǎn)。Generate_node函數(shù)是遞歸函數(shù),它先作用于DTD圖的根結(jié)點(diǎn)(這里為Dep,此時(shí)VparentNode參數(shù)為空),創(chuàng)建View Forest的根結(jié)點(diǎn);再按照深度優(yōu)先順序遞歸處理DTD圖中其余結(jié)點(diǎn),從而創(chuàng)建View Forest中相應(yīng)的子孫結(jié)點(diǎn)。函數(shù)處理過程具體分為4個(gè)步驟:
(1)首先根據(jù)Dnode的信息,得到待創(chuàng)建的View Forest結(jié)點(diǎn)的XML標(biāo)簽和SQL片斷。XML標(biāo)簽即為Dnode所表示的元素或?qū)傩缘拿Q(行3)。SQL片斷則要分3種情況處理:
??? ①若Dnode為XML中根元素結(jié)點(diǎn),則SQL片斷形式為:From 根元素表 as 別名(行7)。其中根元素表即是數(shù)據(jù)庫(kù)中存儲(chǔ)根元素的關(guān)系表。
??? ②若Dnode為XML中普通元素結(jié)點(diǎn),且數(shù)據(jù)庫(kù)中將該元素?cái)?shù)據(jù)單獨(dú)存為一張關(guān)系表,則SQL片斷形式為:From 子表 as 子表別名 where 子表別名.parentid=父表別名.id(行13)。其中子表為存儲(chǔ)該元素的關(guān)系表,父表為其外鍵parentid引用的關(guān)系表。從VparentNode或其祖先結(jié)點(diǎn)的SQL語(yǔ)句片斷中可得父表的別名(因?yàn)閂parentNode是待創(chuàng)建結(jié)點(diǎn)的父結(jié)點(diǎn),行10～12)。若存儲(chǔ)該元素的關(guān)系表中還存在parentCode字段(如圖1中的Name表),則還需根據(jù)父表表名在Where子句中限定parentCode的值,算法中省略了這一點(diǎn)。
??? ③若Dnode是內(nèi)嵌元素或?qū)傩越Y(jié)點(diǎn),則由于Dnode的數(shù)據(jù)內(nèi)嵌于祖先元素表中,并未產(chǎn)生新的數(shù)據(jù)選取范圍,所以SQL片斷為空(即From(),行23)。
??? (2)根據(jù)XML標(biāo)簽和SQL片斷創(chuàng)建新的View Forest結(jié)點(diǎn)newvfnode(行28),再把新結(jié)點(diǎn)作為VparentNode的子結(jié)點(diǎn)加入到View Forest中。
??? (3)若Dnode結(jié)點(diǎn)為屬性結(jié)點(diǎn)或包含文本值的元素結(jié)點(diǎn),則繼續(xù)創(chuàng)建newvfnode的子結(jié)點(diǎn)newatomicnode(行31～35),即為View Forest中的葉結(jié)點(diǎn)。其XML標(biāo)簽為父結(jié)點(diǎn)值的類型,SQL片斷形式為select表別名.字段名。其中表別名是存儲(chǔ)Dnode的關(guān)系表的別名,可從newvfnode或其祖先結(jié)點(diǎn)的SQL片斷中得到(行14,18～21);字段名是表中存儲(chǔ)Dnode結(jié)點(diǎn)文本值(或?qū)傩灾?的字段名稱,根據(jù)其構(gòu)成規(guī)則,可由newvfnode及其某些祖先結(jié)點(diǎn)的XML標(biāo)簽組合而得到。
??? (4)將新創(chuàng)建的結(jié)點(diǎn)vfnewnode作為VparentNode參數(shù),對(duì)Dnode的所有的子結(jié)點(diǎn)遞歸調(diào)用Generate_node函數(shù)。重復(fù)上述步驟,繼續(xù)創(chuàng)建View Forest結(jié)點(diǎn)(行35～36)。
以程序1、程序2中的XML數(shù)據(jù)為實(shí)例,應(yīng)用該算法構(gòu)造的View Forest如圖2所示(圖2(a)為View Forest的樹型圖,圖2(b)為部分結(jié)點(diǎn)的SQL片斷)。該算法對(duì)于存在循環(huán)的DTD圖是無(wú)效的。因?yàn)閂iew Forest本身不能出現(xiàn)環(huán)結(jié)構(gòu)。
3? 結(jié)束語(yǔ)
使用關(guān)系數(shù)據(jù)庫(kù)存儲(chǔ)和查詢XML數(shù)據(jù)一直是研究者們關(guān)注的熱點(diǎn)。根據(jù)XML數(shù)據(jù)的特性,有多種生成關(guān)系模式的技術(shù)。但對(duì)于每一種生成技術(shù)都需要開發(fā)復(fù)雜的查詢處理器,將XQuery轉(zhuǎn)換成SQL語(yǔ)句。本文提出的方法,使得絕大部分關(guān)系模式生成技術(shù)都可直接利用SilkRoute中轉(zhuǎn)換及優(yōu)化XQuery的算法作為自己的查詢處理器,省去了大量的開發(fā)工作,提高了處理查詢的效率。該方法的核心思想是根據(jù)XML數(shù)據(jù)的結(jié)構(gòu)信息和存儲(chǔ)模式來(lái)構(gòu)造SilkRoute中的重要的數(shù)據(jù)結(jié)構(gòu)View Forest,隨后利用SilkRoute中的算法轉(zhuǎn)換XQuery。作為分析實(shí)例,本文針對(duì)典型的關(guān)系模式生成技術(shù)——共享內(nèi)嵌技術(shù),給出了相應(yīng)的構(gòu)造View Forest的算法。以本文的方法為基礎(chǔ),可以很容易地推導(dǎo)出對(duì)應(yīng)于其他關(guān)系模式生成技術(shù)的算法。
上述方法的缺陷是如果XML數(shù)據(jù)存在循環(huán)結(jié)構(gòu),則無(wú)法構(gòu)造View Forest,因?yàn)閂iew Forest中不能帶有回路。因此今后將進(jìn)一步研究如何對(duì)循環(huán)結(jié)構(gòu)進(jìn)行轉(zhuǎn)化,從而構(gòu)造相應(yīng)的View Forest的方法。
?
參考文獻(xiàn)
1? Fernández M,Kadiyska Y,Suciu D et al.SilkRoute:A framework for publishing relational data in XML.ACM
Transactions on Database Systems,2002;27(4)
2? Shanmugasundaram J.Relational Databases for Querying XML Documents:Limitations and opportunities.In:
VLDB Conference,Edinburgh Scotland,1999
3? World-WideWeb Consortium.XQuery 1.0:An XML Query Language.W3C Working Draft,2002,11.http://www.w3.org/TR/xquery/.
4? Florescu D,Kossmann D.Storing and Querying XML?Data using an RDBMS.IEEE Data Engineering
Bulletin,1999,22(3)