基于DBSCAN聚類算法的多模式匹配

丁國輝　許瑩南　郭軍宏

1(沈陽航空航天大學　遼寧 沈陽 110136)

2(沈陽炮兵學院　遼寧 沈陽 110136)

?

基于DBSCAN聚類算法的多模式匹配

丁國輝1許瑩南1郭軍宏2

1(沈陽航空航天大學遼寧 沈陽 110136)

2(沈陽炮兵學院遼寧 沈陽 110136)

摘要模式匹配在很多數據庫相關領域中有著廣泛的應用，例如數據集成、數據空間以及數據倉庫。傳統的匹配技術主要研究兩個屬性之間的匹配任務，而忽略了多個屬性間的匹配任務。針對這一問題，提出一種基于DBSCAN聚類算法的多模式集成技術。該方法將關注多個屬性之間語義對應關系的發現，相對于兩個屬性之間對應關系的發現，這將是一個更加復雜的問題。主要研究思路是將每個屬性看成向量空間中的一個點，然后利用聚類技術將這些屬性劃分到不同的集合中，在同一個聚類中的屬性具有相似的語義。同時，利用Web結構信息源來提高模式匹配結果的質量。最后，通過大量的實驗來驗證該方法是有效的并具有較好的性能。

關鍵詞模式匹配語義對應關系結構化信息聚類技術

MULTI-SCHEMA MATCHING BASED ON DBSCAN CLUSTERING ALGORITHM

Ding Guohui1Xu Yingnan1Guo Junhong21

(Shenyang Aerospace University,Shenyang 110136,Liaoning,China)2(Shenyang Institute of Artillery,Shenyang 110136,Liaoning,China)

AbstractSchema matching has wide application in many database correlated fields, such as data integration, data space and data warehouse. Matching task between only two attributes is what the traditional matching techniques study, but the matching task between multiple attributes is ignored. With respect to this problem, we proposed a multi-schema integration technique in this paper, which is based on DBSCAN (density-based spatial clustering of applications with noise) clustering algorithm. The proposed approach focus on the discovery of semantic correspondence among multiple attributes, which is a more complex issue relative to discovering the pairwise-attribute correspondence. Our main study idea is to deem every attribute as a point in the vector space, and then to partition these attributes into different sets by clustering technique. The attributes within same cluster have similar semantics. Meanwhile, we utilised the information sources of Web structure to improve the quality of schema matching results. At last, we performed extensive experimental research to verify the approach, and the experimental results showed that our approach was effective and had good performance.

KeywordsSchema matchingSemantic correspondenceStructured informationClustering technique

0引言

數據集成是數據庫領域中一個重要研究內容。數據集成的目標是為多個不同的數據源提供統一的查詢結構以及在多個信息系統之間提供共享數據的能力。通過統一的查詢接口，用戶不需要定位所有數據源、不需要單獨與每個數據源進行交互，最后以手動方式將這些結果進行合并。在包含大量數據源的大企業中，數據集成是十分重要的，主要表現在以下方面：大規模的科研項目的推進過程，這些項目中的數據集往往由不同的研究人員產生；為了政府機構之間更好地合作，需要集成來自不同機構的數據源；在互聯網上成千上萬的結構數據源之間進行搜索時，提供更好的搜索質量[1]。異構數據源之間的數據集成將會碰到很多技術上、結構上和語義特性上的難題[1,2]。

數據集成的本質是模式匹配，在數據集成領域，這一直是一個重要，但又很困難的問題。隨著信息系統的劇增，針對模式匹配解決方案的需求也變得更加突出。隨著互聯網的發展，數據共享和數據交換問題也亟待解決。這些問題的實質都是模式匹配，因此，針對模式匹配解決方案的需求將會進一步增加。模式匹配問題的本質是發現源模式和目標模式的屬性之間的語義對應關系，即匹配。在某些具體的應用背景下，一個匹配中的兩個屬性實際上具有相同或者相似的語義。從集合的角度來看，找到的匹配可以被看成兩個模式之間的映射。模式匹配領域存在大量的匹配技術，例如文獻[3-14]所述。

