基于部分函數(shù)依賴的結(jié)構(gòu)匹配方法

1、 基于部分函數(shù)依賴的結(jié)構(gòu)匹配方法本文工作受國家高技術(shù)863計(jì)劃（項(xiàng)目編號(hào)：2007AA01Z309）、國家自然科學(xué)基金（項(xiàng)目編號(hào)：60873030）、國防預(yù)研基金（項(xiàng)目編號(hào)：9140A04010209JW0504、9140A15040208JW0501）及中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助的資助。E-mail:guohuili, hustdxkun 李國徽1） 杜小坤1） 杜建強(qiáng)2） 1）（華中科技大學(xué)計(jì)算機(jī)學(xué)院 武漢430074） 2）（江西中醫(yī)學(xué)院計(jì)算學(xué)院 南昌 330006）摘要 模式匹配是模式集成、數(shù)據(jù)倉庫、電子商務(wù)以及語義查詢等領(lǐng)域中的一個(gè)難點(diǎn)。它主要利用元素自身信息（如元素名、數(shù)據(jù)

2、類型等信息）、數(shù)據(jù)實(shí)例信息（模式中的數(shù)據(jù)）和結(jié)構(gòu)信息（模式元素相互關(guān)聯(lián)的關(guān)系）來挖掘元素語義以獲得正確的映射關(guān)系。本文介紹了一種將數(shù)據(jù)實(shí)例信息與結(jié)構(gòu)信息相結(jié)合來輔助匹配的新方法。本方法首先根據(jù)模式對(duì)應(yīng)的數(shù)據(jù)實(shí)例信息來計(jì)算模式元素間的部分函數(shù)依賴度（模式結(jié)構(gòu)信息），然后根據(jù)部分函數(shù)依賴關(guān)系建立模式元素間的依賴圖（圖3），再根據(jù)元素依賴圖計(jì)算元素間的結(jié)構(gòu)相似度，最后得到模式元素間的映射關(guān)系。由于利用了更多的結(jié)構(gòu)信息輔助匹配，所以本方法在性能上要優(yōu)于其它僅使用完全函數(shù)依賴結(jié)構(gòu)信息進(jìn)行匹配的方法。實(shí)驗(yàn)表明本方法在查準(zhǔn)率、查全率以及全面性等各個(gè)指標(biāo)上都優(yōu)于已有的其它方法（圖8、圖9）。關(guān)鍵字 模式匹配，

3、部分函數(shù)依賴，結(jié)構(gòu)匹配中圖法分類號(hào) TP311.1311引言模式匹配是模式間的一個(gè)二元操作，它以源模式和目標(biāo)模式為輸入，以兩個(gè)模式中元素（在關(guān)系型數(shù)據(jù)庫中對(duì)應(yīng)于關(guān)系的屬性）間的映射關(guān)系為輸出。隨著數(shù)據(jù)庫應(yīng)用的日趨廣泛，模式匹配在越來越多的應(yīng)用領(lǐng)域中發(fā)揮著重要作用，如：模式集成、數(shù)據(jù)倉庫、電子商務(wù)、語義WEB和P2P數(shù)據(jù)庫等領(lǐng)域。目前的模式匹配工作大都是由操作人員手工進(jìn)行，這就要求操作人員必須對(duì)數(shù)據(jù)庫的模式結(jié)構(gòu)以及每個(gè)模式元素的語義都很熟悉，這是一個(gè)枯燥、費(fèi)時(shí)且容易出錯(cuò)的工作。隨著數(shù)據(jù)庫技術(shù)的不斷發(fā)展，數(shù)據(jù)庫模式逐漸增大。數(shù)據(jù)庫中有數(shù)百個(gè)關(guān)系、數(shù)千個(gè)屬性都是比較常見的，而且它們由不同的設(shè)計(jì)人員設(shè)

4、計(jì)，這就使得全面了解數(shù)據(jù)庫的模式結(jié)構(gòu)變得愈加困難，甚至是一個(gè)不太可能完成的任務(wù)，因此需要一種自動(dòng)的模式匹配方法來代替費(fèi)力、費(fèi)時(shí)且容易出錯(cuò)的手工匹配。目前，這方面的研究成果已經(jīng)相當(dāng)豐富1,2,3,4,5,6,7,8，它們分別利用模式中不同類型的信息來挖掘模式元素的語義，然后進(jìn)行元素匹配。目前利用的信息主要有如下三種類型：(1) 元素自身信息：元素自身信息(元素名，數(shù)據(jù)類型等)是模式中最基本的信息，是元素語義最直觀的反映。早期對(duì)模式匹配的研究2,6,7,9大多是基于元素自身信息。(2) 數(shù)據(jù)實(shí)例信息：數(shù)據(jù)實(shí)例信息是模式描述的對(duì)象，所以也能夠準(zhǔn)確的反映元素語義，但是從大量的數(shù)據(jù)實(shí)例中提取準(zhǔn)確的元素語

5、義是一個(gè)很困難的過程。10是這方面的研究成果。(3) 結(jié)構(gòu)信息：模式中元素間的關(guān)聯(lián)關(guān)系構(gòu)成了模式的結(jié)構(gòu)信息，結(jié)構(gòu)信息能夠有效地輔助匹配，但缺點(diǎn)是模式中定義的結(jié)構(gòu)信息不夠豐富（例如在關(guān)系型數(shù)據(jù)庫中只存在元素間的主、外鍵關(guān)系）。目前這方面的研究成果主要有11,12。目前模式匹配的研究中利用的結(jié)構(gòu)信息主要是模式元素間的主、外鍵關(guān)系，它們由設(shè)計(jì)者在模式設(shè)計(jì)階段指定。但主、外鍵關(guān)系并不能全面地反映出模式中元素間的關(guān)聯(lián)關(guān)系，因?yàn)樵O(shè)計(jì)者在設(shè)計(jì)模式結(jié)構(gòu)時(shí)為了滿足關(guān)系數(shù)據(jù)庫嚴(yán)格的規(guī)范化定義，會(huì)省略某些關(guān)聯(lián)關(guān)系或?qū)ζ溥M(jìn)行修正。如例1所示：例1：表1是某公司進(jìn)銷存管理系統(tǒng)數(shù)據(jù)庫對(duì)供應(yīng)商信息進(jìn)行管理的一個(gè)關(guān)系，它包括

6、供應(yīng)商編號(hào)、名稱、地址、電話、聯(lián)系人、備注等信息。表1 供應(yīng)商信息表ManufaID (PK)CompanyNameAddressTelephoneLinkManSupTypeRemarkA02001南京通用電器有限公司南京苜蓿園大街128號(hào)02584855496黃甘監(jiān)控系統(tǒng)210007A02002深圳市新安錦輝電子廠深圳市寶安44區(qū)4號(hào)樓075529961658毛維金電子器件518101A02003深圳市寶安區(qū)新安金海牛電子廠深圳市寶安44區(qū)4號(hào)樓075527837528梁鷺電子器件518101A03001慈溪市華威電子有限公司慈溪市橋頭鎮(zhèn)工業(yè)區(qū)057463550423毛維金電子器件3153

