【ZK75页】毕业论文：基于DRA的不确定数据的查询研究.doc文档完稿

可能世界模型，是最早被提出来的，之后的很多处理模型和查询算法都是在可能世界模型的基础上提出的。

些研究人员根据不同的数据特点，提出了相应的处理模型，用于处理拥有些数据结构特性的不确定数据，比如滑动窗口模型是针对随时间快速流动的数据流数据所提出的处理模型，当数据随着时间的变化，以流数据的形式快速产生时，可能世界模型产生的可能世界实例的数目将会非常大，而滑动窗口模型只处理窗口内的，部分内容简介，哈尔滨工程大学硕士学位论文第章绪论引言研究背景及意义论文工作论文的组织及内容安排第章不确定数据的介绍不确定数据产生的原因不确定数据的概念和特点不确定数据的不确定性属性值的不确定性存在性的不确定性不确定数据元组之间的关系元组之间相互元组之间存在定关系本章小结第章不确定数据的处理模型及存在的问题可能世界模型关系型数据模型流数据模型多维数据模型可能世界模型存在的问题排序的方法剪枝的方法本章小结第章基于的不确定数据查询现有的不确定数据查询哈尔滨工程大学硕士学位论文思想的来源和查询基于的不确定数据查询基于的查询基于的查询基于的查询基于的不确定数据查询本章小结第章实验与结果分析实验环境实验数据实验结果本章小结参考文献结论攻读硕士学位期间发表的论文和取得的科研成果致谢第章绪论第章绪论引言由于，和无线传感器等技术的快速发展和大量应用，不确定数据已经对人们的生活产生了重大影响，由于不确定数据元组存在个到之间的数字来表示其不确定性，使很多有关传统的确定性数据的处理方法不能够用于处理不确定数据，急切需要提出新的方法来处理大量的不确定数据。

自上个世纪八十年代末，和提出有关不确定数据和可能世界的理论后，就有不少学者开始关注这种含有不确定概率值的新型数据。

年以后，随着不确定数据出现的越来越多，数据库领域的研究人员对此也产生了极大的兴趣，并推动了社会各界对不确定数据的关注和研究。

目前，已经有很多文献对不确定数据的处理模型和查询算法进行了研究。

可能世界模型，是最早被提出来的，之后的很多处理模型和查询算法都是在可能世界模型的基础上提出的。

些研究人员根据不同的数据特点，提出了相应的处理模型，用于处理拥有些数据结构特性的不确定数据，比如滑动窗口模型是针对随时间快速流动的数据流数据所提出的处理模型，当数据随着时间的变化，以流数据的形式快速产生时，可能世界模型产生的可能世界实例的数目将会非常大，而滑动窗口模型只处理窗口内的元组，这些元组由窗口的大小和窗口滑动的位置决定，这样就大大减少了要处理的不确定数据元组的数量。

在众多的处理模型被提出的同时，也有不少查询方法根据不同的语义和应用背景被明确定义下来。

比如查询和查询查询就是要查询不确定数据中分值最高的个元组，由于在不确定数据中每个元组都存在不确定性，因此对于不确定数据的查询处理不能像在传统的确定性数据库中那么简单，不仅要考虑分值的大小，还要考虑到元组的不确定性查询原本是用于研究多目标优化的问题，是属于确定性数据库的研究范畴，但近年来由于可能世界模型的影响力越来越大，文献也把查询引入到不确定数据的研究中来。

本文所研究的问题就是如何基于可能世界模型更加高效的处理存在性不确定数据的查询问题，由于存在性不确定数据产生的可能世界实例的数目会随着数据量的增长呈现出指数级的增长，这样当数据量比较大时，就无法得到所有的可能世界实例，也无法得到正确的查询结果。

目前已经有不少文章针对这个问题和不同的查询方法给出哈尔滨工程大学硕士学位论文了比较好的解决办法，本文工作就是在这些方法的基础上提出了改进，进步降低了时间复杂度和空间复杂度，提高了搜索的效率。

研究背景及意义最近几年集合。

由于是的控制节点，根据定义有，则有，因此有。

进步得到，则向量，比哈尔滨工程大学硕士学位论文，更有资格成为的查询结果，这与，是查询结果矛盾，故原定理结论正确，证毕。

定理对于个具有元组存在性不确定的数据库，如果个元组被其他个元组控制，并且查询结果要求阈值大于时，元组定不会成为不确定数据的查询结果。

证明设元组至少有个控制元组，为包含且排在前个位置的个可能世界实例，集合为数据库中所有元组的集合，为那些包含，且排在前位的可能世界实例集合，为的概率，则在这个可能世界实例中不可能包含的所有个控制节点，定存在个的控制节点不在这个可能世界实例中，则有排在前个位的可能世界实例概率之和为，是集合中所有元组产生的所有可能世界实例的集合。

