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