現存的匹配技術也被稱為匹配器。最初，匹配任務都是領域專家手工完成，這種手工的解決方案耗時耗力。因此，人們開始研究自動的匹配技術，以提高匹配的效率。文獻[14]對現存的自動和半自動的模式匹配技術進行了綜述。他們提出的分類涵蓋了大部分現存的方法。其中，一個主要的分類是基于模式信息的匹配方法和基于數據實例信息的匹配方法。雖然該領域存在大量的工作，但是不存在完美的能夠返回100%正確匹配結果的技術。因此，模式匹配問題還需要更多的研究。本文研究的重點是自動的模式匹配技術，并提出一種自動的基于DBSCAN(Density-Based Spatial Clustering of Applications with Noise)[15]聚類技術的多模式匹配技術。傳統的匹配技術主要研究兩個屬性之間語義對應關系的發現問題。例如，給定兩個數據庫關系表“Movie(title, director, running_time, release_date)”和“Film(fName, fDirector, fRunningTime, fReleaseDate)”，現存匹配技術的目標是尋找成對的屬性對應關系，例如(title, fName), (director, fDirector)等。這些屬性對將被輸出作為最后的匹配結果，每個屬性對被稱為一個匹配。然而，大部分情況下，實際應用需要的是多模式匹配，也就是尋找多個屬性之間的語義對應關系。因此，針對多模式匹配技術的研究是有意義的。如果直接使用現有的匹配技術去處理多模式匹配問題，將會出現一些問題(在后面進行介紹)。

因此，本文提出通過聚類技術解決多個屬性間語義對應關系的發現問題。給定一個待匹配的屬性集合，本文的主要思路是將每個屬性看成一個空間中的點(實際上是一個向量)。然后，利用聚類技術將屬性劃分到不同的聚類中，每個聚類則代表一種語義，在同一個聚類中的屬性則具有相同或者相似的語義。在這個過程中，本文利用文獻[16]中的TFIDF(Term Frequency-Inverse Document Frequency)加權機制將每個輸入屬性轉換成空間中的點，進而應用聚類技術。

互聯網上存在大量的信息源，可以利用他們來輔助解決模式匹配問題。根據文獻[17]的調查，在互聯網的Deep Web中存在約96 000個搜索站點和5500億個隱藏的頁面。據網景公司統計，截止2008年，互聯網上存在1.6億個網站。文獻[17]經過研究發現了Web數據源的兩個非常有用的特性。第一，隨著Web規模的擴大，存在豐富的數據源提供同一領域內的結構信息。第二，隨著數據源的擴大，它們的模式詞匯總和傾向收斂于一個較小的規模。他們研究了四個領域的信息源：電子圖書、在線音樂、電影和手機，然后獲得統計數據。對于每個領域的任意數據源，其使用的所有屬性的全部詞匯量在40到60之間。因此，本文利用從Web結構信息源中抓取的模式詞匯來進一步提高模式匹配的質量。

1向量空間模型中模式屬性的轉換方法

實踐中，待集成的數據源往往多于兩個，例如，Deep Web中需要被整合的數據源往往是大量的，社交網絡中需要被分享的數據源也不僅僅是兩個。因此，多模式集成還需大量的研究工作。這一節將討論如何利用聚類技術完成多模式匹配工作。

如果直接利用傳統技術發現多屬性間的匹配，那么將會產生一些潛在的問題。傳統技術一般利用相似性分值和閾值來尋找匹配。一般通過計算兩個屬性間的相似性來作為它們的分值，例如字符串相似性，來自數據實例的統計信息的相似性等等。給定兩個屬性a1和b1，如果它們之間的相似性超過某個給定閾值，那么a1和b1被認為是相似的，即他們具有相似的語義。最后，屬性對(a1,b1)被輸出作為最后的匹配結果，習慣上稱為匹配。

然而，如果考慮三個給定屬性a1、b1和c1的匹配任務，那么一系列的問題將會出現。如果a1和b1之間的相似性分值以及a1和c1之間的相似性分值都大于給定閾值，那么我們可以得出結論a1和b1是相似的，同時a1和c1之間也是相似的，可進一步推斷出b1和c1也是相似的。這里，存在一個潛在的關于b1和c1之間的相似性問題。如果b1和c1之間的真實的相似性分值大于給定閾值，那么所得出的結論是正確的，相反，如果它們之間的分值小于這個閾值，將會得到一個矛盾：輸出一個小于給定閾值的匹配結果。

