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

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

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

3、部分函數(shù)依賴，結(jié)構(gòu)匹配中圖法分類號 TP311.1311引言模式匹配是模式間的一個二元操作，它以源模式和目標模式為輸入，以兩個模式中元素（在關(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)域。目前的模式匹配工作大都是由操作人員手工進行，這就要求操作人員必須對數(shù)據(jù)庫的模式結(jié)構(gòu)以及每個模式元素的語義都很熟悉，這是一個枯燥、費時且容易出錯的工作。隨著數(shù)據(jù)庫技術(shù)的不斷發(fā)展，數(shù)據(jù)庫模式逐漸增大。數(shù)據(jù)庫中有數(shù)百個關(guān)系、數(shù)千個屬性都是比較常見的，而且它們由不同的設(shè)計人員設(shè)

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

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

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

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

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

9、得到結(jié)構(gòu)信息來輔助匹配的新思路。(2) 給出了一種根據(jù)元素間部分函數(shù)依賴計算結(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é)對本方法進行實驗評價；第6節(jié)為總結(jié)與展望。2相關(guān)工作模式匹配研究目前成果豐碩1,2,3,4,5,6,7,8，它們分別利用了模式中不同類型的信息來進行匹配。元素自身信息是模式匹配中使用的最基本信息，早期的模式匹配方法2,9,6,7都重點利用了這一信息；模式中包含的數(shù)據(jù)實例信息也可以輔助匹配，1

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

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

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

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

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

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

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

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

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

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

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

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

22、y_ID，計算其與表1中各個屬性間的語義相似度為(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é)點表示元素，節(jié)點間的連線表示元素間的部分函數(shù)依賴關(guān)系，邊的權(quán)重表示元素間的部分函數(shù)依賴度。根據(jù)模式S的有效部分函數(shù)依賴集EPFD(S)可生成模式S的部分函數(shù)依賴圖G(V,E)，其

23、中V是節(jié)點集合，每個節(jié)點表示模式中的一個元素，E是有向邊集合，每條有向邊表示有效部分函數(shù)依賴集EPFD(S)中的一個部分函數(shù)依賴關(guān)系。例如，在圖結(jié)構(gòu)中用一條從節(jié)點CompanyName到節(jié)點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)建而成。將兩圖對比，可明顯看出部分函數(shù)依賴提供了更多的結(jié)構(gòu)信息，能更有效的支持匹配操作。下面以圖

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

25、其對應(yīng)的集合分別稱為依賴元素集和決定元素集。定義如下：定義3 元素e的決定元素集為部分函數(shù)依賴圖中以該元素為起點的所有有向邊的終點所表示元素的集合，同時把以e為起點的有向邊的權(quán)重及該邊終點所表示的元素合稱為e的一個決定結(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ù)依賴圖中以該元素為終點的所有有向邊的起點所表示元素的集合，同時把以e為終點的有向邊的權(quá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)信息集來計算決定結(jié)構(gòu)相似度和依賴結(jié)構(gòu)相似度。由于二者的計算過程相似，下面我們以決定結(jié)構(gòu)相似度的計算為例介紹它們的計算過程。在引入部分函數(shù)依賴這個概念之前，兩個元素間的結(jié)構(gòu)相似度一般是指與它們分別關(guān)聯(lián)的所有元素組成的集合中互為候選匹配的元素占所有元素的比率12。引入部分函數(shù)依賴這個概念之后，雖然同為候選匹配對，但由于元素間的函數(shù)依賴關(guān)系有強弱（部分函數(shù)依賴度的高低）之分，因此對結(jié)構(gòu)相似度的促進作用也有差異，所以前面計算結(jié)構(gòu)相似度的方法在這里已經(jīng)不再適用。為了方便后面的介紹，我們定義了如下概念：定義5 模式S中存在部分函數(shù)依賴關(guān)系，模式T中存在部分函數(shù)依賴關(guān)系，若(A,B)和(

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

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

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

31、所以該算法中將所有候選匹配對間的語義相似度都看作1。（可有效減少計算量，對結(jié)果無明顯影響）CalDcssim(x，y，X，Y)輸入：候選匹配對(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)相似度計算圖5中的算法以候選匹配對(x，y)以及x，y對應(yīng)的決定元素集X，Y為輸入，步驟(1)-(4)遍歷X中所有元素，對每一個元素m，求m的候選匹配集CAND(m)與集合Y的交集Q，若Q，則在Q中選擇這樣一個元素n，使得|w(y，n)w(x，m)|最小，即相似度促進度最大，然后得出(m，n)對(x，y)的相似度促進度為，并將該值與其它促進匹配對的相似度促進度相加。處理完X中的元素后，步

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

34、算法對結(jié)構(gòu)相似度進行調(diào)整優(yōu)化，使結(jié)構(gòu)相似度能夠更準確的反映元素間結(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)的一對候選匹配對(m，n)對候選匹配對(x，y)的相似度促進度，這里為dcssim(m，n)。我們用該二部圖的最大流通量表示這兩個元素的決定集結(jié)構(gòu)相似度(公式(1)，對公式(1)的右邊采用匈牙利算法15計算二部圖最大流通量。 公式（1）對于依賴集結(jié)構(gòu)相似度，我們以x的依賴元素集X和y的依賴元素集Y為例，同理我們可以得到其依賴集結(jié)構(gòu)相

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

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

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

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

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

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

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

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

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

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

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

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

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

48、不同的模式設(shè)計者描述時，其自身信息可能有很大的差異，從而在模式匹配過程中產(chǎn)生誤導(dǎo)作用，使得單獨利用元素自身信息進行匹配的效果并不理想，事實也正是如此。數(shù)據(jù)實例信息能夠最真實地反映元素的語義，且不會由于設(shè)計者的不同而產(chǎn)生差異，能夠在模式匹配過程中發(fā)揮更重要的作用。未來我們可以利用數(shù)據(jù)實例信息來獲取更真實的元素語義，并進行匹配，提高匹配的精確度。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參考文獻：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