粗糙XML 函數(shù)依賴及其推理規(guī)則

殷麗鳳, 邱占芝

（大連交通大學(xué) 軟件學(xué)院, 遼寧 大連 116028）

粗糙XML 函數(shù)依賴及其推理規(guī)則

殷麗鳳, 邱占芝

（大連交通大學(xué) 軟件學(xué)院, 遼寧 大連 116028）

隨著XML成為網(wǎng)絡(luò)信息表示和交換的標準以及不確定數(shù)據(jù)的廣泛存在,不確定XML數(shù)據(jù)庫管理技術(shù)成為了當今研究的熱點。基于粗糙集理論提出了XML信息系統(tǒng)模型、粗糙XML樹信息系統(tǒng)、粗糙冗余等定義,基于粗糙XML信息系統(tǒng)的上近似、下近似給出了粗糙XML函數(shù)依賴的定義及推理規(guī)則,并對推理規(guī)則的正確性進行了證明。為粗糙XML數(shù)據(jù)庫理論的進一步研究奠定了基礎(chǔ)。

粗糙集; 粗糙XML樹信息系統(tǒng); 粗糙冗余; 粗糙XML函數(shù)依賴; 推理規(guī)則

在許多應(yīng)用中,如無線射頻識別技術(shù)(RFID)[1]、傳感器網(wǎng)絡(luò)[2]、基于位置的服務(wù)[3]、數(shù)據(jù)集成[4]等領(lǐng)域都涉及不確定數(shù)據(jù)。不確定數(shù)據(jù)普遍存在,傳統(tǒng)的數(shù)據(jù)管理技術(shù)無法有效管理不確定性數(shù)據(jù),不確定數(shù)據(jù)的管理技術(shù)成為新的研究領(lǐng)域。粗糙集理論[5]是描述和研究不精確、不確定和不完全知識的數(shù)學(xué)工具、用于分析和處理各種不完備信息,從中發(fā)現(xiàn)隱含的知識,揭示潛在的規(guī)律。目前,粗糙集理論基本成熟,主要用在和各個學(xué)科的相互結(jié)合上。由于粗糙集理論和關(guān)系數(shù)據(jù)庫的表示形式都是二維表,所以二者之間的結(jié)合已得到了很多學(xué)者的研究,目前粗糙關(guān)系數(shù)據(jù)庫理論[6]已經(jīng)很成熟。由于不確定數(shù)據(jù)的普遍存在性,研究表示和處理不確定XML(eXtensible Markup Language)數(shù)據(jù)成為一個新的研究領(lǐng)域。不確定數(shù)據(jù)包含不完備數(shù)據(jù)、概率數(shù)據(jù)以及多值數(shù)據(jù),文獻[7]對不完備XML數(shù)據(jù)的處理技術(shù)進行了研究;很多學(xué)者提出了概率XML數(shù)據(jù)處理技術(shù)[8-13],目前多值XML數(shù)據(jù)研究得

還很少。采用概率描述不確定XML數(shù)據(jù)存在很多問題,如由于概率信息的存在,可能世界實例的數(shù)量相對于數(shù)據(jù)規(guī)模為指數(shù)倍,XML數(shù)據(jù)又為樹型結(jié)構(gòu),這樣導(dǎo)致查詢種類、解決問題的難度都大大增加。為了克服概率信息描述不確定XML數(shù)據(jù)加大問題解決難度的缺陷,本文借助粗糙集理論不需要先驗知識的優(yōu)勢,用粗糙集理論來描述XML中的不確定數(shù)據(jù)(允許葉子節(jié)點取值為原子值集合,簡稱粗糙XML數(shù)據(jù)),對粗糙XML函數(shù)依賴相關(guān)問題進行研究,為粗糙XML信息系統(tǒng)的路徑約簡和查詢問題等方面的研究奠定了基礎(chǔ)。

1 粗糙XML樹信息系統(tǒng)

為了研究粗糙XML函數(shù)依賴,首先給出XML信息系統(tǒng)模型、粗糙XML信息系統(tǒng)、粗糙冗余等相關(guān)定義。

定義1 一個XML信息系統(tǒng)模型為一棵樹,記為Tm,其中Tm六元組,即Tm=(Tm, Am, lab, ele, N, Dom),其中:

1）Vm表示樹的節(jié)點的集合;Vm=Vs∪Vl∪Vr,其中Vs表示結(jié)構(gòu)信息,即分支節(jié)點;Vl表示數(shù)據(jù)信息,即葉子節(jié)點;Vr代表根節(jié)點。

2）Am表示樹的有向弧的集合;

3）lab 表示元素名字(EN)和屬性名字(AN)的集合;

4）ele 表示從節(jié)點Am到Vm中一系列節(jié)點的部分映射,滿足對?v∈ Vm,ele(v)=[v1,…,vn]且有向弧 (v,vi)∈ Am,其中i∈[1,n];

