多维不确定性XML数据模型的研究

2013-07-22乐嘉锦姜久雷

计算机工程与应用 2013年23期

关键词：概率模型数据模型文档

王艳，乐嘉锦，姜久雷，张云

1.东华大学旭日工商管理学院，上海 200061

2.上海海洋大学信息学院，上海 201306

3.东华大学计算机科学与技术学院，上海 201620

多维不确定性XML数据模型的研究

王艳1，2，乐嘉锦3，姜久雷1，张云2

1.东华大学旭日工商管理学院，上海 200061

2.上海海洋大学信息学院，上海 201306

3.东华大学计算机科学与技术学院，上海 201620

1 引言

近年来，大量技术被应用于海量数据的存储和记录，但是在很多情况下，数据本身存在错误或者不完整性，同时数据的源事件也是存在大量不确定性。

在数据库领域对于不确定信息而言，最早是文献[1]提出一种概率关系数据模型PRM及其关系代数，并在研究中用系统的观点阐述了概率数据库的有关理论，奠定了在数据库中应用概率论来处理不确定信息的基础。

后来，不确定的数据模型也被扩展到半结构化的XML数据。XML概率模型具备XML的灵活性，可以很自然地表示多个粒度的概率信息，乃至嵌套的概率信息；另外XML以其自描述性好与可扩展性高的优点，特别适用于信息抽取与数据集成等可能产生大量不确定信息的应用。

文献[2]提出的P文档模型（ProDB）是最早的概率XML数据模型，该模型描述节点的概率以父节点存在为前提，提出兄弟节点之间关系为相对独立（ind）和相互排斥（mux）。文献[3]和文献[4]均扩展了P文档模型，其中文献[4]对原有的P文档模型的边增加了外部约束条件，利用约束条件来限制节点出现概率。文献[5]对P文档模型给出了高效的查询算法。文献[6]提出了一种XML概率树模型，该模型给各节点附加一系列事件变量，由外部事件的发生的概率决定节点的存在性，增加了数据表示的灵活度。文献[7]对概率树模型进一步分析了查询复杂度。文献[8]提出了PXML模型，该模型是以有向图为基础的概率半结构数据模型，把概率实例定义为半结构实例及其对应的概率值。文献[9]提出了以概率区间值表示PXML的数据模型。文献[10]提出的概率树模型以及文献[11]提出的PrXML模型等对概率模型进行了进一步的扩充。

现有的XML概率模型在表达方式和表达效率上不断演进，但是由于一直在单维空间进行表述，所以在描述复杂事件时依然存在一定缺陷。本文在目前已有的XML概率模型的基础上，以建立描述多维复杂事件的概率数据模型为目标，建立一种新的关联事件概率模型，并且提出了多维不确定概率模型空间的概念，从而使系统能对多个概率模型进行统一建模，并把单维XML概率节点引申到多维空间，进而定义了统一的空间查询方式，从而优化了复杂事件的概率数据建模和查询方法。

2 关联事件概率模型

2.1 两种经典概率模型

半结构化数据模型的出现，解决了不确定数据在无严格模式结构情况下的描述问题。在管理概率半结构化数据的方法基础上，出现了直接以文档树形式描述的p-文档模型[2]。如图1所示，p-文档模型以文档树的边作为概率属性的载体，各个节点的概率依附于上一级的概率，同时对于同层次节点之间，使用互斥或者独立关系作为描述。节点和边的数目决定了计算概率的工作量。

图1 p-文档模型结构图

在计算节点概率的时候，按照下式：

得到C节点的概率，同样D节点的概率也可由公式（1）得到：

其中等式右边的值可以从原XML文档得到。所以计算某个元素e∈A，A为某个定义的子图，只需要计算公式（2）：

其中n为从e节点到root节点r的所有路径上的节点数目。

