殷麗鳳, 邱占芝

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

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

殷麗鳳, 邱占芝

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定義4 對(duì)于Ti中的2個(gè)節(jié)點(diǎn)v', v''∈Vi,如果存在節(jié)點(diǎn)集 合 {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''為通過(guò)路徑w 的一個(gè)路徑節(jié)點(diǎn)集。用函數(shù)Last(w)表示通過(guò)路徑w 的路徑節(jié)點(diǎn)集最后節(jié)點(diǎn)的集合。

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

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

定義5 設(shè)Tm為一個(gè)XML信息系統(tǒng)模型，粗糙XML樹信息系統(tǒng)TI為Tm的一個(gè)實(shí)例，Path(Tm)表示Tm的所有全路徑集合。?p∈ Path(Tm),? Ti, Tj∈ TI,若Val(lasti(p))=Val(lastj(p)),則稱Ti,Tj子樹信息存在冗余,其中l(wèi)asti(p)表示在Ti中通過(guò)路徑p 的路徑節(jié)點(diǎn)集的最后節(jié)點(diǎn),記作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為一個(gè)XML信息系統(tǒng)模型,粗糙XML樹信息系統(tǒng)TI為Tm的一個(gè)實(shí)例，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ī)則

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

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

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

4 結(jié)束語(yǔ)

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

[1] 許嘉,于戈,谷峪,等. 不確定數(shù)據(jù)管理技術(shù)[J]. 計(jì)算機(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ù)庫(kù)[M]. 北京:電子工業(yè)出版社,2009.

[7] 殷麗鳳,郝忠孝. 不完全信息環(huán)境下存在XML強(qiáng)多值依賴的XML 文檔的規(guī)范化研究[J]. 計(jì)算機(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é)點(diǎn)概率的查詢算法[J].計(jì)算機(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 稿件編號(hào)：201306104

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

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