概率數(shù)據(jù)庫(kù)可擴(kuò)展查詢技術(shù).pdf

1、隨著信息化進(jìn)程的推進(jìn)，在信息檢索、模糊物體匹配、數(shù)據(jù)集成、傳感器網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等應(yīng)用領(lǐng)域存在著大量的不確定數(shù)據(jù)。然而傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)只能處理確定的數(shù)據(jù)，對(duì)于概率數(shù)據(jù)的查詢處理顯得力不從心。因此，如何高效地實(shí)現(xiàn)概率數(shù)據(jù)查詢處理的問(wèn)題成為現(xiàn)階段數(shù)據(jù)庫(kù)系統(tǒng)一個(gè)嶄新的問(wèn)題，這促進(jìn)了概率數(shù)據(jù)庫(kù)理論與技術(shù)的研究。
　　近年來(lái)，概率數(shù)據(jù)庫(kù)領(lǐng)域的熱點(diǎn)問(wèn)題一直集中在概率數(shù)據(jù)庫(kù)的數(shù)據(jù)表示模型以及高效查詢算法上。BIDL(Block Indenpent

2、 Disjiont with Lineage)模型在BID(Block Indenpent Disjiont)模型的基礎(chǔ)上加入世系信息lineage。世系信息不僅可以記錄數(shù)據(jù)的來(lái)源，而且可以方便用戶提供反饋信息。概率數(shù)據(jù)庫(kù)的基礎(chǔ)查詢算法總體上分為兩類，即基于語(yǔ)義(intensional)的查詢算法和基于擴(kuò)展(extensional)的查詢算法。前者可以保證結(jié)果的準(zhǔn)確性，但是計(jì)算復(fù)雜度很高。然而，基于擴(kuò)展的查詢算法查詢速度相對(duì)較快，但是不

3、能保證查詢結(jié)果的準(zhǔn)確性。ST(Split Tuple)算法首先基于世系信息 lineage進(jìn)行概率推理，并深入分析元組間的關(guān)系，其次通過(guò)拆分相應(yīng)的元組，從而使元組間的關(guān)系進(jìn)一步清晰和易處理，然后采取有效的概率計(jì)算策略以及高效的概率計(jì)算算法執(zhí)行查詢，最后將查詢結(jié)果以及對(duì)應(yīng)的概率值返回給用戶。基于世系信息的概率推理具有一定的可擴(kuò)展性。
　　高級(jí)查詢算法包括Top-k、Skyline、K近鄰(K Nearest Neighbors)、軌