7、17A03002桂林市興華探測(cè)器有限公司桂林市施家園路31-2號(hào)07735825656石偉安檢門541004從上表可以看出，關(guān)系以供應(yīng)商編號(hào)（ManufaID）作為主鍵，因此屬性ManufaID能夠函數(shù)決定其它屬性。除此之外，我們不能夠發(fā)現(xiàn)其它的結(jié)構(gòu)信息（元素間的關(guān)聯(lián)），但通過與該關(guān)系的設(shè)計(jì)人員溝通，我們發(fā)現(xiàn)它的各個(gè)屬性間還存在著如下一些關(guān)聯(lián)關(guān)系：(1) 當(dāng)某供應(yīng)商不與其它供應(yīng)商重名時(shí)，知道供應(yīng)商名稱就能夠知道該供應(yīng)商的其它信息（事實(shí)上某公司的供應(yīng)商中名字相同的非常少，所以“供應(yīng)商名稱決定供應(yīng)商的其它信息”對(duì)絕大多數(shù)供應(yīng)商來說是適用的）。(2) 事實(shí)上，供應(yīng)商的聯(lián)系電話(Telephone)對(duì)

8、于不同的供應(yīng)商來說是絕對(duì)不同的，所以知道了供應(yīng)商的聯(lián)系電話，就能夠確定是哪個(gè)供應(yīng)商，以及該供應(yīng)商的其它信息。(3) 原則上每個(gè)供應(yīng)商都應(yīng)該有唯一的聯(lián)系地址和聯(lián)系人，但可能存在某些供應(yīng)商提供的地址不夠詳細(xì)、聯(lián)系人重名或者同一業(yè)務(wù)員代理多家供應(yīng)商產(chǎn)品的情況，所以“聯(lián)系人姓名決定供應(yīng)商的其它信息”和“聯(lián)系地址決定供應(yīng)商的其它信息”并不對(duì)所有供應(yīng)商都適用。這些關(guān)聯(lián)關(guān)系在以往的研究中被稱為部分函數(shù)依賴13，與元素間的主、外鍵關(guān)系一樣，這些部分函數(shù)依賴也能夠有效地支持模式匹配。本文介紹的就是一種利用數(shù)據(jù)實(shí)例信息充分挖掘元素間的結(jié)構(gòu)信息來輔助匹配的新方法，主要有如下創(chuàng)新點(diǎn)：(1) 介紹了一條根據(jù)數(shù)據(jù)實(shí)例信息

9、得到結(jié)構(gòu)信息來輔助匹配的新思路。(2) 給出了一種根據(jù)元素間部分函數(shù)依賴計(jì)算結(jié)構(gòu)相似度的新方法。(3) 給出了一種調(diào)整結(jié)構(gòu)相似度的新方法。本文的組織結(jié)構(gòu)如下：第2節(jié)介紹了相關(guān)的研究工作，第3節(jié)介紹了部分函數(shù)依賴的概念及如何利用其表示元素間的關(guān)聯(lián)關(guān)系；第4節(jié)介紹基于部分函數(shù)依賴的結(jié)構(gòu)匹配方法的具體步驟；第5節(jié)對(duì)本方法進(jìn)行實(shí)驗(yàn)評(píng)價(jià)；第6節(jié)為總結(jié)與展望。2相關(guān)工作模式匹配研究目前成果豐碩1,2,3,4,5,6,7,8，它們分別利用了模式中不同類型的信息來進(jìn)行匹配。元素自身信息是模式匹配中使用的最基本信息，早期的模式匹配方法2,9,6,7都重點(diǎn)利用了這一信息；模式中包含的數(shù)據(jù)實(shí)例信息也可以輔助匹配，1

10、0介紹的就是一種利用數(shù)據(jù)實(shí)例信息提高匹配準(zhǔn)確度的方法；11,12則介紹了如何利用模式的結(jié)構(gòu)信息來進(jìn)行匹配；8中介紹了一種利用數(shù)據(jù)庫查詢?nèi)罩局械牟樵冋Z句來輔助匹配的方法。由于本文介紹的是利用結(jié)構(gòu)信息（由數(shù)據(jù)實(shí)例計(jì)算得到的部分函數(shù)依賴關(guān)系）來輔助匹配的新方法，因此這里我們簡(jiǎn)要介紹幾種與本文相關(guān)的利用數(shù)據(jù)實(shí)例和結(jié)構(gòu)信息進(jìn)行模式匹配的方法。DUMAS10是一種利用數(shù)據(jù)實(shí)例信息來輔助匹配的方法，它首先利用重復(fù)數(shù)據(jù)檢測(cè)算法檢測(cè)出源模式和目標(biāo)模式中重復(fù)（相似）的數(shù)據(jù)，然后根據(jù)重復(fù)數(shù)據(jù)中相同數(shù)據(jù)對(duì)應(yīng)的元素相同的原理得到互相匹配的元素對(duì)，但該方法的難點(diǎn)在于如何準(zhǔn)確定位重復(fù)的數(shù)據(jù)。Cupid12方法利用元素自身信

11、息和模式結(jié)構(gòu)信息進(jìn)行匹配。它基于層次結(jié)構(gòu)的模式，將模式中內(nèi)部相關(guān)聯(lián)的元素互相連接構(gòu)成模式樹；然后利用元素名、數(shù)據(jù)類型等元素自身信息計(jì)算元素間的語義相似度，并根據(jù)得到的語義相似度對(duì)元素進(jìn)行分類；再根據(jù)元素的結(jié)構(gòu)信息（模式樹中與該元素相連接和鄰近的元素與其它元素的語義相似信息）計(jì)算元素的結(jié)構(gòu)相似度；最后將每個(gè)元素對(duì)的元素相似度和結(jié)構(gòu)相似度加權(quán)平均得到最終的相似度，并選取最終相似度值最高的元素作為最終的匹配結(jié)果。SF11方法首先利用圖結(jié)構(gòu)來表示源模式和目標(biāo)模式，然后利用名稱匹配器對(duì)兩個(gè)圖結(jié)構(gòu)中的每一對(duì)節(jié)點(diǎn)計(jì)算其語義相似度并根據(jù)語義相似度選出所有的候選匹配對(duì)，再對(duì)候選匹配對(duì)的相似度進(jìn)行調(diào)整（由于兩個(gè)相

12、似節(jié)點(diǎn)的相鄰節(jié)點(diǎn)也相似，所以候選匹配對(duì)的相似度受相鄰候選匹配對(duì)的相似度的影響）得到最終的相似度。文中還給出了幾種根據(jù)相似度選取匹配結(jié)果的不同策略。但該方法的圖結(jié)構(gòu)中包含了過多的節(jié)點(diǎn)信息，所以具有很高的時(shí)間復(fù)雜度。除了11,12中利用的結(jié)構(gòu)信息（主要是元素間的主、外鍵關(guān)系）外，本文還利用了模式元素間的部分函數(shù)依賴關(guān)系。本方法首先根據(jù)模式元素自身信息計(jì)算模式元素間的語義相似度并選取候選匹配對(duì)，根據(jù)模式的數(shù)據(jù)實(shí)例信息計(jì)算模式元素間的部分函數(shù)依賴度并選取元素的有效部分函數(shù)依賴集；然后建立函數(shù)依賴圖，再計(jì)算候選匹配對(duì)的結(jié)構(gòu)相似度并根據(jù)相鄰節(jié)點(diǎn)的相似度相互影響的原理對(duì)結(jié)構(gòu)相似度進(jìn)行調(diào)整，最后將語義相似度和

