论文部分内容阅读
在数据挖掘、传感器网络、数据检索等应用中产生了大量的不确定性数据,它广泛地存在于金融、军事等领域中。不确定性数据带给用户的信息是不准确的,但是如果直接丢弃或者清洗这些不精确的数据,将会导致一些重要信息的丢失,所以必须对这些不确定性数据进行有效地管理和存储,从中找出有用的信息。不确定数据库就是用于管理这些不确定性数据。Top-k查询是查找出用户最关心的前k个数据,该查询技术在传统的关系型数据库中得到了非常广泛地应用,它对精确数据的Top-k查询的语义是非常明确的,查询出的结果也是精确无异议的。不确定性数据由于本身具有不确定性,不确定数据库中的元组也具有可信度和元组规则这两个特征,在Top-k查询中,必须综合元组的分值和概率值,它们共同决定Top-k查询的最终结果,故传统的针对确定数据Top-k查询不能够直接应用在不确定性数据上。研究者们提出了很多在不确定数据库中实现Top-k查询的算法,这些算法有不同的语义环境,而且它们没有很好的综合不确定性元组的分值和概率值,查询出来的结果也就不能更好地满足用户的需求。不确定数据库中的Top-k查询需要更进一步的研究。本文首先研究分析了不确定性数据和不确定数据库,对不确定性数据建模,在模型基础之上,定义了针对不确定数据库的Top-k查询语义,该语义是明确不具有歧义性的。新语义下,查询结果返回k个元组,在计算排名第i位的元组时,把第i位概率值最大的元组和第i-1位概率值第二大的元组进行比较,返回一个最优的元组最为第i位的最终结果,这样就更好的权衡了不确定性元组的分值和概率值。此外,用户才可以根据自己的需求定义一个阈值,返回的元组的概率值均大于阈值。新语义从根本上保证了该算法能很好的综合了不确定性元组的分值和概率值,能够更好的满足用户的需求。然后具体实现了算法。利用两种优化策略来对算法进行优化,避免了数据建模导致的可能世界空间实例的指数倍增长带来的算法运行时间过长问题,降低了访问元组的深度,使算法效率更高。最后通过实验论证,证明了在不同的数据集上,该算法是有效的、具有可行性。