基于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)。丁国辉，讲师，主研领域：数据库模式匹配。许莹南，讲师。郭军宏，讲师。