因为，所以，当时，取最大值，即，又由于是个可能世界实例的概率，该可能世界实例不包含，同时不包含的个控制元组，而这个可能世界实例又是数据库中所有元组组成的可能世界实例中的个，中所有元组构成的可能世界实例概率的和为，因此有所以因此，如果查询阈值大于时，元组定不会成为的查询结果，定理证毕。

第章基于的不确定数据查询定理对于个具有元组存在性不确定的数据库，如果个元组被其他个元组控制，那么元组定不会成为不确定数据的查询结果。

证明设元组至少有个控制元组，为的其中个控制节点，为包含且排在前个位置的个可能世界实例，则只有两种情况第种情况，可能世界实例中同时含有和，他们都排在前个位置上。

第二种情况，可能世界实例中只包含，不包含，则我们可以用替换，保持其他元组不变，从而得到了个对应的包含不包含的可能世界实例。

设为元组和元组同时出现在前位的可能世界实例的集合，是元组出现在前位不在前位的可能世界实例的集合，为中的可能世界实例中，用替换后产生的对应的可能世界实例的集合，为元组成为查询结果的概率值，为元组成为查询结果的概率值，为数据库中所有元组的集合，为中所有元组的集合，为中所有元组的集合，由于和都出现在中的可能世界实例的前位，所以下面两式的前半部分是样的。

由于中的可能世界实例和中的对应，对应的可能世界实例中只有和不同，其他元组都是样的，即，所以在下面两式中，和是相等的，已知，所以，，中每个的概率值都小于中对应的把中的替换为，其他元组保持不变的概率值，所以，，可见比更有可能成为的查询结果，而由于已经有个元组能够控制，都比成为的概率大，故不可能成为的查询结果，定理正确，证毕。

那么根据以上四个定理，我们可以得出这样个结论对于个具有元组存在性不确定并且还有个属性值是有序的数据库，做不确定数据的和查询时，结果集合是个包含有个元组的集合，分别是和，那么定有，哈尔滨工程大学硕士学位论文。

这是因为除了以外的中其他的元组都必然被个以上的元组所控制，而这些被个以上元组所控制的元组是不可能成为和的查询结果的，所以这些查询得到的结果集合定属于，而定理又证明了，所以也定有，。

对于查询时，如果查询阈值大于时，控制集合之外的元组也不可能成为查询结果，若的查询结果集合为，也同样定有。

最终，我们可以只需要在或者上做查询即可，这样会大大减少需要查询的元组的数量并减少了在查询过程中构建的可能世界实例的数目。

基于的不确定数据查询这章描述了本文是如何利用元组之间的控制关系来快速处理不确定数据的查询。

为了清晰的展现出这种处理对查询起到的作用，这章在现有方法的基础上用实例说明这种处理给查询带来的好处。

基于的查询表相互的不确定数据元组对于表中所示的数据表，若有这样个查询，如按照查询定义计算，该表应先生成个可能世界实例，并对每个可能世界实例中的前个元组进行计算，显然复杂度很大。

现有方法是把元组按照值进行排序，即。

然后在按照分值排序后的元组上进行查询，访问顺序和产生可能世界实例的过程如图所示先访问元组，此时产生两个可能世界实例，是产生的可能世界实例中包含的元组的数目，是产生的可能世界实例中包含的元组，是相应的可能世界实例的概率值，是不包含已经访问到得元组，即中没有元组。

现有方法在查询时，判断包含个元组的可能世界实例的概率值，对于，现有方法只需要访问两第章基于的不确定数据查询个元组，即图中给出的和。

当访问到元组时，为，的可能世界实例的概率值是，这个可能世界实例的概率值是图中所有为的可能世界实例访问图中红色加粗字体标示，该例中只有个中最大的，而为的可能世界实例中概率值最大的可能世界实例是，概率值是，若是继续访问后面的元组并扩展现有的可能世界实例，那么得到新的为的可能世界实例的概率值定小于等于即使新的元组的概率值为，新得到的为的可能世界实例的概率值为，由于，所以此时还不能够判断出，是否为查询结果，还需要继续扩展后面的元组。

这时产生的可能世界实例的数目为，继续扩展为个，复杂度也很大。

分类号密级编号工学硕士学位论文基于的不确定数据的查询研究硕士研究生魏小艳指导教师张志强教授学科专业计算机软件与理论论文主审人谢晓芹副教授哈尔滨工程大学年月分类号密级编号工学硕士学位论文基于的不确定数据的查询研究硕士研究生魏小艳指导教师张志强教授学位级别工学硕士学科专业计算机软件与理论所在单位计算机科学与技术学院论文提交日期年月论文答辩日期年月学位授予单位哈尔滨工程大学哈尔滨工程大学学位论文原创性声明本人郑重声明本论文的所有工作，是在导师的指导下，由作者本人完成的。

有关观点方法数据和文献的引用已在文中指出，并与参考文献相对应。

除文中已注明引用的内容外，本论文不包含任何其他个