數(shù)據(jù)庫模式匹配算法研究.pdf

1、模式匹配是模式間的一個二元操作，它以源模式和目標(biāo)模式為輸入，以兩個模式中元素(在關(guān)系型數(shù)據(jù)庫中對應(yīng)于關(guān)系的屬性)間的映射關(guān)系作為輸出。隨著數(shù)據(jù)庫應(yīng)用的越來越廣泛，模式匹配在越來越多的應(yīng)用領(lǐng)域中發(fā)揮著重要的作用，例如：模式集成、數(shù)據(jù)倉庫、電子商務(wù)、語義WEB和P2P數(shù)據(jù)庫等領(lǐng)域。以往的模式匹配操作大都由操作人員手工完成，這是一個費(fèi)時、費(fèi)力且易出錯的過程，所以自動模式匹配算法的研究是目前一個研究熱點(diǎn)。目前對模式匹配問題的研究成果比較豐富，已

2、有的研究成果主要利用元素自身信息(如元素名、數(shù)據(jù)類型等信息)、數(shù)據(jù)實(shí)例信息(模式中的數(shù)據(jù))和結(jié)構(gòu)信息(模式元素相互關(guān)聯(lián)的關(guān)系)來挖掘模式語義以獲得正確的元素映射關(guān)系。但多數(shù)研究成果都主要利用元素自身信息計(jì)算元素之間的相似度，并根據(jù)相似度選取映射關(guān)系。已有的匹配算法主要存在如下一些不足，首先，利用的元素對應(yīng)的數(shù)據(jù)實(shí)例信息和元素間的結(jié)構(gòu)信息不足，信息不夠全面，從而導(dǎo)致匹配結(jié)果的準(zhǔn)確度不高；其次，已有的算法針對目標(biāo)模式中的每個元素，在源模式的

3、全局范圍內(nèi)搜索其候選匹配元素，搜索范圍大，干擾選項(xiàng)多，匹配結(jié)果不夠準(zhǔn)確；另外，由于已有匹配算法都是基于啟發(fā)式算法，所以對輸出的任意一個匹配結(jié)果都無法完全確定其正確性。
　　 根據(jù)模式匹配研究成果的不足之處，在已有的研究基礎(chǔ)上，我們針對模式匹配問題做了如下一些研究工作：
　　 將模式元素間的相似度分為語義相似度(根據(jù)元素自身信息得到的相似度)和結(jié)構(gòu)相似度(根據(jù)元素之間的關(guān)聯(lián)關(guān)系得到的相似度)，并采用新的統(tǒng)計(jì)方法計(jì)算元素間的

4、結(jié)構(gòu)相似度，然后利用相似概率的概念將結(jié)構(gòu)相似度和語義相似度綜合；最后根據(jù)相似概率得到模式元素間的映射關(guān)系(模式元素之間的對應(yīng)關(guān)系)。該方法是一種利用元素間的結(jié)構(gòu)信息來輔助模式匹配的新方法。
　　 首先根據(jù)模式對應(yīng)的數(shù)據(jù)實(shí)例信息來計(jì)算模式元素間的部分函數(shù)依賴度(模式結(jié)構(gòu)信息)，然后根據(jù)部分函數(shù)依賴關(guān)系建立模式元素間的依賴圖，再根據(jù)元素依賴圖計(jì)算元素間的結(jié)構(gòu)相似度，最后得到模式元素間的映射關(guān)系。由于利用了更多的結(jié)構(gòu)信息輔助匹配，所以

5、該方法在性能上要優(yōu)于其它僅使用完全函數(shù)依賴結(jié)構(gòu)信息進(jìn)行匹配的方法。這是一種將數(shù)據(jù)實(shí)例信息與結(jié)構(gòu)信息相結(jié)合來輔助匹配的新方法。
　　 將模式中的元素按照描述對象的不同劃分為不同的元素塊，然后利用信息檢索領(lǐng)域中的經(jīng)典算法TF/IDF對源模式和目標(biāo)模式中的元素塊進(jìn)行匹配，最后利用已有的模式匹配算法在相互匹配的模式塊之間進(jìn)行元素匹配。因?yàn)楫?dāng)模式中含有較少的元素時，已有的算法能夠取得較好的匹配效果，所以利用本方法對大型模式進(jìn)行分塊匹配能取