13、結(jié)構(gòu)相似度相結(jié)合選取最終的匹配結(jié)果。由于本方法有效的利用了元素間的部分函數(shù)依賴關(guān)系，所以匹配效果明顯優(yōu)于其它未使用部分函數(shù)依賴關(guān)系的方法。3部分函數(shù)依賴通常人們思考問題時(shí)都會(huì)對(duì)獲取的信息加以一定程度地抽象。例如：人們通常會(huì)說“鳥會(huì)飛”，沒有人會(huì)對(duì)這個(gè)命題的正確性產(chǎn)生懷疑，因?yàn)橥ǔＫ姷镍B類都是能夠飛行的，當(dāng)然也有一些特殊的情況：企鵝也屬于鳥類，但企鵝卻不會(huì)飛，但這樣的特殊情況并不會(huì)導(dǎo)致我們對(duì)“鳥會(huì)飛”這個(gè)命題的正確性產(chǎn)生懷疑。這里我們把這樣的一些特殊情況稱為該命題的例外。數(shù)據(jù)庫設(shè)計(jì)時(shí)我們也經(jīng)常會(huì)碰到類似的情況，由于關(guān)系數(shù)據(jù)庫嚴(yán)格的規(guī)范化定義，個(gè)別例外就會(huì)導(dǎo)致整個(gè)命題不正確，從而該命題所表示的信

14、息就不能在關(guān)系數(shù)據(jù)庫中反映出來。如例1中，對(duì)于命題“根據(jù)學(xué)生姓名就能夠知道他的其它信息”，由于會(huì)存在“學(xué)生重名”這樣的個(gè)別例外情況，所以關(guān)系數(shù)據(jù)庫無法表示元素StuName同其它元素間的關(guān)聯(lián)關(guān)系。F.Berzal和J.C.Cubero等對(duì)這種關(guān)系進(jìn)行了研究13,把元素間的這種關(guān)聯(lián)關(guān)系稱為部分函數(shù)依賴(Partial Functional Dependency)，當(dāng)部分函數(shù)依賴中不存在例外時(shí)即為通常意義上的函數(shù)依賴。下面我們給出部分函數(shù)依賴的幾個(gè)相關(guān)定義。定義1 r為關(guān)系R中的數(shù)據(jù)實(shí)例集（記錄構(gòu)成的集合），X,YR為兩個(gè)屬性集，我們稱為部分函數(shù)依賴的例外元組集合，當(dāng)且僅當(dāng)滿足如下條件時(shí)：(1)

15、中所有元組滿足。(2) ，中的元組不都滿足。(3) 不存在滿足條件（1）和（2）并且。(#(r)表示關(guān)系r中的元組數(shù))我們稱中元組的數(shù)目為部分函數(shù)依賴?yán)鈹?shù)。圖1 部分函數(shù)依賴?yán)鈹?shù)圖1中，對(duì)于數(shù)據(jù)實(shí)例集r以及部分函數(shù)依賴，當(dāng)Year=“1990”時(shí)，Course可取多個(gè)值，此時(shí)部分函數(shù)依賴產(chǎn)生沖突，中列出了所有產(chǎn)生沖突的元組，為了滿足條件(1)，當(dāng)Year=“1990”時(shí)，屬性Course只能取集合4，3，2中的一個(gè)值；為滿足條件(2)，當(dāng)Course選定某一值A(chǔ)后，中不應(yīng)包含滿足條件Year=“1990”和Course=A的元組；為滿足條件(3),在選擇Course的取值時(shí)，應(yīng)選擇對(duì)應(yīng)元組

16、最多的取值。這里取Course=“4”，因?yàn)镃ourse取值為“4”時(shí)，對(duì)應(yīng)的元組有4個(gè)，而取值“3”和“2”分別對(duì)應(yīng)的元組數(shù)為2個(gè)和1個(gè)。最后中剩余的元組即為例外元組，如圖1中所示。定義2： r為關(guān)系R的數(shù)據(jù)實(shí)例，X,YR為兩個(gè)屬性集，為部分函數(shù)依賴的例外元組集合，則部分函數(shù)依賴的部分函數(shù)依賴度。(后面我們將部分函數(shù)依賴記為，Y函數(shù)依賴于X的部分函數(shù)依賴度記為w(X，Y)據(jù)部分函數(shù)依賴度定義，圖1中部分函數(shù)依賴的部分函數(shù)依賴度，記為：。給出部分函數(shù)依賴的相關(guān)定義后，可以方便的根據(jù)關(guān)系對(duì)應(yīng)的數(shù)據(jù)實(shí)例信息計(jì)算關(guān)系中任意兩個(gè)元素m, n之間的部分函數(shù)依賴度w(m, n)。因此，對(duì)例1中的關(guān)系S，我

17、們計(jì)算得到其部分函數(shù)依賴集PFD(S)= ， 。4基于部分函數(shù)依賴的結(jié)構(gòu)匹配方法的具體步驟本文第3節(jié)中給出了部分函數(shù)依賴的定義及其計(jì)算方法，并利用與模式S對(duì)應(yīng)的數(shù)據(jù)實(shí)例信息計(jì)算得到了模式S的部分函數(shù)依賴集PFD(S)。本節(jié)將介紹如何利用部分函數(shù)依賴集PFD(S)進(jìn)行模式匹配。為了描述上的方便，下表2給出了與源模式S對(duì)應(yīng)的目標(biāo)模式T，模式T也是對(duì)進(jìn)銷存數(shù)據(jù)庫中供應(yīng)商信息的描述，在后面的介紹中我們以模式S為源模式，模式T為目標(biāo)模式。表2 供應(yīng)商信息表（T）Company_ID(PK)NameAddressPhoneFaxPostalCodeContactPersonA02001天長市長久電器有限公

18、司安徽省天長市0550-70221390550-7038928239300徐承義A02002常州市新邁電子有限公司常州市鐘樓區(qū)勞動(dòng)西路常寧公寓0519-868623180519-86892370213001李仲南A02003杭州晶新電子有限公司杭州市市心中路398號(hào)金城廣場(chǎng)B座1801室0571-828145260571-82814786311200陳斌A03001常熟市常新電子有限公司江蘇省常熟市常福路0512-526118880512-52611888215523葉云興B01001上海雙騰電子電器有限公司上海市崇明縣崇明工業(yè)園區(qū)西引路578號(hào)021-69625142021-69625110

19、202150黃曉東4.1方法準(zhǔn)備第3節(jié)的最后部分給出了模式S的部分函數(shù)依賴集，結(jié)合實(shí)際情況考查該集合時(shí)發(fā)現(xiàn)如下兩個(gè)問題：(1) 雖然與的函數(shù)依賴度相同，但事實(shí)上屬性Remark與屬性LinkMan之間并無任何關(guān)聯(lián)關(guān)系，發(fā)生這種情況是由于計(jì)算函數(shù)依賴度時(shí)我們選取的數(shù)據(jù)實(shí)例的數(shù)量太少，從而在計(jì)算依賴度時(shí)產(chǎn)生了較大的隨機(jī)誤差，這里我們通過增加數(shù)據(jù)實(shí)例數(shù)量的方法來避免誤差的產(chǎn)生（事實(shí)上模式匹配的應(yīng)用環(huán)境中一般都存在大量的數(shù)據(jù)實(shí)例）。(2) 的函數(shù)依賴度太低，事實(shí)上SupType和Address之間并沒有任何關(guān)聯(lián)關(guān)系，這樣的部分函數(shù)依賴會(huì)對(duì)匹配操作產(chǎn)生負(fù)面影響，應(yīng)該去除掉，通常我們選取依賴度大于閾值的依

20、賴關(guān)系（從本文5.3節(jié)實(shí)驗(yàn)部分可以看出，閾值選取0.8左右比較合適，這里我們選取）。對(duì)部分函數(shù)依賴集的以上兩個(gè)問題采取相應(yīng)的處理措施后可得到模式的有效部分函數(shù)依賴集(EPFD)。例1中關(guān)系S的有效部分函數(shù)依賴集為EPFD(S)=， 。在根據(jù)部分函數(shù)依賴計(jì)算模式元素間的結(jié)構(gòu)相似度之前，我們首先對(duì)源模式和目標(biāo)模式中的元素根據(jù)其自身信息計(jì)算它們之間的相似度，稱之為語義相似度9，然后根據(jù)語義相似度對(duì)目標(biāo)模式中的每個(gè)元素生成其候選匹配集。在計(jì)算結(jié)構(gòu)相似度時(shí)，以候選匹配集為基礎(chǔ)，僅計(jì)算每個(gè)元素與其候選匹配集中所有元素的結(jié)構(gòu)相似度，這樣可有效地降低算法的時(shí)間復(fù)雜度。候選匹配集一般有如下三種選取策略6：(1)

21、 MaxN：選取相似度最高的N個(gè)匹配項(xiàng)為候選匹配集。(2) MaxDelta：選取與相似度最大值間差值小于d或者最大值的的匹配項(xiàng)為候選匹配集。(3) Threshold：選取相似度大于固定閾值（Threshold）的匹配項(xiàng)為候選匹配集。單一的選擇標(biāo)準(zhǔn)都存在缺點(diǎn)，例如：MaxN和MaxDelta返回的值可能相似度都很低，而Threshold返回的值可能非常少或者非常多(據(jù)Threshold的大小而定)，因此，我們將多條標(biāo)準(zhǔn)結(jié)合考慮。根據(jù)算法的特點(diǎn)，我們的算法將MaxDelta和Threshold這兩種策略相結(jié)合，為目標(biāo)模式中的每個(gè)元素m生成相應(yīng)的候選匹配集CAND(m)。如表2中屬性Compan

22、y_ID，計(jì)算其與表1中各個(gè)屬性間的語義相似度為(CompanyName,0.7) ,(ManufaID,0.4) ,(Address,0.14)，我們?nèi)axDelta策略的值為50%，Threshold策略的閾值為0.3，選取屬性Company_ID的候選匹配集為ManufaID，CompanyName。4.2 依賴圖的建立圖結(jié)構(gòu)是事物間相互關(guān)系最直觀有效的表現(xiàn)方式，所以這里用圖結(jié)構(gòu)來表示元素間的關(guān)聯(lián)關(guān)系，圖中的節(jié)點(diǎn)表示元素，節(jié)點(diǎn)間的連線表示元素間的部分函數(shù)依賴關(guān)系，邊的權(quán)重表示元素間的部分函數(shù)依賴度。根據(jù)模式S的有效部分函數(shù)依賴集EPFD(S)可生成模式S的部分函數(shù)依賴圖G(V,E)，其

