粗糙XML 函数依赖及其推理规则

殷丽凤, 邱占芝

（大连交通大学 软件学院, 辽宁 大连 116028）

粗糙XML 函数依赖及其推理规则

殷丽凤, 邱占芝

（大连交通大学 软件学院, 辽宁 大连 116028）

随着XML成为网络信息表示和交换的标准以及不确定数据的广泛存在,不确定XML数据库管理技术成为了当今研究的热点。基于粗糙集理论提出了XML信息系统模型、粗糙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数据库理论及应用。