考虑了事件驱动后的概率树模型[6]在各节点附加一系列外部事件变量，由外部事件的发生与关联决定节点的存在性。按照概率树的定义，数据树t是一个4元组t=(A，E，r，φ)，A是一个节点有限级，E⊆A2，是以rootr∈A为起点的数据树。φ作为字符串组对应的节点label标示。假设t=(A，E，r，φ)，t′=(A′，E′，r′，φ′)。可以说t和t′同构。假设有W作为有限事件变量级，存在概率条件为w或者-w， w∈W 。对于概率树的定义T为4元组(t，W，π，Y)，t=(A，E，r，φ)是数据树，π以W 的某种概率分布，Y分配概率条件到节点A-{r}。图2是一个具体的概率树模型结构图，概率树模型作为事件驱动的模型，它并不在各节点边上附加概率值来描述不确定性，而是由事件的发生与否决定节点的存在性。

图2 概率树模型结构图

图2共有2个外部事件w1和w2，其发生概率分别为0.7和0.8。节点B出现的前提条件是事件w1发生且事件w2不发生；节点E存在的前提条件是事件w2发生。由于节点B与E的存在条件互斥，不存在同时包含节点B、E的子图。包含且仅包含 A、C、D 3个节点的子图的概率为：(1-0.8)×(1-0.7)-0.06，前提是w1、w2均不发生。

2.2 关联事件有向图概率模型定义

本文定义了一种概率有向图模型，同时兼顾了前面描述的两种经典模型的优点，并且扩展了表述概率事件的复杂度，从而提高了模型的表述能力。

定义1数据有向图 f是一个4元组，表述为 f=(S，E，p，φ)，其中S是节点的有限集合，E⊆S2，作为节点有向图，概率关系矩阵 p定义了所有节点的关系，φ标示了有限节点集合的字符串。

对于概率矩阵 p的定义为 pij=(ei-＞ej)节点i指向节点j的关联概率，如果有A、B、C、D四个节点，形成的概率关系矩阵如公式（3）所示：

如果其中存在不相关的节点对，使用0表示。

对于某个节点B的概率Prob(B)，可以看作与之关联的有向标识的集。

图2的概率树模型变换为如下关联事件图3，对于 A出现，B必然出现的节点关系，使用单向箭头表示，把依存概率作为边，对于C出现，B不出现，概率为 -1，箭头的方向表示作用关系。不同节点通过外部事件关联，如图3所示。

计算节点B的概率，先确定有向标示的起点概率和标示概率的极性，然后计算。图4中B节点的概率为：

其中前面的Prob(A)，(1-Prob(C))，Prob(D)组成关联概率，Prob(Wb)是内在节点事务驱动概率。

图3 关联事件概率模型结构图

图4 B节点的关联事概率拓扑

所以，任何一个节点概率e可以由公式（4）计算为：

对于关联事件有向图概率模型，很明显每个节点的关系从树变成网，同时保留了外部驱动事件的影响。所以表述能力得到了提升，可以对更加复杂的概率数据进行描述。

3 多维XML概率模型空间定义与查询

关联事件的概率模型和其他概率模型均可以在多维平面展开，形成对于多维事件驱动的概率表述，从而极大地扩展了其复杂性。

定义2对任何一个节点的概率，有一个n维概率坐标表示，(P1，P2，…，Pn)，其中对于每一个坐标，表示在某一个该节点所在概率空间的概率坐标。对于该节点的概率，可以看作是在n维概率空间的某个点。

如果O(i)表示某个节点的概率坐标的维度。如果i点有4个坐标点，表示坐标维度为4，如果4维坐标的其中一个坐标值为1，O(i)=O(i-1)，出现降维事件。

对于每个概率空间，存在某一个概率模型，表示该节点的位置。假设Mi是第i维空间概率坐标形成的模型，Mj是第 j维空间概率坐标形成的模型，如果Mi∩Mj=0，则称为 Mi正交于Mj，其中∩操作表示两个模型的节点之间关系∩，或者说两个模型非联通。如果 Mi非正交于Mj，则称为节点i所处的概率空间存在联通性。需要通过联通关系裁剪概率空间，保证正交，或者降低坐标维度。

关联事件模型M1和p文档模型M2对每个点的概率模型叠加，如图5所示。

图5 多维概率模型叠加结构图

对于每一个节点的概率坐标Pnode=(Pp，Pw)，其中Pp是由P-文档模型定义的，Pw由概率树事件定义。