23、中V是節(jié)點(diǎn)集合，每個(gè)節(jié)點(diǎn)表示模式中的一個(gè)元素，E是有向邊集合，每條有向邊表示有效部分函數(shù)依賴集EPFD(S)中的一個(gè)部分函數(shù)依賴關(guān)系。例如，在圖結(jié)構(gòu)中用一條從節(jié)點(diǎn)CompanyName到節(jié)點(diǎn)ManufaID的權(quán)重為0.98的有向邊表示。下圖2是模式S的完全函數(shù)依賴圖（僅包含完全函數(shù)依賴關(guān)系），圖3是模式S的部分函數(shù)依賴圖。 圖2 模式S的完全函數(shù)依賴圖圖3 模式S的部分函數(shù)依賴圖圖2根據(jù)模式S的完全函數(shù)依賴集（所有完全函數(shù)依賴組成的集合）構(gòu)建而成，圖3則根據(jù)模式S的有效部分函數(shù)依賴集EPFD(S)構(gòu)建而成。將兩圖對(duì)比，可明顯看出部分函數(shù)依賴提供了更多的結(jié)構(gòu)信息，能更有效的支持匹配操作。下面以圖

24、3為例介紹部分函數(shù)依賴圖中的一些概念：圖3中有一條從節(jié)點(diǎn)CompanyName指向節(jié)點(diǎn)Address的權(quán)重為0.97的有向邊，據(jù)該邊我們稱節(jié)點(diǎn)CompanyName為節(jié)點(diǎn)Address的依賴節(jié)點(diǎn)，節(jié)點(diǎn)Address為節(jié)點(diǎn)CompanyName的決定節(jié)點(diǎn)，邊的權(quán)重0.97稱為元素Address對(duì)元素CompanyName的部分函數(shù)依賴度。4.3 結(jié)構(gòu)相似度計(jì)算建立部分函數(shù)依賴圖后，接下來我們根據(jù)部分函數(shù)依賴圖計(jì)算元素間的結(jié)構(gòu)相似度。下圖4為目標(biāo)模式T的部分函數(shù)依賴圖。圖4 模式T 的部分函數(shù)依賴圖與一個(gè)元素關(guān)聯(lián)的其它元素構(gòu)成了該元素的結(jié)構(gòu)信息，在部分函數(shù)依賴圖中表示為該元素的依賴節(jié)點(diǎn)和決定節(jié)點(diǎn)，

25、其對(duì)應(yīng)的集合分別稱為依賴元素集和決定元素集。定義如下：定義3 元素e的決定元素集為部分函數(shù)依賴圖中以該元素為起點(diǎn)的所有有向邊的終點(diǎn)所表示元素的集合，同時(shí)把以e為起點(diǎn)的有向邊的權(quán)重及該邊終點(diǎn)所表示的元素合稱為e的一個(gè)決定結(jié)構(gòu)信息，把所有決定結(jié)構(gòu)信息組成的集合稱為e的決定結(jié)構(gòu)信息集。如圖3，模式S中的元素CompanyName的決定元素集為ManufaID、Address、Telephone、LinkMan、SupType、Remark，決定結(jié)構(gòu)信息集為( ManufaID,0.98)，(Address，0.97)，(Telephone，0.98)，(LinkMan，0.96)，(SupType，

26、0.96)，(Remark，0.98)。定義4 元素e的依賴元素集為部分函數(shù)依賴圖中以該元素為終點(diǎn)的所有有向邊的起點(diǎn)所表示元素的集合，同時(shí)把以e為終點(diǎn)的有向邊的權(quán)重及該邊起點(diǎn)所表示元素合稱為e的依賴結(jié)構(gòu)信息，把所有依賴結(jié)構(gòu)信息組成的集合稱為e的依賴結(jié)構(gòu)信息集。如圖3，模式S中的元素CompanyName的依賴元素集為 ManufaID、Address、Telephone、LinkMan，其依賴結(jié)構(gòu)信息集為( ManufaID，1)，(Address，0.90)，(Telephone，1)，(LinkMan，0.95)。同理我們把元素間的結(jié)構(gòu)相似度分為決定結(jié)構(gòu)相似度和依賴結(jié)構(gòu)相似度，分別根據(jù)決定