5）N 是從樹節(jié)點Vm到Lab 的映射,若任意v∈VS,則N(v)∈EN,若任意v∈Vl,則N(v)∈ AN;

6）Dom 為T 中所有葉子(屬性)節(jié)點的值域;

定義2同態(tài)映射[14]。設(shè)XML模式樹T 'm和Tm之間的映射函數(shù)為φ:VS'→VS,若φ(rs')=rs,則稱映射φ為根保持的;若?V '∈VS,有N(v')=N(φ(v')),則稱映射φ為名字保持的;若φ滿足下面的兩個條件,則稱φ在T 'm和Tm之間是同態(tài)映射。

1） 若T 'm中 任 意 一 條 弧(v',w')∈Am',則(φ(v'),φ(w'))∈ Am;

2 )映射φ為根保持和名字保持。若φ為同態(tài)映射且也為雙射函數(shù),即對于任意a=(v',w')∈Am',當且僅當a'=(φ(v'),φ(w'))∈Am,則稱φ在T 'm和Tm之間是同構(gòu)映射。

粗糙XML樹信息系統(tǒng)對確定的XML樹信息系統(tǒng)進行了擴展,允許葉子節(jié)點的信息值是多個原子值的集合。本文限定TI中任意一棵樹與Tm之間都存在同態(tài)映射,稱TI為Tm的一個實例。T1,T2,… ,Tn的信息可以看作是每個對象信息的描述。