在引入多维概率模型以后，进而描述多维空间的操作运算和关于节点的概率坐标的几个延伸，如下定义。

定义3对某个节点的概率坐标，形成坐标向量Pi，定义坐标概率权重向量：

K'i，Pi作为权重因子以后的节点概率坐标。对于正交模型空间的节点 X每个坐标 pi，如果存在一个时间函数，在t时刻，发生关系，假设存在函数 F(t，pi)，在t时刻，坐标 pi可以映射到 pj上，则称为概率模型i和 j在节点X上存在时间滑动映射关系，pj=F(t，pi)，其中F为时间滑动概率函数，对于实际世界，不同的概率模型在某个节点是存在某种关联的，∃t，pj=F(t，pi)，则概率模型空间i和 j是可以一一映射的，同时O(i)=O(i-1)，存在降维事件。

下面对于关联事件概率模型与概率模型空间进行查询研究。首先定义查询类型。对于关联事件概率模型，作为网状关联模型，需要给出并且评估有效的查询方法。为了定义一种查询方式，首先定义子关联图的概念：

定义4有 f=(S，E，p，φ)和 f′=(S′，E′，p′，φ′)两个关联事件图，如果有：

对于具有多维概率坐标的节点，首先获得正交概率空间，得到Omin。

对每个空间实施Qi(e)函数，获得全部维度的查询信息。

对概率世界的查询可以表示为：

其中S={(ti，pi)}，作为PW集。

在多维概率模型以及概率模型的引申定位，从空间上统一了多种概率模型。对于节点的多模型多概率定义创造性地给出了统一建议，使得表述和兼容性在多维度下统一，也就是在兼容性和统一性上有很大改善和提升。

多维概率模型对于查询的复杂度并不能降低，而是在于表述能力的提升。需要指出的是在降维操作之后的查询复杂度才是最终的可度量查询复杂度。对于复杂度本身可以同样适用矩阵和向量表示。

4 多维概率模型实例分析

以某大学人事数据为例。图6列出了一个2维概率模型的实例。可以看到，在维1（黑影部分），通过类似P-文档模型结构表示了某大学人事数据概率模型各个节点的关系。而对于维2（灰色部分），是同样节点的外部概率事件模型。对于每个节点，存在二维概率值，例如对于salary value的划分概率，不只是由工资级别决定的，同时与职位存在外部事件关联。

图6 多维概率模型实例

在假设的概率关系中得到一个节点二维矩阵如下：

同时该二维数存在W1节点子集存在维度降低，为1维概率节点集：

存在W0节点子集存在更大的维度减低，为0维概率节点集：

剩余的子集为2维节点子集W2，由此可以将W形成3类矩阵进行计算，3类矩阵的计算复杂度一次增加。

可见同一节点由于存在多重空间表示，表述性必然增加。但是降维以后的操作和查询复杂度是由节点本身的关联复杂度导致的。随后对二维空间的每个维度概率节点，可以实施前文定义的多维查询函数，获得全部维度的查询信息。多维查询函数是在之前多维模型的同步维度扩展，并不作为重点在本文描述。

在本实例中可见二维查询函数存在一个可优化之处。对于每个模型通常是既定的，并没有考虑正交性，也很难进行正交分解，所以在非正交化概率模型间的查询效率简化是值得进一步研究的。

5 结束语

随着计算机与网络技术的蓬勃发展，海量的数据展现在人们面前，大量的不确定数据需要有高效的管理，并且要能为用户提供方便、有效、真实的查询，概率则恰是表示不确定信息的一种常用方式，因此对概率数据模型进行研究有着很重要的应用价值。

本文描述了一种XML关联事件概率数据模型，能够描述较为复杂的概率数据模型并提出概率模型空间的概念和查询，使系统能够使用多个概率模型进行建模，把每个XML概率节点引申到多维空间，进而定义了统一的查询方式，为复杂概率数据建模和查询优化提供了一种新颖的理论方法。

后续多维概率模型的维度正交化研究以及在非正交性的既定概率模型下的最大查询简化方法研究，是下一步的研究工作。