27、結(jié)構(gòu)信息集和依賴結(jié)構(gòu)信息集來計(jì)算決定結(jié)構(gòu)相似度和依賴結(jié)構(gòu)相似度。由于二者的計(jì)算過程相似，下面我們以決定結(jié)構(gòu)相似度的計(jì)算為例介紹它們的計(jì)算過程。在引入部分函數(shù)依賴這個(gè)概念之前，兩個(gè)元素間的結(jié)構(gòu)相似度一般是指與它們分別關(guān)聯(lián)的所有元素組成的集合中互為候選匹配的元素占所有元素的比率12。引入部分函數(shù)依賴這個(gè)概念之后，雖然同為候選匹配對(duì)，但由于元素間的函數(shù)依賴關(guān)系有強(qiáng)弱（部分函數(shù)依賴度的高低）之分，因此對(duì)結(jié)構(gòu)相似度的促進(jìn)作用也有差異，所以前面計(jì)算結(jié)構(gòu)相似度的方法在這里已經(jīng)不再適用。為了方便后面的介紹，我們定義了如下概念：定義5 模式S中存在部分函數(shù)依賴關(guān)系，模式T中存在部分函數(shù)依賴關(guān)系，若(A,B)和(

28、C,D)為兩個(gè)候選匹配對(duì)，則稱(A，B)和(C，D)互為促進(jìn)匹配對(duì)，它們之間相互促進(jìn)作用的大小稱為相似度促進(jìn)度。下面我們通過如下三個(gè)問題來分析促進(jìn)匹配對(duì)間的相似度促進(jìn)度。(1) (C，D)對(duì)(A，B)相似度促進(jìn)度的大小與(C，D)的相似度之間有什么關(guān)系？(2) (C，D)對(duì)(A，B)相似度促進(jìn)度的大小與函數(shù)依賴度之間有什么關(guān)系？(3) (C，D)作為(A，B)的促進(jìn)匹配對(duì)，對(duì)(A，B)的相似度促進(jìn)度有多大？對(duì)問題(1)，顯然(C，D)的相似度越高，對(duì)(A，B)的相似度促進(jìn)度越大。對(duì)問題(2)，當(dāng)，即A、B分別以相同的函數(shù)依賴度函數(shù)決定C、D時(shí)，(C，D)對(duì)(A，B)的相似度促進(jìn)度最大；越大，則

29、(C，D)對(duì)(A，B)的相似度促進(jìn)度越小。例如：模式S對(duì)應(yīng)的部分函數(shù)依賴圖(圖3)中存在部分函數(shù)依賴關(guān)系：和，模式T對(duì)應(yīng)的部分函數(shù)依賴圖(圖4)中存在部分函數(shù)依賴關(guān)系：。從中我們可以看出與的函數(shù)依賴度相接近，即兩者差值為0.01，而與的函數(shù)依賴度差值為0.02，據(jù)前面分析我們得出如下結(jié)論：因?yàn)?.02>0.01，所以(S.Address，T.Address)對(duì)(S.ManufaID，T.Name)的相似度促進(jìn)度比對(duì)(S.CompanyName，T.Name)的相似度促進(jìn)度小。問題(1)、(2)是對(duì)相似度促進(jìn)度大小與函數(shù)依賴度、促進(jìn)匹配對(duì)相似度之間關(guān)系的定性分析，問題(3)則是對(duì)它們之間關(guān)

30、系的定量分析。表3列舉了描述依賴度差值d、(C，D)間相似度m與相似度促進(jìn)度之間定量關(guān)系的幾種方法。從本文第5.2節(jié)我們可以看表3 三種相似度間差值d與促進(jìn)度之間的定量關(guān)系序號(hào)名稱公式描述1線性函數(shù)（a為參數(shù)）2拋物線函數(shù)3指數(shù)函數(shù)（）出， 與第一種線性函數(shù)和第二種拋物線函數(shù)相比，第三種以自然對(duì)數(shù)為底的指數(shù)函數(shù)能夠更準(zhǔn)確的描述三者間的定量關(guān)系。通過對(duì)以上三個(gè)問題的分析，我們得到了促進(jìn)度與函數(shù)依賴度、促進(jìn)匹配對(duì)相似度之間的定性關(guān)系，并給出了有效的公式描述。下面我們利用該公式來計(jì)算結(jié)構(gòu)相似度。算法如圖5所示。需要說明的是：由于語義相似度的計(jì)算都采用啟發(fā)式的方法，計(jì)算出的相似度數(shù)值并不具有實(shí)際意義，

31、所以該算法中將所有候選匹配對(duì)間的語義相似度都看作1。（可有效減少計(jì)算量，對(duì)結(jié)果無明顯影響）CalDcssim(x，y，X，Y)輸入：候選匹配對(duì)(x，y)，x的決定元素集X，y的決定元素集Y輸出：x和y的函數(shù)決定結(jié)構(gòu)相似度dcssim(x，y)（1）從X中任取元素m，令Q=YCAND(m)，并從X中去除m；（2）若Q=，轉(zhuǎn)入步驟(4)； （3）在Q中選擇使|w(y，n)w(x，m)|最小的元素n，令dcssim(x,y)=dcssim(x,y)+；（4）若X，則轉(zhuǎn)入步驟(1)；（5）從Y任取元素p，令Q=XCAND(p)，并從Y中去除p；（6）若Q=，轉(zhuǎn)入步驟(8)；（7）在Q中選擇使|w(x，

32、q)w(y，p)|最小的元素q，令dcssim(x,y)=dcssim(x,y)+；（8）若Y，則轉(zhuǎn)入步驟(5)；（9）返回dcssim(x,y) = dcssim(x,y)/(|X|+|Y|)；圖5 決定結(jié)構(gòu)相似度計(jì)算圖5中的算法以候選匹配對(duì)(x，y)以及x，y對(duì)應(yīng)的決定元素集X，Y為輸入，步驟(1)-(4)遍歷X中所有元素，對(duì)每一個(gè)元素m，求m的候選匹配集CAND(m)與集合Y的交集Q，若Q，則在Q中選擇這樣一個(gè)元素n，使得|w(y，n)w(x，m)|最小，即相似度促進(jìn)度最大，然后得出(m，n)對(duì)(x，y)的相似度促進(jìn)度為，并將該值與其它促進(jìn)匹配對(duì)的相似度促進(jìn)度相加。處理完X中的元素后，步