定義4 對于Ti中的2個節(jié)點v', v''∈Vi,如果存在節(jié)點集 合 {v1,v2,…,vn},使 得 v1∈ ele(v'),v2∈ ele(v1),…,vn∈ ele(vn-1),v''∈ele(vn)成立,其中 ,w0=lab(v'),w1=lab(v1),w2=

lab(v2),…,wn=lab(vn),wn+1=lab(v'')。

稱w=w0/w1/…/wn+1為一條從w0到wn+1的一條路徑;稱v'.v1. … .vn.v''為通過路徑w 的一個路徑節(jié)點集。用函數(shù)Last(w)表示通過路徑w 的路徑節(jié)點集最后節(jié)點的集合。

若w0為根節(jié)點,wn+1為葉子節(jié)點,則稱w 為全路徑。

Path(Tm)表示Tm的所有全路徑集合,XML信息系統(tǒng)模型可以看作所有全路徑集合的并集構(gòu)成的樹。

定義5 設(shè)Tm為一個XML信息系統(tǒng)模型，粗糙XML樹信息系統(tǒng)TI為Tm的一個實例，Path(Tm)表示Tm的所有全路徑集合。?p∈ Path(Tm),? Ti, Tj∈ TI,若Val(lasti(p))=Val(lastj(p)),則稱Ti,Tj子樹信息存在冗余,其中l(wèi)asti(p)表示在Ti中通過路徑p 的路徑節(jié)點集的最后節(jié)點,記作Redundant(Ti|Tm,Tj|Tm),也可記作Ti|Tm≡Tj|Tm。若Val(lasti(p))∩Val(lastj(p))≠ψ,則稱Ti,Tj子樹信息存在粗糙冗余,記作R-Redundant(Ti|Tm,Tj|Tm),也可記作

Ti|Tm≈ Tj|Tm。

2 粗糙XML 函數(shù)依賴

為了描述粗糙XML函數(shù)依賴,下面給出粗糙XML樹信息系統(tǒng)TI的上近似、下近似的概念。

定義6設(shè)Tm為一個XML信息系統(tǒng)模型,粗糙XML樹信息系統(tǒng)TI為Tm的一個實例，Path(Tm)表示Tm的所有全路徑集合。定義TI在Path(Tm)上的下近似為Path(Tm)(TI)={Ti|?p∈Path(Tm),|Val(lasti(p))|=1且Ti∈TI};定義TI在Path(Tm)上的上近似為Path(Tm)(TI)={Ti| ?p∈Path(Tm),|Val(lasti(p))|≥1且Ti∩ TI≠ ψ}。

下面給出XML粗糙函數(shù)依賴的定義。

3 粗糙XML函數(shù)依賴的推理規(guī)則

為了解決邏輯蘊涵的判定問題,需要從一組已知的粗糙XML函數(shù)依賴集,推導(dǎo)出其它粗糙XML函數(shù)依賴成立,這就需要一個粗糙XML函數(shù)依賴的推理規(guī)則集。下面給出相應(yīng)的推理規(guī)則集,并對其正確性給予證明。

定理1 設(shè)Tm為粗糙XML 樹信息系統(tǒng)模型,TI={T1,T2,…,Tn}為粗糙XML樹信息系統(tǒng)且是Tm的一個實例,Path(Tm)表示Tm的所有全路徑集合。下面推理規(guī)則成立:

由(1)、(2)可得傳遞規(guī)則成立。

4 結(jié)束語

目前,基于粗糙集研究不確定XML函數(shù)依賴問題,在國內(nèi)外還處于空白。文中借助粗糙集對確定的XML樹信息系統(tǒng)進行了擴展,允許葉子節(jié)點的信息值是多個原子值的集合。給出了粗糙XML樹信息系統(tǒng)、粗糙冗余等相關(guān)的定義,借助上近似、下近似給出了粗糙XML函數(shù)的定義以及相應(yīng)的推理規(guī)則,并對推理規(guī)則的正確性進行了證明。本文的理論成果為粗糙XML數(shù)據(jù)的路徑約簡及查詢問題的進一步研究奠定了基礎(chǔ)。

[1] 許嘉,于戈,谷峪,等. 不確定數(shù)據(jù)管理技術(shù)[J]. 計算機科學(xué)與探索,2009,3(6):561-576.

XU Jia,YU Ge,GU Yu,et al. RFID uncertain datamanagement technology[J]. Journal of Frontiers of ComputerScience and Technology,2009,3(6):561-576.

[2] DESHPANDE A,GUESTRIN C,MADDEN S,et al.Model-driven data acquisition in sensor networks[C]//Proceedings of the30th International Conference on Very Large Databases.Toronto,2004:588-599.

[3] LIU L. From data privacy to location privacy:models andalgorithms(tutorial) [C]//Proceedings of the 33rd InternationalConference on Very Large Databases. Vienna,2007:1429-1430.

[4] MADHAVAN J,COHEN S,XIN D,HALEVY A,et al. Webscaledata integration: you can afford to pay as you go[C]//Proceedings of the 3rd Biennial Conference on Innovative DataSystems Research.Asilomar, 2007:342-350.

[5] PAWLAK Z. Rough sets[J]. International Journal of Computer and Information Science,1982,11(5):341-356.

[6] 安秋生. 粗糙關(guān)系數(shù)據(jù)庫[M]. 北京:電子工業(yè)出版社,2009.

[7] 殷麗鳳,郝忠孝. 不完全信息環(huán)境下存在XML強多值依賴的XML 文檔的規(guī)范化研究[J]. 計算機研究與發(fā)展,2009,46(7):1226-1233.

YIN Li- feng,HAO Zhong - xiao. Normalization of XMLdocument with strong MVD under incomplete informationcircumstances [J]. Journal of Computer Research andDevelopment,2009,46(7):1226-1233.

[8] HUNG E,GETOOR L,SUBRAHMANIAN V S. Probabilisticinterval XML[J]. ACM Transactions on Computational Logic,2007,8(4):24.

[9] KIMELFED B,Sagiv+Y. Modeling and querying probabilistic XML data[C]//Special Interest Group on Management of Data Conference,2008:701-714.

[10] Kimelfeld B,Kosharovsky Y,Sagiv Y.Query evaluation over probabilistic XML[J]. Very Large Databases Journal,2009,18(5):1117-1140.

[11] Abiteboul S,Hubert Chan T- H,Kharlamov E. Aggregate queries for discrete and continuous probabilistic XML[C]//the 13th International Conference of Database Theory.Lausanne, Switzerland,2010:50-61.

[12] Ning B,Liu C F,Yu J X,et al. Matching Top-k answers of twig patterns in probabilistic XML[C]//Database systems for advanced applications, the 15th international conference,Tsukuba, Japan,2010:125-139.

[13] 王建衛(wèi),郝忠孝. 概率XML 文件樹結(jié)點概率的查詢算法[J].計算機研究與發(fā)展,2012,49(4):785-794.

WANG Jian-wei,HAO Zhong-xiao. Node probability query algorithm in probabilistic XML document tree[J]. Journal of Computer Research and Development,2012,49(4):785-794.

[14] Hartmann S,Link S,Kirchberg M. A subgraph- based approach towards functional dependencies for XML[C]// Seventh World- Multi conference on Systemics, Cybernetics and Informatics, invited Session: Dependencies on the Web,2003:200-205.

Functional dependency and inference rules for rough XML

YIN Li feng, QIU Zhan zhi
（Software Technology of Dalian Jiaotong University, Dalian 116028, China）

The management technology of uncertain XML database become today's research focus with XML being the standards of information representation and data exchange on the Internet and uncertain data existing in various fields. Based on rough set theory, the paper formalized the concepts of XML information system model, rough XML tree information systemand rough redundant. Rough XML functional dependency was given basing on the upper and lower approximations of rough XML information system. Inference rules for rough XML dependency were presented, its soundness was given. The production in this work lays the foundation for the research of rough XML database theory.

rough set; rough XML tree information system; rough redundant; rough XML functional dependency; inference rules

TP311.13

A

1674-6236(2014)03-0004-03

2013–06–17 稿件編號：201306104

國家自然科學(xué)基金項目(61074029)；遼寧省自然科學(xué)基金項目(20102014)

殷麗鳳(1976—)，女，黑龍江海倫人，博士，講師。研究方向：不確定XML數(shù)據(jù)庫理論及應(yīng)用。