粗糙XML 函數依賴及其推理規則

殷麗鳳, 邱占芝

（大連交通大學 軟件學院, 遼寧 大連 116028）

粗糙XML 函數依賴及其推理規則

殷麗鳳, 邱占芝

（大連交通大學 軟件學院, 遼寧 大連 116028）

隨著XML成為網絡信息表示和交換的標準以及不確定數據的廣泛存在,不確定XML數據庫管理技術成為了當今研究的熱點?；诖植诩碚撎岢隽薠ML信息系統模型、粗糙XML樹信息系統、粗糙冗余等定義,基于粗糙XML信息系統的上近似、下近似給出了粗糙XML函數依賴的定義及推理規則,并對推理規則的正確性進行了證明。為粗糙XML數據庫理論的進一步研究奠定了基礎。

粗糙集; 粗糙XML樹信息系統; 粗糙冗余; 粗糙XML函數依賴; 推理規則

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

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

1 粗糙XML樹信息系統

為了研究粗糙XML函數依賴,首先給出XML信息系統模型、粗糙XML信息系統、粗糙冗余等相關定義。

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

1）Vm表示樹的節點的集合;Vm=Vs∪Vl∪Vr,其中Vs表示結構信息,即分支節點;Vl表示數據信息,即葉子節點;Vr代表根節點。

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

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

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

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

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

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

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

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

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

定義4 對于Ti中的2個節點v', v''∈Vi,如果存在節點集 合 {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 的一個路徑節點集。用函數Last(w)表示通過路徑w 的路徑節點集最后節點的集合。

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

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

定義5 設Tm為一個XML信息系統模型，粗糙XML樹信息系統TI為Tm的一個實例，Path(Tm)表示Tm的所有全路徑集合。?p∈ Path(Tm),? Ti, Tj∈ TI,若Val(lasti(p))=Val(lastj(p)),則稱Ti,Tj子樹信息存在冗余,其中lasti(p)表示在Ti中通過路徑p 的路徑節點集的最后節點,記作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 函數依賴

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

定義6設Tm為一個XML信息系統模型,粗糙XML樹信息系統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粗糙函數依賴的定義。

3 粗糙XML函數依賴的推理規則

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

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

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

4 結束語

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

[1] 許嘉,于戈,谷峪,等. 不確定數據管理技術[J]. 計算機科學與探索,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] 安秋生. 粗糙關系數據庫[M]. 北京:電子工業出版社,2009.

[7] 殷麗鳳,郝忠孝. 不完全信息環境下存在XML強多值依賴的XML 文檔的規范化研究[J]. 計算機研究與發展,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] 王建衛,郝忠孝. 概率XML 文件樹結點概率的查詢算法[J].計算機研究與發展,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

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

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