不確定數(shù)據(jù)庫中Top-k查詢研究.pdf

1、在數(shù)據(jù)挖掘、傳感器網(wǎng)絡(luò)、數(shù)據(jù)檢索等應(yīng)用中產(chǎn)生了大量的不確定性數(shù)據(jù),它廣泛地存在于金融、軍事等領(lǐng)域中。不確定性數(shù)據(jù)帶給用戶的信息是不準(zhǔn)確的,但是如果直接丟棄或者清洗這些不精確的數(shù)據(jù),將會導(dǎo)致一些重要信息的丟失,所以必須對這些不確定性數(shù)據(jù)進(jìn)行有效地管理和存儲,從中找出有用的信息。不確定數(shù)據(jù)庫就是用于管理這些不確定性數(shù)據(jù)。
　　 Top-k查詢是查找出用戶最關(guān)心的前k個(gè)數(shù)據(jù),該查詢技術(shù)在傳統(tǒng)的關(guān)系型數(shù)據(jù)庫中得到了非常廣泛地應(yīng)用,它對精

2、確數(shù)據(jù)的Top-k查詢的語義是非常明確的,查詢出的結(jié)果也是精確無異議的。不確定性數(shù)據(jù)由于本身具有不確定性,不確定數(shù)據(jù)庫中的元組也具有可信度和元組規(guī)則這兩個(gè)特征,在Top-k查詢中,必須綜合元組的分值和概率值,它們共同決定T0p.k查詢的最終結(jié)果,故傳統(tǒng)的針對確定數(shù)據(jù)Top-k查詢不能夠直接應(yīng)用在不確定性數(shù)據(jù)上。研究者們提出了很多在不確定數(shù)據(jù)庫中實(shí)現(xiàn)Top-k查詢的算法,這些算法有不同的語義環(huán)境,而且它們沒有很好的綜合不確定性元組的分值和

3、概率值,查詢出來的結(jié)果也就不能更好地滿足用戶的需求。不確定數(shù)據(jù)庫中的Too-k查詢需要更進(jìn)一步的研究。
　　 本文首先研究分析了不確定性數(shù)據(jù)和不確定數(shù)據(jù)庫,對不確定性數(shù)據(jù)建模,在模型基礎(chǔ)之上,定義了針對不確定數(shù)據(jù)庫的Top-k查詢語義,該語義是明確不具有歧義性的。新語義下,查詢結(jié)果返回k個(gè)元組,在計(jì)算排名第I位的元組時(shí),把第i位概率值最大的元組和第I-1位概率值第二大的元組進(jìn)行比較,返回一個(gè)最優(yōu)的元組最為第i位的最終結(jié)果,這樣就

4、更好的權(quán)衡了不確定性元組的分值和概率值。此外,用戶才可以根據(jù)自己的需求定義一個(gè)閾值,返回的元組的概率值均大于閾值。新語義從根本上保證了該算法能很好的綜合了不確定性元組的分值和概率值,能夠更好的滿足用戶的需求。
　　 然后具體實(shí)現(xiàn)了算法。利用兩種優(yōu)化策略來對算法進(jìn)行優(yōu)化,避免了數(shù)據(jù)建模導(dǎo)致的可能世界空間實(shí)例的指數(shù)倍增長帶來的算法運(yùn)行時(shí)間過長問題,降低了訪問元組的深度,使算法效率更高。
　　 最后通過實(shí)驗(yàn)論證,證明了在不同的