[1]Dey D，Sarkala S.A probabilistic relational model and algebra[J].ACM Transactions on Database Systems，1996，21（3）：339-369.

[2]Nierman A，Jagadish H V.ProTDB：probabilistic data in XML[C]// Proceedings of 28th International Conference on Very Large Data Bases，2002：646-657.

[3]Kimelfeld B，Sagiv Y.Matching twigs in probabilistic XML[C]// VLDB’07，Vienna，Austria，2007：27-38.

[4]Cohen S，Kimelfeld B，Sagiv Y.Incorporating constraints in probabilistic XML[C]//Proceedings of the 27th ACM SIGMODSIGACT-SIGART Symposium on PrinciplesofDatabase Systems，Vancouver，2008：109-118.

[5]Souihli A，Senellart P.Efficient query evaluation over probabilistic XML with long-distance dependencies[C]//Proceedings of the 2011 Joint EDBT/ICDT Ph.D.Workshop，Sweden，2011：32-37.

[6]Abiteboul S，Senellart P.Querying and updating probabilistic information in XML[C]//10th InternationalConference on Extending DatabaseTechnology，Munich，Germany，2006：1059-1068.

[7]Senellart P，Abiteboul S.On the complexity of managing probabilistic XML data[C]//Proceedings of the 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems，Beijing，2007：283-292.

[8]Hung E，Getoor L，Subrahmanian V S.PXML：a probabilistic semistructured data modeland algebra[C]//Proceedingsof the 19th International Conference on Data Engineering（ICDE），2003：467-478.

[9]Hung E，Getoor L，Subrahmanian V S.Probabilistic interval XML[J].ACM Transactions on Computational Logic，2007，8（4）.

[10]van Keulen M，de Keijzer A，Alink W.A probabilistic XML approach to data integration[C]//Proceedings ofthe 2lst IEEE International Conference on Data Engineering，Tokyo，2005：459-470.

[11]Kimelfeld B，Kosharovsky Y，Sagiv Y.Query efficiency in probabilistic XML models[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data，Vancouver，2008：701-714.

WANG Yan1，2,LE Jiajin3,JIANG Jiulei1,ZHANG Yun2

1.Glorious Sun School of Business and Management,Donghua University,Shanghai 200061,China
2.College of Information Technology,Shanghai Ocean University,Shanghai 201306,China
3.School of Computer Science and Technology,Donghua University,Shanghai 201620,China

Uncertainty of mass data storage and recording and the extensive application of XML in the extension make that the XML association event probability data model has become a hot topic.Based on the existent probability models,this article describes the complex event probabilistic data model,and puts forward the conception of multidimensional uncertainty probability model space.Furthermore,the paper unifies modeling of multiple probability models,and extends the single dimension XML probability node to multidimensional space,and then defines the uniform spatial query,provides a new theory method of modeling and query optimization of complex probabilistic data model.

Extensive Markup Language（XML）;uncertainty;multi-dimensional space;probability model;related events

不确定海量数据存储与记录的广泛应用及其在XML上的扩展，使XML的关联事件概率的数据模型研究成为研究热点，以描述复杂事件的概率数据模型为目标，在当前已有概率模型的基础上，提出了多维不确定概率模型空间的概念，基于多个概率模型进行统一建模，并把单维XML概率节点引申到多维空间，进而定义了统一的空间查询方式，为复杂概率数据建模和查询优化提供了一种新颖的理论方法。

可扩展标示语言（XML）；不确定性；多维空间；概率模型；关联事件

TP309.2

10.3778/j.issn.1002-8331.1203-0174

WANG Yan,LE Jiajin,JIANG Jiulei,et al.Research on multi-dimensional uncertainty data model based on XML.Computer Engineering and Applications,2013,49（23）：91-94.

上海市科学技术委员会专项基金资助项目（No.11510501300）。

王艳（1978—），女，博士研究生，讲师，主要研究方向：信息管理与信息系统、数据挖掘等。E-mail：yanwang@shou.edu.cn

2012-03-07

2012-05-21

1002-8331（2013）23-0091-04

CNKI出版日期：2012-07-16 http://www.cnki.net/kcms/detail/11.2127.TP.20120716.1501.040.html