基于上面的分析，可以看出傳統的匹配技術不能用來完成多屬性間的語義對應關系發現工作。在本文的方法中，利用聚類技術解決這一問題。本文的方法分為三個階段。首先，利用信息檢索領域中被廣泛應用的向量空間模型[17]將所有的輸入屬性轉換成空間中的一個點。其次，利用DBSCAN聚類算法發現多屬性間的匹配。最后，利用Web上的結構信息源進一步提高模式匹配質量。

在向量空間模型中，文本被轉換成相關的向量，然后關于文本的處理工作就轉換成對向量的處理任務。具體地，給定一個字符串s，s被表示成一個向量，向量的每一維代表一個詞匯對應的項的權重。利用基于token[16]的方法將一個字符串解釋成一個項的集合。給定一個字符串的集合，所有字符串的項集則組成了全局的詞匯表。實際上，一個token是指一個字符串中的具有固定長度的片段(子串)，也稱為詞項。例如，字符串“conference”的長度為3的詞項集合是{“con”, “onf”, “nfe”, “fer”, “ere”, “ren”, “enc”, “nce”}。在本文的討論中，使用屬性的名字(字符串)作為屬性的表示。因此，實際上是利用屬性名字中包含的這種信息進行模式匹配。在下面的描述中，在不出現混淆的情況下，一個屬性就代表一個字符串。每個屬性都可以被轉換成一個詞項集合。令ST為所有詞項的集合，即全局詞匯。基于ST，每個屬性被表示成一個向量，向量的每一維表示一個詞項t的權重，其中t∈ST。這個權重表示一個詞項在一個屬性名中的相對重要性。給定一個屬性a，如果一個詞項t沒有在屬性a中出現，那么詞項t在屬性a所對應的向量中的權重為0，本文將通過TFIDF來計算詞項權重。TFIDF是IR(Information Retrieval)和文本挖掘領域中經常用到的加權方式。給定一個文檔集合，其利用統計數據來反應一個詞在該集合中的文檔中的重要性， TFIDF加權模式考慮了兩方面內容。第一個是詞項在文檔中出現的頻率(TF)，也就是詞項的TF越高，該詞項越重要。第二個是一個詞項在所有文檔中的出現頻率(DF)，也就是一個詞項的DF越高，則其重要性越低。原因是類似“within”、“based”、“usually”等常見的詞匯會經常出現在大部分文檔中，所以具有較高的DF。然而，這些常見的普通的詞匯對于文檔主題的表示來說是不重要的，因此，具有較高DF的詞將會被分配較低的權重。下面將給出屬性向量的每一維權重的具體計算方法。

定義1令A為所有輸入模式的屬性的全集，Ut為A中所有屬性的詞項的全集。令s為A中任意屬性對應的字符串，t為Ut中任意的詞項。則詞項t在字符串s中的權重w(s,t)被定義為：

(1)

式中，tfs,t表示詞項t在s中出現的頻率TF，|A|為A中屬性的數量，dft為t在A中出現的屬性的數量。通過上述方法，可以將每個輸入模式的屬性轉化成空間中的點，然后利用聚類技術對這些點進行劃分，處于同一個聚類中的屬性則具有相似的語義。

2基于聚類技術的語義對應關系發現

當將每個屬性看成空間中的點后， 點之間的距離則暗含了屬性之間的相似性，相似的點的集合則表示了某個語義，因此，采用聚類技術對空間中的點進行聚類。基于密度的聚類方法以密度作為聚類間差異性的度量，將聚類看作是數據空間中被低密度區域分隔開的高密度對象區域。對給定聚類中某個數據點，在該數據點的一定范圍的區域中必須至少包含某個數目的點。基于密度的聚類方法可以用來過濾噪聲或孤立點，可以發現任意形狀的聚類。這種聚類算法對數據集合中的聚類形狀以及聚類中的數據分布不敏感。DBSCAN[15]算法是經典的基于密度的聚類算法，由Ester等人在1996年提出，其基本思想是：搜索核心對象，然后利用密度可達特性對數據對象進行聚類。所謂核心對象是指滿足某個數量要求的某個鄰域內的一個對象。該算法利用“某個聚類可以由其內部的任一核心對象確定”這一性質來產生最后的聚類。DBSCAN算法具有基于密度聚類方法的典型特征，即DBSCAN可以挖掘任意形狀的聚類、聚類過程與數據的輸入順序無關，并且具有處理異常點的能力。與K-Means方法相比，DBSCAN不需要事先知道要形成的聚類的數量，DBSCAN可以發現任意形狀的聚類，DBSCAN能夠識別出噪聲點，同時DBSCAN對于數據的輸入順序不敏感，因此本文采用DBSCAN算法來對空間中的屬性點進行聚類。下面將給出DBSCAN算法的一些概念和定義。