33、驟(5)-(8)對(duì)Y中元素做相同處理，最后步驟(9)將所有相似度促進(jìn)度之和對(duì)X,Y中元素?cái)?shù)量求平均得到候選匹配對(duì)(x,y)的決定結(jié)構(gòu)相似度dcssim(x,y)。對(duì)于依賴結(jié)構(gòu)相似度我們采用與決定結(jié)構(gòu)相似度同樣的計(jì)算方法，不同的是這里的X為元素x的依賴元素集，Y為元素y的依賴元素集，最后求得元素x和y的依賴結(jié)構(gòu)相似度dpssim(x,y)。4.4 結(jié)構(gòu)相似度傳遞4.3節(jié)中計(jì)算的候選匹配對(duì)的結(jié)構(gòu)相似度是所有促進(jìn)匹配對(duì)的語義相似度對(duì)其促進(jìn)度的綜合，但事實(shí)上促進(jìn)匹配對(duì)的結(jié)構(gòu)相似度對(duì)候選匹配對(duì)的結(jié)構(gòu)相似度也具有促進(jìn)作用，即互為促進(jìn)匹配對(duì)的兩個(gè)候選匹配對(duì)的結(jié)構(gòu)相似度間也能夠相互促進(jìn)。據(jù)此，我們采用傳遞調(diào)整

34、算法對(duì)結(jié)構(gòu)相似度進(jìn)行調(diào)整優(yōu)化，使結(jié)構(gòu)相似度能夠更準(zhǔn)確的反映元素間結(jié)構(gòu)上的相似程度。在介紹傳遞調(diào)整算法之前，我們首先介紹決定集結(jié)構(gòu)相似度和依賴集結(jié)構(gòu)相似度的概念。以x的決定元素集X和y的決定元素集Y為例，據(jù)X，Y我們定義二部圖G(X，Y，E)，E中每條邊的權(quán)值為所關(guān)聯(lián)的一對(duì)候選匹配對(duì)(m，n)對(duì)候選匹配對(duì)(x，y)的相似度促進(jìn)度，這里為dcssim(m，n)。我們用該二部圖的最大流通量表示這兩個(gè)元素的決定集結(jié)構(gòu)相似度(公式(1)，對(duì)公式(1)的右邊采用匈牙利算法15計(jì)算二部圖最大流通量。 公式（1）對(duì)于依賴集結(jié)構(gòu)相似度，我們以x的依賴元素集X和y的依賴元素集Y為例，同理我們可以得到其依賴集結(jié)構(gòu)相

35、似度(公式(2)，對(duì)公式(2)的右邊同樣采用匈牙利算法15計(jì)算二部圖最大流通量。 公式（2）然后根據(jù)以上定義，我們分別對(duì)候選匹配對(duì)的決定結(jié)構(gòu)相似度和依賴結(jié)構(gòu)相似度進(jìn)行調(diào)整。首先我們對(duì)決定結(jié)構(gòu)相似度進(jìn)行調(diào)整，對(duì)任意一對(duì)候選匹配(x，y)，x對(duì)應(yīng)的決定節(jié)點(diǎn)集合為X，y對(duì)應(yīng)的決定節(jié)點(diǎn)集合為Y，則x，y間的決定結(jié)構(gòu)相似度可利用如下公式(3)進(jìn)行調(diào)整。 公式(3)根據(jù)公式（3）對(duì)所有候選匹配對(duì)的決定結(jié)構(gòu)相似度都進(jìn)行一次調(diào)整稱為一個(gè)調(diào)整周期，若兩個(gè)調(diào)整周期之間所有候選匹配對(duì)的決定結(jié)構(gòu)相似度的變化都小于閾值，說明調(diào)整已充分，調(diào)整過程結(jié)束；若多次調(diào)整仍未達(dá)到要求，則在第N個(gè)調(diào)整周期后結(jié)束調(diào)整。同理，對(duì)依賴結(jié)構(gòu)

36、相似度的調(diào)整與對(duì)決定結(jié)構(gòu)相似度的調(diào)整類似。經(jīng)過上述調(diào)整我們可以得到比較真實(shí)反映元素間結(jié)構(gòu)相似程度的決定結(jié)構(gòu)相似度和依賴結(jié)構(gòu)相似度，下面我們將介紹如何根據(jù)決定結(jié)構(gòu)相似度、依賴結(jié)構(gòu)相似度及原有的語義相似度生成模式元素間的映射。4.5 映射生成映射生成是映射關(guān)系確定的過程，它是模式匹配過程中的一個(gè)重要步驟，其確定的映射關(guān)系作為模式匹配的結(jié)果直接輸出。文獻(xiàn)11中介紹了一種解決映射問題的方法：穩(wěn)定婚姻法，其核心思想是：選擇滿足如下兩個(gè)條件的匹配對(duì)組成的集合作為模式映射結(jié)果。(1) 集合中所有匹配對(duì)的相似度之和最大。(2) 其中不存在這樣的兩個(gè)匹配對(duì)(x,y)，(m,n)：x與n的相似度大于x與y的相似度

37、，同時(shí)y與m的相似度大于y與x的相似度。本文也采用相同的方法來生成映射。前面我們得到了元素間的語義相似度、決定結(jié)構(gòu)相似度和依賴結(jié)構(gòu)相似度，但是在映射生成過程中，使用三種不同的相似度標(biāo)準(zhǔn)會(huì)使過程復(fù)雜、準(zhǔn)確率降低，所以在生成映射之前我們先對(duì)這三種相似度采用加權(quán)平均法進(jìn)行合并，生成候選匹配對(duì)總的相似度，如公式(4)： 公式(4)得到候選匹配對(duì)總的相似度后，我們?cè)俑鶕?jù)穩(wěn)定婚姻法選取最終的映射結(jié)果輸出。第5節(jié)將對(duì)本方法得到結(jié)果的精確性進(jìn)行實(shí)驗(yàn)評(píng)價(jià)。5 算法實(shí)驗(yàn)評(píng)價(jià)5.1 實(shí)驗(yàn)情況介紹本方法利用數(shù)據(jù)實(shí)例信息挖掘元素間的結(jié)構(gòu)信息，并以之輔助匹配。為驗(yàn)證本方法的有效性，我們將本方法與模式匹配領(lǐng)域中常用的一些方

38、法進(jìn)行實(shí)驗(yàn)對(duì)比，并以如下三個(gè)指標(biāo)來描述對(duì)比結(jié)果：(1) 查準(zhǔn)率(Precision)：匹配結(jié)果中正確匹配結(jié)果占所有匹配結(jié)果的比率；(2) 查全率(Recall)：匹配結(jié)果中正確匹配結(jié)果占所有正確匹配的比率；(3) 全面性(Overall)：通過匹配方法節(jié)省的工作量占總的匹配工作量的比率。其中T為匹配算法返回的正確匹配結(jié)果，P為匹配算法返回的所有匹配結(jié)果，F(xiàn)為匹配算法返回的錯(cuò)誤匹配結(jié)果，R為所有正確的匹配結(jié)果。查準(zhǔn)率、查全率和全面性能夠比較全面的反映匹配方法的性能，是模式匹配研究中最常用的三個(gè)評(píng)價(jià)指標(biāo)6,11,12。對(duì)測(cè)試用例的選取我們分為兩個(gè)步驟，首先選取模式結(jié)構(gòu)，然后生成數(shù)據(jù)實(shí)例。這里的源模

