綜合信息集成及查詢優(yōu)化的研究.pdf

1、隨著Internet技術(shù)的發(fā)展，Web上各種在線信息源不斷涌現(xiàn)，這些信息源種類繁多，結(jié)構(gòu)各異。在互聯(lián)網(wǎng)這樣一個(gè)動(dòng)態(tài)的環(huán)境中，各信息源不斷地發(fā)生著變化，在這樣一個(gè)動(dòng)態(tài)、異構(gòu)、開(kāi)放的環(huán)境下快速、準(zhǔn)確地獲取信息是十分困難的。因此，研究信息集成系統(tǒng)，為用戶提供一個(gè)訪問(wèn)異構(gòu)數(shù)據(jù)源的統(tǒng)一接口有著非常重要的意義。在這種背景下，本文對(duì)信息集成系統(tǒng)的主要技術(shù)進(jìn)行了深入的研究，具體研究工作如下： 信息集成系統(tǒng)體系結(jié)構(gòu)是研究系統(tǒng)的組成模塊以及各模塊之

2、間關(guān)系的。本文對(duì)目前幾種典型的信息集成系統(tǒng)體系結(jié)構(gòu)進(jìn)行了分析，總結(jié)了這些體系結(jié)構(gòu)的優(yōu)點(diǎn)和不足。在對(duì)實(shí)際的信息集成工作中遇到的問(wèn)題及其他相關(guān)需求進(jìn)行分析的基礎(chǔ)上，提出了綜合信息集成系統(tǒng)體系結(jié)構(gòu)。該體系結(jié)構(gòu)既考慮對(duì)已有投資的保護(hù)，又考慮對(duì)不斷生成的新數(shù)據(jù)的有效處理；既考慮對(duì)傳統(tǒng)數(shù)據(jù)庫(kù)中的數(shù)據(jù)和XML數(shù)據(jù)的處理，又考慮信息檢索和輔助決策的需求。是一個(gè)面向目前大多數(shù)企業(yè)的綜合信息集成系統(tǒng)。 模式映射的建立是信息集成系統(tǒng)的重要環(huán)節(jié)之一。本

3、文提出了基于劃分的映射模式發(fā)現(xiàn)框架——PBMSDF (Partition Based Mapping Schema Discovery Framework)。Dhamankar 等提出了iMAP框架，該框架采用搜索器集合和Beam Search的方法，可以自動(dòng)發(fā)現(xiàn)1：1映射、1：n和n：1的復(fù)雜映射，但是存在以下不足：一是不能發(fā)現(xiàn) m：n 的復(fù)雜映射；二是該框架需要對(duì)屬性及屬性值實(shí)例進(jìn)行分析，導(dǎo)致系統(tǒng)開(kāi)銷很大；三是對(duì)于Web信息集成，獲

4、取屬性值的數(shù)據(jù)實(shí)例有時(shí)是不可能的，因此該框架不能用于Web 信息集成。He 等提出了DCM(Dual Correlation Mining)框架，該框架采用對(duì)屬性在模式中的分布進(jìn)行分析發(fā)現(xiàn)屬性之間相關(guān)度的方法來(lái)發(fā)現(xiàn)屬性之間的映射關(guān)系，可以解決 iMAP 框架中存在的問(wèn)題，仍存在以下不足：一是由于該框架采用的相關(guān)度衡量標(biāo)準(zhǔn)對(duì)部分屬性的評(píng)價(jià)結(jié)果不準(zhǔn)確，導(dǎo)致發(fā)現(xiàn)結(jié)果準(zhǔn)確性不高；二是該框架中采用的AprioriCorrmining和DualCo

5、rrelationmining挖掘算法在由相關(guān)e項(xiàng)集生成相關(guān)e+1項(xiàng)集的過(guò)程中，將整個(gè)屬性集合中的每一個(gè)屬性添加到相關(guān)e項(xiàng)集中構(gòu)成候選相關(guān)e+1項(xiàng)集，然后再判斷該e+1項(xiàng)集是否相關(guān)，增加了許多不必要的計(jì)算，致使搜索空間過(guò)大，算法的效率較低。本文提出了比較適合于衡量屬性之間相關(guān)度的C-衡量標(biāo)準(zhǔn)，并在PBMSDF框架中采用了該標(biāo)準(zhǔn)以提高發(fā)現(xiàn)結(jié)果的準(zhǔn)確度；提出了基于劃分和棧的模式映射發(fā)現(xiàn)算法，理論分析和實(shí)驗(yàn)結(jié)果均證明，該框架較iMAP和DCM

6、具有較高的性能和較好的模式發(fā)現(xiàn)能力。 XML成為目前Web上數(shù)據(jù)表示和信息交換的標(biāo)準(zhǔn)，處理 XML 數(shù)據(jù)是集成系統(tǒng)的功能之一，XML 查詢的效率將直接影響集成系統(tǒng)的性能。本文提出了一種基于遞歸模式的XML查詢優(yōu)化算法。該算法對(duì)XML模式中的節(jié)點(diǎn)和XML文檔中的節(jié)點(diǎn)分別建立索引，并用模式節(jié)點(diǎn)編號(hào)建立模式中的節(jié)點(diǎn)與文檔中節(jié)點(diǎn)的關(guān)聯(lián)。查詢時(shí)先在XML模式中進(jìn)行查找，若無(wú)匹配結(jié)果，則無(wú)需在XML文檔中查找；否則也只需對(duì)XML文檔中與對(duì)X

7、ML模式查詢的結(jié)果節(jié)點(diǎn)編號(hào)相同的節(jié)點(diǎn)進(jìn)行篩選，大大減小了搜索空間。對(duì)具有遞歸模式的XML的查詢，先對(duì)查詢樹(shù)進(jìn)行去除重復(fù)元素的預(yù)處理，然后將查詢樹(shù)分解成主路徑和分支路徑，分別進(jìn)行查找。查詢過(guò)程中利用XML文檔節(jié)點(diǎn)索引以加快查詢速度。該方法可以減少連接操作的次數(shù)，提高查詢操作的效率，能處理較復(fù)雜的XML模式。多連接查詢是影響信息系統(tǒng)查詢效率的主要因素之一。本文提出了基于圖的多連接查詢優(yōu)化算法。該算法充分考慮與同一個(gè)關(guān)系相關(guān)的連接操作之間的相

8、互影響，首先確定與同一個(gè)關(guān)系相關(guān)的連接中結(jié)果關(guān)系最小的連接操作為優(yōu)先進(jìn)行的操作，再?gòu)倪@些優(yōu)先進(jìn)行的連接操作中選擇權(quán)重最小的執(zhí)行；實(shí)驗(yàn)證明，該算法較MVP算法、G<,MC>算法、G<,MR>算法和Improved-G<,MC>算法具有較好的性能。 屬性值的分布會(huì)對(duì)查詢計(jì)劃的執(zhí)行效率產(chǎn)生影響。本文充分考慮了模式中屬性值分布的不均勻性和屬性值之間的相關(guān)性對(duì)查詢結(jié)果的影響，給出了基于值的簡(jiǎn)單查詢優(yōu)化模型和帶連接操作的查詢優(yōu)化模型，并根據(jù)