定義2令p為一給定數據點、e為給定半徑，則稱以p為中心，以e為半徑的領域為p的e領域。

定義3令D為數據對象集合，即空間中的數據點的集合，且p∈D，那么稱p的e鄰域內的數據對象的數量為p的密度。

定義4給定一個點p，如果點p的密度超過某一給定的閾值Minpts，則稱p為核心對象。

定義5給定數據對象集合D，p、q是D中任意的數據對象，如果p是核心對象，且q在p的e鄰域內，則稱點q從點p直接密度可達。

定義6給定數據對象集合D，{p1, p2, …, pi, …, pn}是D中任意的數據對象，如果pi+1從pi關于e和Minpts直接密度可達，其中1≤i≤n-1，則稱pn從p1關于e和Minpts密度可達。

根據上述概念，現給出基于密度聚類的概念。對于給定的閾值Minpts和鄰域半徑e，一個聚類就是可以密度相連的所有數據對象的集合。密度相連具有傳遞性，因此一個聚類可以被其中的任意一個核心對象唯一確定。所以數據的輸入順序對DBSCAN算法沒有影響。DBSCAN算法的基本思想是：不斷地從數據集D中的某一點出發，查找D中所有關于閾值Minpts和鄰域半徑e的從該點密度可達的點，直至D中所有點都被遍歷。若從p點出發，且p是核心對象，則其鄰域內的所有點和p同屬于一個聚類，同時，這些點將作為下一次迭代遍歷的對象，依次從這些點出發，尋找從它們密度可達的點，重復這一過程直至所有密度可達的點都被找到，這個過程中發現的點則形成一個聚類。若p不是核心點，即沒有對象從p密度可達，則p被暫時標注為噪聲。然后，算法從D中的下一個沒有被遍歷過的點開始，重復上述過程直至D中所有數據對象都被遍歷，并將形成的聚類進行輸出，此時，若存在不屬于任何一個聚類的點，那么這些點將作為噪聲輸出。具體流程如算法1所示。

算法1基于密度聚類的多屬性匹配發現算法

輸入：A={a1,…,an}，屬性集合;

e，鄰域半徑;

Minpts，密度閾值;

輸出：C，聚類結果;

1: for each unvisited aiin D do

2:visited(ai);

//將ai標記為已訪問

3:N=getNeighbours(ai,e);

//ai的e鄰域內的點集