39、式和目標(biāo)模式分別取自兩家銷售同類產(chǎn)品的公司的進(jìn)銷存管理系統(tǒng)，稱為DB1和DB2。下表4列出了兩個(gè)模式中關(guān)系和屬性的基本情況。模式中的數(shù)據(jù)實(shí)例采用DTM Data Generator 生成。測(cè)試中我們將模式及其對(duì)應(yīng)數(shù)表4 DB1、DB2的關(guān)系及屬性數(shù)目模式關(guān)系數(shù)目屬性數(shù)目DB125224DB227252據(jù)導(dǎo)入MySql5.0數(shù)據(jù)庫中，使用ODBC連接數(shù)據(jù)庫以獲取各種模式信息。主機(jī)硬件采用Intel Pentium 4 2.0G，1G內(nèi)存；操作系統(tǒng)為Windows XP SP2。5.2相似度促進(jìn)度與相似度及函數(shù)依賴度定量關(guān)系的實(shí)驗(yàn)證明4.3節(jié)中對(duì)相似度促進(jìn)度與相似度及函數(shù)依賴度的關(guān)系進(jìn)行了討論，給

40、出了三種描述它們之間關(guān)系的方法，這里我們通過實(shí)驗(yàn)來對(duì)這三種方法進(jìn)行分析對(duì)比。取數(shù)據(jù)實(shí)例集的大小為3000，對(duì)比結(jié)果如下圖6所示：圖6 三種不同的描述方法之間的指標(biāo)對(duì)比圖通過圖6我們可以看出，當(dāng)用指數(shù)函數(shù)描述函數(shù)依賴度與相似度促進(jìn)度之間的關(guān)系時(shí)，在查準(zhǔn)率、查全率和全面性三個(gè)指標(biāo)上都優(yōu)于其它兩種描述方法，所以本方法中采用指數(shù)函數(shù)來描述函數(shù)依賴度與相似度促進(jìn)度間的關(guān)系。5.3參數(shù)不同取值的匹配結(jié)果對(duì)比本文4.1節(jié)中，對(duì)所有的部分函數(shù)依賴關(guān)系，我們選取依賴度大于閾值的依賴關(guān)系作為有效部分函數(shù)依賴來輔助匹配。值的選取對(duì)匹配結(jié)果有很大程度的影響，下圖7是閾值在區(qū)間0.4,1之間變化時(shí)，查準(zhǔn)率、查全率、全面

41、性三個(gè)指標(biāo)的變化圖。由于函數(shù)依賴度低于0.4時(shí)無任何實(shí)際意義，在此我們對(duì)函數(shù)依賴度值小與0.4的依賴關(guān)系不予考慮。圖7：不同閾值對(duì)算法性能的影響圖7描述了算法各項(xiàng)性能指標(biāo)隨閾值變化的趨勢(shì)圖，如圖所示，算法的查準(zhǔn)率（Precision）從36%提高到88%再下降到70%，這說明算法的查準(zhǔn)率隨著從0.4到1的變化而先升后降，并在某一中間值達(dá)到最高，即匹配結(jié)果中正確匹配占所有匹配結(jié)果的比率達(dá)到最高。算法的查全率從38%提高到100%然后下降到71%，說明算法的查全率也隨著從0.4到1的變化而先升后降，并在某一中間值達(dá)到最高，即匹配結(jié)果中包含的正確匹配數(shù)目最多。算法的全面性同樣從-22.7%提高到88

42、%然后下降到41.4%，也說明全面性隨著從小到大的變化而先升后降，并在某一中間值達(dá)到最高，即匹配算法節(jié)省的工作量最多。從圖中我們發(fā)現(xiàn)：當(dāng)取值在0.8左右時(shí)，算法的各項(xiàng)性能指標(biāo)都達(dá)到最大。所以為了使算法的性能最優(yōu)，應(yīng)在0.8左右取值。當(dāng)取值過小時(shí)，很多依賴度很小的部分依賴關(guān)系參與匹配，依賴度數(shù)值偏小意味著這個(gè)依賴關(guān)系不具有實(shí)際意義的可能性很大，這樣的依賴關(guān)系參與匹配會(huì)使算法的準(zhǔn)確度降低；當(dāng)取值過大時(shí)，有些依賴度數(shù)值較大的依賴關(guān)系被過濾，依賴度數(shù)值較大意味著該依賴關(guān)系具有實(shí)際意義的可能性很大，這樣的依賴關(guān)系不參與匹配過程會(huì)使法的準(zhǔn)確度降低，而當(dāng)時(shí)，幾乎所有的非完全函數(shù)依賴都不參與匹配過程，算法僅僅

43、利用了模式中的完全函數(shù)依賴關(guān)系，準(zhǔn)確度大幅下降。5.4 同類方法對(duì)比數(shù)據(jù)實(shí)例信息與結(jié)構(gòu)信息是模式匹配中利用的兩類重要信息，利用數(shù)據(jù)實(shí)例信息進(jìn)行匹配的方法中具有代表性的是duplicates10方法，而cupid12方法和SF11方法則都是常用的利用結(jié)構(gòu)信息來進(jìn)行匹配的方法，因?yàn)楸痉椒▽⑦@兩種信息結(jié)合起來，利用數(shù)據(jù)實(shí)例信息計(jì)算得到的結(jié)構(gòu)信息（部分函數(shù)依賴）輔助匹配。所以為了驗(yàn)證本方法的有效性，下面我們首先將本方法與利用數(shù)據(jù)實(shí)例信息進(jìn)行匹配的duplicates方法進(jìn)行對(duì)比，由于數(shù)據(jù)集中數(shù)據(jù)量的大小對(duì)兩種方法的實(shí)驗(yàn)結(jié)果都有影響，所以我們分別生成了四種不同數(shù)據(jù)量大小(50，200，1000，5000

44、)的數(shù)據(jù)集進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果圖7所示：A：兩種方法針對(duì)不同數(shù)據(jù)量的數(shù)據(jù)集合的查準(zhǔn)率對(duì)比圖B：兩種方法針對(duì)不同數(shù)據(jù)量的數(shù)據(jù)集合的查全率對(duì)比圖C：兩種方法針對(duì)不同數(shù)據(jù)量的數(shù)據(jù)集合的全面性對(duì)比圖圖8 兩種方法針對(duì)不同數(shù)據(jù)量的數(shù)據(jù)集合的指標(biāo)對(duì)比從圖8(A)兩種方法查準(zhǔn)率的對(duì)比圖中我們可以看出：隨著數(shù)據(jù)集中數(shù)據(jù)量的不斷增大，duplicates方法和PFD_based方法的查準(zhǔn)率都在增大，但是相對(duì)于duplicates方法，PFD_based方法受數(shù)據(jù)量大小的影響更大。當(dāng)數(shù)據(jù)量為50時(shí)，PFD_based方法的查準(zhǔn)率低于duplicates方法，當(dāng)數(shù)據(jù)量增大到1000時(shí)，PFD_based方法的查準(zhǔn)率就

