基于連接操作的反輪廓查詢處理算法研究與實(shí)現(xiàn).pdf

1、信息是以數(shù)據(jù)的形式存儲(chǔ)在數(shù)據(jù)庫(kù)中。由于信息量的巨大，相關(guān)的數(shù)據(jù)大部分是建立在多個(gè)數(shù)據(jù)表上。因此，數(shù)據(jù)應(yīng)用中跨表的數(shù)據(jù)查詢變得十分普遍，這不可避免的涉及到了數(shù)據(jù)表的連接問題。但是現(xiàn)有的反輪廓查詢算法基本是針對(duì)于一個(gè)數(shù)據(jù)表的處理，而如果直接將數(shù)據(jù)表連接合并成一個(gè)數(shù)據(jù)表，再對(duì)其求在輪廓結(jié)果性能很低。因?yàn)樵谝话闱闆r下，只有少量的連接結(jié)果會(huì)成為最終的查詢結(jié)果，有很多的連接操作都是不必要的。所以本文對(duì)這一課題進(jìn)行了研究，對(duì)涉及到數(shù)據(jù)表連接操作的反輪

2、廓查詢處理問題進(jìn)行了細(xì)致的分析，提出了兩種刪減策略來(lái)有效的減少數(shù)據(jù)的訪問量，從而減少連接比較次數(shù)。本文設(shè)計(jì)的算法是將查詢分散在每個(gè)數(shù)據(jù)表上，對(duì)每個(gè)數(shù)據(jù)表分別進(jìn)行操作，而不是將數(shù)據(jù)表連接后再求反輪廓，這樣能夠很好的減少元組之間的連接次數(shù)，可以在很大程度上提高算法的查詢性能。貢獻(xiàn)點(diǎn)概括如下:
　　1.針對(duì)連接上的反輪廓查詢問題，提出了有效的解決方案。對(duì)數(shù)據(jù)表采用了網(wǎng)格結(jié)構(gòu)進(jìn)行索引，在此基礎(chǔ)上，提出兩種提前終止條件，以減少需要訪問的數(shù)據(jù)

3、點(diǎn)量，提前結(jié)束對(duì)整個(gè)數(shù)據(jù)集的訪問。并由給出相關(guān)概念、性質(zhì)和定理，證明了方法的正確性。基于此，得到基本反輪廓查詢算法(BRSJ)。
　　2.對(duì)BRSJ算法進(jìn)行分析改進(jìn)，提出改進(jìn)反輪廓連接算法(PRSJ)。算法PRSJ對(duì)比于BRSJ，將半支配操作提至連接操作之前，這樣可以提前判斷出連接之后一定不會(huì)成為結(jié)果的點(diǎn)，所以只進(jìn)行了必需的連接操作，就可以得到最終反輪廓連接結(jié)果?？梢赃M(jìn)一步減少數(shù)據(jù)點(diǎn)連接量。
　　3.通過實(shí)驗(yàn)驗(yàn)證了兩種提前終