4:if(|N|

//將ai標記為噪聲

5:else

6:insert aito c;

//c為一個聚類

7:for each biin N do

8:visited(bi);

9:O = getNeighbours(bi,e);

10:if(|O|>=Minpts) then N=N O;

11:end if

12:if bi? any cxthen insert bito c;

13:end if

//cx為已存在的某個聚類

14:end for

15:insert c to C;

16:end if

17:end for

3利用Web信息源改進模式匹配質量

本節將會介紹如何利用Web上的結構信息源來提高最終聚類結果的質量。如上所述，互聯網上存在大量的結構信息源。據網景公司調查，截止2010年底，互聯網上存在超過1.6億個網站，而且這個數字還在不斷地增長。文獻[17]調查發現隨著數據源數量的增長，它們的詞匯總和傾向收斂于一個較小的數量規模。本文將利用這一特點來提高聚類結果的質量。

文獻[17]總結的特點可被解釋成可以從互聯網的結構信息源中為每個領域抽取一個規模較小的模式詞匯集合。這個小的模式詞匯集合可以被稱為某個領域的模式詞匯。本文的主要思想是利用這個詞匯集合來提高聚類結果的質量。待匹配的輸入模式一般來自相同或者相似的領域。給定一個來自領域H的輸入模式的集合，為輸入模式從領域H的頁面的結構信息源中抽取一個詞匯表G，然后，將G劃分成不同的集合{G1,…,Gi,…,Gq}。在同一個集合Gi中的模式元素的詞匯具有相似的語義。

本文以兩種方式使用詞匯表G，首先介紹第一種方式。在最終的聚類結果中，具有相似語義、不同表示方法的屬性經常被劃分到不同的聚類中，例如“book-Name”和“bookTitle”。本文利用詞匯表G解決這一問題。令a1和a2為最終聚類結果中屬于不同聚類的兩個屬性。如果存在Gi使得|v(a1)-v(b1)|<β∩|v(a2)-v(b2)|<β，其中b1,b2∈G1，b1≠b2，v()表示屬性對應的特征向量，β設置為0.1，那么將a2替換為a1，也就是從a2所在的聚類θi中將a2移除，并將a1加入聚類θi。目的是利用一個屬性表示多個語義相似的屬性以提高聚類結果的質量。其次，令a1為聚類θi中的一個屬性，如果在任意的一個集合Gi中，存在一個屬性b1，使得|v(a1)-v(b1)|<γ，其中γ被置為0.2，那么用b1替換a1。這里，將相似性閾值進行放寬意在使得輸入屬性更加標準和完整，例如，用“title”替換“bTitle”。當屬性替換結束后，重新運行聚類過程以得到更好的聚類結果。實驗中，我們對比了改進后的方法和原始方法。

4實驗

本節首先介紹實驗所用數據集。其次，給出關于多模式匹配算法性能的實驗結果，同時將改進后的算法與原始算法進行對比。為簡便起見，將原始算法記為DA，將改進后的算法記為IA。實驗利用信息檢索領域中經典的度量標準F-Measure作為最后匹配結果的準確性評價方法，該標準在模式匹配領域也得到了廣泛的應用。以人工得到的匹配作為標準結果，通過和標準結果進行對比來評估最后算法的有效性。算法采用C++語言實現，在PC機上運行，PC機器配置為Intel Core I5處理器，主頻3.10 GHz，4 GB內存，Win7操作系統。

通過三個不同人員開發的在線書店系統來產生實驗數據。本次實驗只考慮書目信息表，即數據庫表“book”。每個表包含16~20個字段。利用原始的三個真實的數據庫表產生32個合成的數據庫表作為實驗數據集。利用加前綴或者后綴的方式通過原有字段生成新表中的字段(例如，“t_”、“table_”、“book_”等)。主要目的是模擬實際應用中的真實情況。本文以人工的方式從“亞馬遜”和“當當”等網站抽取與書目相關的詞匯表G。G中包含大約30個模式詞匯。從生成的表集合中隨機地選擇子集作為每次實驗的數據集。

圖1給出了第一個實驗結果，該實驗測試了鄰域半徑的變化對算法性能的影響，橫坐標e則表示聚類過程中用到的鄰域半徑，e的取值范圍為[1.0, 3.0]。可以看出本文的方法具有較好的準確性，如圖1(a)所示，最好的結果接近90%。隨著e的增加算法的有效性逐漸增加，當e超過區間[1.6, 2.0]后，算法的性能開始下降，主要原因是當e超過某一范圍時，密度相連的范圍變大，即原本不是密度相連的點開始密度相連，從而導致多個聚類的合并，使算法的有效性降低。通過實驗，本文選定e的值為1.8。同時，可以看出引入的詞匯表改善了匹配結果的質量，即IA優于沒有引入詞匯表的原始算法DA。

圖1　鄰域半徑對匹配結果的影響

下面實驗研究了核心對象閾值Minpts的變化對算法性能的影響，實驗結果如圖2所示，Minpts從2增加至20。可以看出，隨著Minpts的增加，算法的性能先升高后降低。這是由于較小的閾值使得點之間的密度相連的難度降低，使得不屬于同一個聚類的點被劃分到同一個聚類中，即最后的聚類增大。當Minpts較大時，情況相反，此時的密度相連難度增加，最終得到的聚類的數量增多，但是每個聚類的體積減小(包含的點的數量減少)。通過實驗，本文選定Minpts的值為12。同時，改進后的算法要優于原始算法，這與上面實驗相符。

圖2　核心對象密度閾值的影響

最后，對輸入模式的數量對算法性能的影響進行了測試，實驗結果如圖3所示。可以看出隨著輸入模式的增加，除去輕微的局部上升趨勢之外，本文方法的準確率基本保持不變，這說明在一定的范圍內基于密度的聚類方法不受輸入模式數量的影響。同時，在圖3(b)中，由于鄰域半徑為3.0，匹配結果的準確性大幅度下降，這與圖1中的實驗結果相符。

圖3　輸入模式數量的影響

5相關工作

模式匹配是一個長期的且比較受關注的研究問題[12-23]。文獻[14]給出一個自動模式匹配方法的綜述。他們將現存的匹配技術看成匹配器，并將它們分為基于模式信息的匹配方法和基于實例信息的匹配方法。基于模式的匹配器只考慮模式自身的信息，例如模式的名稱、描述、類型等。基于實例的信息則主要探測了依賴模式而存在的數據的特性，特別是當模式信息不可用時，此種方法顯得尤為重要。

文獻[18]提出一種通用的圖匹配算法，稱為“相似性洪流”。他們的模型有一個假設前提，即如果圖中的任意兩個頂點是相似的，那么它們的鄰居之間相似性也會被增加。基于這個假設，相似性在待匹配的模式屬性之間進行傳遞。文獻[19]考慮了模式中的屬性和依賴模式存在的數據都比較模糊、難以解釋時如何進行模式匹配的情況。文獻[17]提出一種新的思路：統計模式匹配。為了進一步改善模式匹配的質量，上下文信息“context”被文獻[20]引入。所謂的“context”是指數據庫表中具有離散值的分類字段，例如人員信息表中的“性別”字段。他們利用這些分類字段作為約束條件以進一步提高匹配的質量。

文獻[21]提出一種基于corpus的匹配技術。所謂的corpus是指一個包含大量的模式和它們之間映射關系的實例集合。他們利用corpus訓練多種不同的學習機，利用這些學習機去預測給定輸入模式的匹配結果。文獻[16]提出利用數據實例副本的方式進行模式匹配。給定兩個模式，他們利用字符串比對領域的技術來發現數據實例間的重復記錄，然后利用這些重復記錄找出匹配。除上述工作外，文獻[12]利用神經網絡來發現異構數據庫中的屬性對應關系。

最近，文獻[22]提出一種新的匹配技術，稱為基于使用信息的匹配技術。他們的主要思想是利用從查詢日志中抽取一種稱為“共同出現模式”的特征來進行模式匹配。不同于傳統的匹配方法，文獻[23]提出一個新的概念“可能映射”。對于一個屬性a，“可能映射”則表示a可以被匹配給另外一個模式的多個屬性，即每個映射實例帶有一個概率值。“可能映射”可以被用來創建“可能中間模式”以描述一個查詢的多個潛在的查詢結果。然而，不存在完美的可以返回100%正確結果的匹配器，因此，模式匹配領域仍然需要大量的研究。

6結語

多個屬性之間語義對應關系的發現工作具有廣泛的應用，例如數據集成。本文提出一種利用DBSCAN聚類算法發現模式匹配的方法，利用Web上的結構信息源進一步改善模式匹配結果的質量。作為DBSCAN算法的準備工作，本文利用TFIDF加權方法將每個輸入屬性轉換為向量空間模型中的一個點。然后，利用DBSCAN算法將屬性點劃分至不同的聚類中。在同一個聚類中的屬性具有相似的語義。通過實驗比對，本文提出的算法具有較好的準確性。

參考文獻

[1] 李玉坤,孟小峰,張相於.數據空間技術研究[J].軟件學報,2008,19(8):2018-2031.

[2] 周傲英,金澈清,王國仁,等.不確定性數據管理技術研究綜述[J].計算機學報,2009,32(1):1-16.

[3] Zhang M,Chakrabarti K.InfoGather+:semantic matching and annotation of numeric and time-varying attributes in web tables[C].SIGMOD 2013:proceedings of Special Interest Group on Management Of Data,NY,USA,June 22-27,2013.New York:ACM,2013.

[4] Yakout M,Ganjam K,Chakrabarti K,et al.InfoGather: entity augmentation and attribute discovery by holistic matching with web tables[C].SIGMOD 2012:proceedings of Special Interest Group on Management Of Data,AZ,USA,May 20-24,2012.New York:ACM,2012.

[5] Peukert E,Eberius J,Erhard Rahm.A self-configuring schema matching system[C].ICDE 2012:proceedings of International Conference on Data Engineering,DC,USA,April 1-5,2012.Washington:IEEE Computer Society,2012.

[6] Qian L,Cafarella M J,Jagadish H V.Sample-driven schema mapping[C].SIGMOD 2012:proceedings of Special Interest Group on Management of Data,AZ,USA,May 20-24,2012.New York:ACM,2012.

[7] Patricia C Arocena,Boris Glavic,Renee J Miller.Value invention in data exchange[C].SIGMOD 2013:proceedings of Special Interest Group on Management Of Data,NY,USA,June 22-27,2013.New York:ACM,2013.

[8] Nguyen Quoc Viet Hung,Nguyen Thanh Tam,Zoltan Miklos,et al.Pay-as-you-go reconciliation in schema matching networks[C].ICDE 2014:proceedings of International Conference on Data Engineering,Chicago,USA,March 31-April 4,2014.Washington:IEEE Computer Society,2014.

[9] Floris Geerts,Giansalvatore Mecca,Paolo Papotti,et al.Mapping and cleaning[C].ICDE 2014:proceedings of International Conference on Data Engineering,Chicago,USA,March 31-April 4,2014.Washington:IEEE Computer Society,2014.

[10] Xin Luna Dong,Divesh Srivastava.Big data integration[C].ICDE 2013:proceedings of International Conference on Data Engineering,Brisbane,Australia,April 8-12,2013.Washington:IEEE Computer Society,2013.

[11] Franklin M,Halevy A,Maier D.From Databases to Dataspaces:A New Abstraction for Information Management[C].SIGMOD 2005:Proceedings of Special Interest Group on Management of Data,Maryland,USA,June 14-16,2005.New York:ACM,2005.

[12] Li W S,Clifton C.SEMINT:A Tool for Identifying Attribute Correspondences in Heterogeneous Databases Using Neural Networks[J].Data & Knowledge Engineering,2000,33(1):49-84.

[13] Doan A,Domingos P,Halevy A.Reconciling schemas of disparate data sources:A machine-learning approach[C].SIGMOD 2001:proceedings of Special Interest Group on Management Of Data,CA,USA,July 20-24,2001.New York:ACM,2001.

[14] Rahm E,Bernstein P A.A survey of approaches to automatic schema matching[J].Very Large Data Base Journal,2001,10(4):334-350.

[15] Ester Martin,Kriegel HansPete,Sander J?rg,et al.A density-based algorithm for discovering clusters in large spatial databases with noise[C].KDD 1996:proceedings of Discovery and Data Mining,Oregon,USA,August 20-24,1996.New York:ACM,1996.

[16] Bilke A,Naumann F.Schema Matching using Duplicates[C].ICDE 2005:proceedings of International Conference on Data Engineering,Tokyo,Japan,April 5-8,2005.Washington:IEEE Computer Society,2005.

[17] He B,Chang K C.Statistical schema matching across web query interfaces[C].SIGMOD 2003:proceedings of Special Interest Group on Management Of Data,California,USA,June 9-12,2003.New York:ACM,2003.

[18] Melnik S,GarciaMolina H,Rahm E.Similarity flooding: a versatile graph matching algorithm[C].ICDE 2002:proceedings of International Conference on Data Engineering,California,USA,26 February-1 March,2002.Washington:IEEE Computer Society,2002.

[19] Kang J,Naughton J F.On Schema Matching with Opaque Column Names and Data Values[C].SIGMOD 2003:proceedings of Special Interest Group on Management of Data,Wisconsin,USA,June 9-12,2003.New York:ACM,2003.

[20] Bohannon P,Elnahrawy E,Fan W,et al.Putting context into schema matching[C].VLDB 2006:proceedings of Very Large Data Base,Seoul,Korea,September 9-12,2003.New York:ACM,2006.

[21] Madhavan J,Bernstein P,Doan A,et al.Corpus-based schema matching[C].ICDE 2005:proceedings of International Conference on Data Engineering,Tokyo,Japan,April 5-8,2005.Washington:IEEE Computer Society,2005.

[22] Chan C,Elmeleegy H V J H,Ouzzani M,et al.Usage- Based Schema Matching[C].ICDE 2008:proceedings of International Conference on Data Engineering,Cancún,México,April 7-12,2008.Washington:IEEE Computer Society,2008.

[23] Dong X,Halevy A Y,Yu C.Data integration with uncertainty[C].VLDB 2007:proceedings of Very Large Data Base,Vienna,Austria,September 23-27,2003.New York:ACM,2007.

中圖分類號TP3

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.006

收稿日期：2014-07-16。國家自然科學基金項目(61303016)；遼寧省教育廳一般項目(L2012045)。丁國輝，講師，主研領域：數據庫模式匹配。許瑩南，講師。郭軍宏，講師。