45、明顯高于duplicates方法，同時(shí)我們還發(fā)現(xiàn)當(dāng)數(shù)據(jù)集的數(shù)據(jù)量從1000增加到5000時(shí)，兩種方法查準(zhǔn)率的提高幅度都比較小。據(jù)此我們得到如下結(jié)論：數(shù)據(jù)集越大，越能夠提高方法的查準(zhǔn)率，但當(dāng)其增大到一定程度后再繼續(xù)增大時(shí)，則對(duì)查準(zhǔn)率的提高幅度并不大，反而會(huì)提高算法的時(shí)間復(fù)雜度。據(jù)圖8(B)和圖8(C)分別對(duì)查全率和全面性的對(duì)比我們也可以發(fā)現(xiàn)和圖8(A)相同的規(guī)律。圖8中分別對(duì)查準(zhǔn)率、查全率和全面性三個(gè)指標(biāo)進(jìn)行對(duì)比，我們可以得到如下結(jié)論：與duplicates方法相比，PFD_based方法對(duì)數(shù)據(jù)量的要求更高，需要大量的數(shù)據(jù)實(shí)例，但當(dāng)數(shù)據(jù)實(shí)例的數(shù)量大于1000時(shí)，算法的各項(xiàng)指標(biāo)相比duplicat

46、es方法都有較大提高，大幅度提高了模式匹配的精確度。同時(shí)考慮到算法的時(shí)間復(fù)雜度，我們一般取數(shù)據(jù)量的大小位于區(qū)間1000,5000。接下來我們?cè)賹⒈痉椒ㄅc利用結(jié)構(gòu)信息的Cupid方法和 SF方法進(jìn)行對(duì)比，這里取數(shù)據(jù)集的大小為3000。實(shí)驗(yàn)數(shù)據(jù)如下圖9所示：圖9 Cupid、SF和PFD_based三種方法的不同指標(biāo)對(duì)比從圖9中三種方法在各個(gè)指標(biāo)上的對(duì)比我們可以看出：在查準(zhǔn)率指標(biāo)上，PFD_based方法高于其它兩種方法，即PFD_based方法的匹配結(jié)果中正確匹配所占的比率最高；在查全率指標(biāo)上，PFD_based方法高于其它兩種方法，即PFD_based方法的匹配結(jié)果中包含的正確匹配最多；在全面

47、性指標(biāo)上，PFD_based方法也高于其它兩種方法，即節(jié)省的工作量也比其它兩種算法要多。通過上面的實(shí)驗(yàn)我們可以看出，PFD_based方法將數(shù)據(jù)實(shí)例信息和結(jié)構(gòu)信息結(jié)合起來進(jìn)行匹配，在各項(xiàng)性能指標(biāo)上都明顯優(yōu)于單獨(dú)利用數(shù)據(jù)實(shí)例信息的duplicates方法，也明顯優(yōu)于單獨(dú)利用結(jié)構(gòu)信息的SF方法和Cupid方法。6總結(jié)與展望本文提出了一種通過數(shù)據(jù)實(shí)例信息得到元素間的部分函數(shù)依賴關(guān)系，然后利用其輔助模式匹配的新方法，并從理論分析和實(shí)驗(yàn)結(jié)果兩個(gè)方面論證了此方法能夠在一定程度上提高模式匹配的精確度。目前的模式匹配方法大多以元素自身信息為主來進(jìn)行匹配，其它種類的信息只起到了一些輔助的作用，然而同一描述對(duì)象由

48、不同的模式設(shè)計(jì)者描述時(shí)，其自身信息可能有很大的差異，從而在模式匹配過程中產(chǎn)生誤導(dǎo)作用，使得單獨(dú)利用元素自身信息進(jìn)行匹配的效果并不理想，事實(shí)也正是如此。數(shù)據(jù)實(shí)例信息能夠最真實(shí)地反映元素的語義，且不會(huì)由于設(shè)計(jì)者的不同而產(chǎn)生差異，能夠在模式匹配過程中發(fā)揮更重要的作用。未來我們可以利用數(shù)據(jù)實(shí)例信息來獲取更真實(shí)的元素語義，并進(jìn)行匹配，提高匹配的精確度。A structure matching method based on partial functional dependenciesLi Guo-Hui1） Du Xiao-Kun1） Du Jian-Qiang2）1)School of Comput

49、er Science & Technology, Huazhong University of Science & Technology, Wuhan 4300742)School of Computer Science & Technology, JiangXi University of Traditional Chinese Medicine Nanchang 330006AbstractSchema matching is a difficulty in many database application domains, e.g., data integrat

50、ion, E-business, data warehousing and semantic query. We can get correct mapping by mining the semantics of elements from the elements' own information (e.g., elements names and elements data types), data instances for elements and structure information. In this paper, we introduce a new algorit

51、hm which integrates the data instance information and structure information to supply matching. At first, we calculated the degree of partial functional dependency according to the data instance information, and then we constructed the graph of partial functional dependency(Fig.3) based on the degre

52、e of partial functional dependency, the degree of structure similarity was calcluated according to the graph fo partial functional dependency, at last, according to the degree of structure similarity and semantic similarity, the mapping was generated .Because of the more stucture information was use

53、d, the performance of this algorithm is better than the algorithm only use the complete functional dependency information. Extensive simulation experiments were conducted and the results（Fig.8,Fig.9） show that this algorithm is better than other related algorithms in various performance metrics such

54、 as precision, recall and overall.Keywords:schema matching, partial functional dependency, structure match參考文獻(xiàn)：1 Huimin Zhao. Semantic Matching Across Heterogeneous Data Sources. In Communications of the ACM, 2007, 50: 4550.2 Li W, Clifton C. SemInt: a tool for identifying attribute correspondences

55、in heterogeneous databases using neural network. Data Knowl Eng 2000, 33(1):4984.3 Robert H. Warren, Frank Wm. Tompa. Multicolumn Substring Matching for Database Schema Translation. Proc. of VLDB, Seoul, Korea, 2006.4 Philip Bohannon, Eiman Elnahrawy, Wenfei Fan and Michael Flaster. Putting Context

56、into Schema Matching. In Proc. of VLDB, Seoul, Korea,2006.5 J.Madhavan, Philip A.Bernstein,AnHai Doan,Alon Halevy. Corpus-based Schema Matching. Proceeding of the 21st International Conference on Data Engineering (ICDE), Berlin, Germany, 2005.6 Hong-Hai Do and Erhard Rahm. COMA - a system for flexib

57、le combination of schema matching approaches. In Proc. Of VLDB, Hong Kong, China,2002.7 David Aumueller, Hong-Hai Do, Sabine Massmann, Erhard Rahm. Schema and Ontology Matching with COMA+. In Proc. SIGMOD, Baltimore, Maryland, 2005.8 Hazem Elmeleegy, Mourad Ouzzani and Ahmed Elmagarmid. Usage-Based Schema Matching. Proceeding of the 24st International Conferenc