CN114048240A - 一种基于近似图匹配算法的数据集成方法及系统 - Google Patents

Abstract

本发明涉及一种基于近似图匹配算法的数据集成方法及系统。该方法包括将不同的数据模式分别进行图映射，确定相应的图结构；利用近似图匹配算法对所映射成的图进行图匹配，确定图结构之间的代价矩阵；根据图结构之间的代价矩阵确定图结构中节点的最优匹配序列；并根据最优匹配序列确定图编辑距离；根据最优匹配序列以及图编辑距离对图结构之间相应位置的节点进行集成。本发明能够提高异构数据的集成程度。

Description

一种基于近似图匹配算法的数据集成方法及系统

技术领域

本发明涉及数据集成领域，特别是涉及一种基于近似图匹配算法的数据集成方法及系统。

背景技术

在当前所处的数据爆炸时代下，大数据管理是正在面临的重要挑战之一，而在大数据管理的场景中，一个重要的问题就是数据集成。数据集成是协调数据源之间不匹配问题，将异构、分布、自治的数据集成在一起，为用户提供单一视图，可以透明的访问数据源。因此，对于异构数据的模式进行匹配和集成就尤为重要。数据集成领域早期研究方向主要是针对给定的数据源以及数据集，如何识别出描述相同属性，相同实体的数据表、数据列与元组之间的关联。在关联关系的挖掘方面，主要采用的是较为简单、基于字符串进行直接匹配，通过人工识别等方式完成。对于字段属性相似但字段名不一致的数据，如Name(姓名)与EmployeeName(员工姓名)，集成程度较低。

因此。亟需一种新的数据集成方法或系统，以提高异构数据的集成程度。

发明内容

本发明的目的是提供一种基于近似图匹配算法的数据集成方法及系统，能够提高异构数据的集成程度。

为实现上述目的，本发明提供了如下方案：

一种基于近似图匹配算法的数据集成方法，包括：

将不同的数据模式分别进行图映射，确定相应的图结构；

利用近似图匹配算法对所映射成的图进行图匹配，确定图结构之间的代价矩阵；

根据图结构之间的代价矩阵确定图结构中节点的最优匹配序列；并根据最优匹配序列确定图编辑距离；

根据最优匹配序列以及图编辑距离对图结构之间相应位置的节点进行集成。

可选地，所述将不同的数据模式分别进行图映射，确定相应的图结构，具体包括：

采用SQL2Graph工具，将不同的数据模式分别进行图映射，确定相应的图结构。

可选地，所述利用近似图匹配算法对所映射成的图进行图匹配，确定图结构之间的代价矩阵，具体包括：

根据不同数据模式映射的图结构，确定二分代价矩阵；

对所述二分代价矩阵进行简化构建SFBP代价矩阵。

可选地，所述根据图结构之间的代价矩阵确定图结构中节点的最优匹配序列；并根据最优匹配序列确定图编辑距离，具体包括：

在代价矩阵中采用引进元A_ij替换规则；所述引进元A_ij替换规则为相同的两个节点执行先插入再删除，或先删除再插入操作的代价值一致；其中i表示对一结构图中第i个节点进行删除操作，j表示在一结构图中插入另一结构图g中的第j个节点；

对采用引进元A_ij替换规则后的代价矩阵，采用GLA算法，确定最优匹配序列。

可选地，所述根据最优匹配序列以及图编辑距离对图结构之间相应位置的节点进行集成，具体包括：

判断所述图编辑距离是否大于距离阈值；

若所述图编辑距离大于距离阈值，则不同的数据模式为不匹配，无法进行数据集成；

若所述图编辑距离小于或等于距离阈值，则根据所述最优匹配序列对结构图进行集成。

一种基于近似图匹配算法的数据集成系统，包括：

图结构确定模块，用于将不同的数据模式分别进行图映射，确定相应的图结构；

代价矩阵确定模块，用于利用近似图匹配算法对所映射成的图进行图匹配，确定图结构之间的代价矩阵；

最优匹配序列和图编辑距离确定模块，用于根据图结构之间的代价矩阵确定图结构中节点的最优匹配序列；并根据最优匹配序列确定图编辑距离；

数据集成完成模块，用于根据最优匹配序列以及图编辑距离对图结构之间相应位置的节点进行集成。

可选地，所述图结构确定模块具体包括：

图结构确定单元，用于采用SQL2Graph工具，将不同的数据模式分别进行图映射，确定相应的图结构。

可选地，所述代价矩阵确定模块具体包括：

二分代价矩阵确定单元，用于根据不同数据模式映射的图结构，确定二分代价矩阵；

SFBP代价矩阵确定单元，用于对所述二分代价矩阵进行简化构建SFBP代价矩阵。

可选地，所述最优匹配序列和图编辑距离确定模块具体包括：

引进元A_ij替换规则单元，用于在代价矩阵中采用引进元A_ij替换规则；所述引进元A_ij替换规则为相同的两个节点执行先插入再删除，或先删除再插入操作的代价值一致；其中i表示对一结构图中第i个节点进行删除操作，j表示在一结构图中插入另一结构图g中的第j个节点；

最优匹配序列确定单元，用于对采用引进元A_ij替换规则后的代价矩阵，采用GLA算法，确定最优匹配序列。

可选地，所述数据集成完成模块具体包括：

第一判断单元，用于判断所述图编辑距离是否大于距离阈值；

若所述图编辑距离大于距离阈值，则不同的数据模式为不匹配，无法进行数据集成；

若所述图编辑距离小于或等于距离阈值，则根据所述最优匹配序列对结构图进行集成。

根据本发明提供的具体实施例，本发明公开了以下技术效果：

本发明所提供的一种基于近似图匹配算法的数据集成方法及系统，通过将两个或多个数据模式(如，XML文档，数据库中的数据等)映射为图结构，再通过近似图匹配算法对所映射成的图进行图匹配，得出图之间的代价矩阵以及图编辑距离，以此衡量图之间的相似性。在此基础上，将不同数据模式中相似的部分进行抽取，整合，达到在异构数据间的进行数据集成的目的。本发明利用图结构能更好表示对象的属性以及对象之间关系的特点，将原本抽象的数据模式映射为结构层次清晰的图，并结合近似图匹配算法，使异构数据可以较高效，较准确的进行匹配与集成。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1为本发明所提供的一种基于近似图匹配算法的数据集成方法流程示意图；

图2为映射后的结构图；

图3为本发明所提供实施例的流程示意图

图4为本发明所提供的一种基于近似图匹配算法的数据集成系统结构示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本发明的目的是提供一种基于近似图匹配算法的数据集成方法及系统，能够提高异构数据的集成程度。

为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。

图1为本发明所提供的一种基于近似图匹配算法的数据集成方法流程示意图，如图1所示，本发明所提供的一种基于近似图匹配算法的数据集成方法，包括：

S101，将不同的数据模式分别进行图映射，确定相应的图结构；

S101具体包括：

采用SQL2Graph工具，将不同的数据模式分别进行图映射，确定相应的图结构。

作为一个具体的实施例，不同的数据模式如下：

模式S1：

CREATE TABLE Personnel(

Pno int，

Pname string，

Dept string，

Born date，

UNIQUE Pkey(Pno)

)

模式S2：

CREATE TABLE Employee(

EmpNo int PRIMARY KEY，

EMpName varchar(50)，

DeptNo int REFERENCES

Department，

Salary dec(15，2)，

Birthdate date

)

CREATE TABLE Department(

DeptNo int PRIMARY KEY，

DeptName varchar(70)

)

S1是名为Personal的表，表中有四个字段，分别为类型为int的Pno，类型为string的Pname，类型为string的Dept，类型为date的Born，其中Pno为该表的唯一主键。S2包含两个表分别为Employee和Department，Employee中有5个字段分别为类型为int的唯一主键EmpNo，类型为varchar(50)的EmpName，类型为int的DeptNo，它是表Department的一个外键，类型为dec(15，2)的Salary，以及类型为date的Birthdate。表Department包含两个字段，类型为int的唯一主键DeptNo和类型为varchar(70)的DeptName。

S1与S2中的元素都是使用SQL DDL定义的表结构。借助SQL2Graph工具对以上模式进行映射G₁＝SQL2Graph(S₁)，G₂＝SQL2Graph(S₂)。映射结果如图2所示，其中，G₁为源图，G₂为目标图。

该图G₁为模式S1经过映射后所得图结构，为表示清晰，图中并未表示出Pkey等约束。图中的节点显示为椭圆形和矩形。椭圆中的标签标示节点的标识符，而矩形标示文字或者字符串值。其中上层三个椭圆为表示节点类型，此模式中有三种类型，分别为Table(表)，Column(字段)，ClolumnType(字段类型)。上图可简单表述为，节点1类型为表，其表名为Personal。节点1连接节点2、4、6、7，该四个节点类型为Column，节点所连接的name为各字段的字段名。节点3、5、8为ColumnType，节点3为int类型，节点5为string类型，节点8为date类型。节点2连接节点3，表示节点2类型为int，以此类推。

S102，利用近似图匹配算法对所映射成的图进行图匹配，确定图结构之间的代价矩阵；

S102具体包括：

根据不同数据模式映射的图结构，确定二分代价矩阵；

对所述二分代价矩阵进行简化构建SFBP代价矩阵。

作为一个具体的实施例，将以上图G₁，G₂简化，假设他们的节点数分别为|V₁|＝m以及|V₂|＝m，在两个图中添加一定的空点ε，保持两图中点的数量一致，具体如下：

此时可以得到G₁的邻接矩阵A：

G₂的邻接矩阵B：

在以上两图的定点集合基础上，构建二分代价矩阵C：

在矩阵C中，c_ij表示节点的替换操作(u_i→v_j)的代价值，c_iε表示节点的删除操作(u_i→ε)的代价值，代价矩阵C中，左上分块表示所有点替换代价值，左下分块为插入节点代价值，右上分块为删除节点代价值，右下分块为空节点之间的替换操作，因此右下分块代价值都为0。由于每个节点都只能进行一次插入或删除操作，所以左下分块和右上分块只有对角线元素为实数值，其余元素为∞。

次指派问题的图编辑路径公式：

其中

表示图标号序列(1，2，...，(n+m))所有的(n+m)！种可能的编辑距离。

假设源图和目标图的节点分别为n和m，分两种情况构建。

当n＞m时，SFBP代价矩阵如下：

不考虑对源图进行插入节点操作，将代价矩阵右上分块值为∞的元素全部替换成所在行中未实数值的元素的值。

当n＜m时，SFBP代价矩阵如下：

不考虑对源图经行节点删除操作，并将代价矩阵中左下分块中值为∞的元素的值都替换成所在列中为实数值的元素的值。

S103，根据图结构之间的代价矩阵确定图结构中节点的最优匹配序列；并根据最优匹配序列确定图编辑距离；

S103具体包括：

在代价矩阵中采用引进元A_ij替换规则；所述引进元A_ij替换规则为相同的两个节点执行先插入再删除，或先删除再插入操作的代价值一致；其中i表示对一结构图中第i个节点进行删除操作，j表示在一结构图中插入另一结构图g中的第j个节点；

对采用引进元A_ij替换规则后的代价矩阵，采用GLA算法，确定最优匹配序列。

为避免构建SFBP代价矩阵时，因不考虑对源图节点进行删除或插入操作，导致精确度缺失。引入一个新元素A_ij,其中i表示对源图G中第i个节点进行删除操作，j表示在源图G中插入目标图g中的第j个节点。元素A_ij需满足以下的条件：

(1)相同的两个节点执行先插入再删除，或先删除再插入操作的代价值一致。

(2)元素A_ij为非负数的实数。

(3)i≠j，即不能对同一节点进行删除或插入操作。

在代价矩阵中采用引进元A_ij替换规则，具体包括：

(1)当n>m：

矩阵左侧分块由c_ij构成，右侧分块主对角线上元素为源图节点进行删除操作的代价值，其余每一行的元素由A_ij中每一行元素依次对应组成。

(2)当n<m:

矩阵上方分块元素由c_ij组成，下方分块主对角元素为源图节点的添加操作代价值，其余每一行元素由A_ij中每一行元素依次对应组成。

(3)n＝m：

当A_ij<c_ij,则使用A_ij替换c_ij。

采用引进元A_ij替换规则后的代价矩阵可分为三种情况：

情况一：若该矩阵总行数大于总列数，并且当前计算元素所在列的列号大于矩阵总行数与总列数之差，则将c_ij中所有比A_ij大的元素都使用相应的A_ij进行替换。构建n维矩阵，矩阵左侧分块由c_ij构成，右侧分块主对角线上元素为源图节点进行删除操作的代价值，其余每一行的元素由c_ij中每一行元素依次对应组成。

情况二：若该矩阵总行数小于总列数，并且当前计算元素所在行的行号大于矩阵总行数和总列数之差，则把c_ij中所有比A_ij大的元素都使用相应的A_ij进行替换。构建m维矩阵，矩阵上方分块元素由c_ij组成，下方分块主对角元素为源图节点的添加操作代价值，其余每一行元素由A_ij中每一行元素依次对应组成。

情况三：若矩阵总行数等于总列数，则将c_ij中所有比A_ij小的元素使用相应的A_ij进行替换。构建n维矩阵，矩阵中元素即为c_ij中对应元素。

通过以上算法可得到以下三种不同情况下的代价矩阵：

(1)n>m:

(2)n<m：

(3)n＝m：

使用GLA算法求解图匹配问题：

第一步：将ψ置为空

第二步：逐个检查代价矩阵C中的所有节点，若其中某一节点i未被使用则进行以下计算

以及

第三步：判断i＝k是否成立。若成立则进行

并从代价矩阵C中移除第i行和第φ_i列。

否则进行计算

以及

若

成立，则从代价矩阵C中移除第i，k行和第φ_i，φ′_i列。

第四步：根据ψ中的序列求得图编辑距离数值N。

自此算法结束，返回图编辑距离数值N。

算法中ψ为节点的最优匹配序列，其基本思想是通过从代价矩阵中的第i行找到最小代价值元c_ij，并以φ_i表示该元素所在列，再从φ_i列中找到最小代价值元

并使用k表示该元素所在行。当i＝k时，c_ij即为第i行和第φ_i列的最小代价值元素，并将其添加入最优匹配序列中。若i≠k，则从第i行中找到除元c_ij之外的最小代价值元c_ij′，用φ_i′表示此元素的所在列，从k行中找到除

之外的最小元

用φ_k表示元素所在列。比较

将较小代价值的元素所在行和列添加到最优匹配序列中。对上述过程进行迭代计算，直至所有的行和列全部被分配使用，最后根据最优匹配序列计算图编辑距离。

S104，根据最优匹配序列以及图编辑距离对图结构之间相应位置的节点进行集成。

S104具体包括：

判断所述图编辑距离N是否大于距离阈值MaxN；

若所述图编辑距离N大于距离阈值MaxN，则不同的数据模式为不匹配，无法进行数据集成；

若所述图编辑距离N小于或等于距离阈值MaxN，则根据所述最优匹配序列对结构图进行集成。ψ中保存映射好的节点的行和列，将两图中对应行列上的节点进行整合即可。

如图3为本发明所提供的具体实施例的流程图，本发明能更高效的对数据模式进行匹配、集成，因为图能更好的表示对象属性以及对象之间的关系。在SFBP代价矩阵基础上引入新元A_ij，提高匹配的精确度。图结构使原数据模式之间抽象关联更清晰，可以更好的处理当下数据爆炸时代的海量异构数据匹配和集成问题。

图4为本发明所提供的一种基于近似图匹配算法的数据集成系统结构示意图，如图4所示，本发明所提供的一种基于近似图匹配算法的数据集成系统，包括：

图结构确定模块401，用于将不同的数据模式分别进行图映射，确定相应的图结构；

代价矩阵确定模块402，用于利用近似图匹配算法对所映射成的图进行图匹配，确定图结构之间的代价矩阵；

最优匹配序列和图编辑距离确定模块403，用于根据图结构之间的代价矩阵确定图结构中节点的最优匹配序列；并根据最优匹配序列确定图编辑距离；

数据集成完成模块404，用于根据最优匹配序列以及图编辑距离对图结构之间相应位置的节点进行集成。

所述图结构确定模块301具体包括：

图结构确定单元，用于采用SQL2Graph工具，将不同的数据模式分别进行图映射，确定相应的图结构。

所述代价矩阵确定模块302具体包括：

二分代价矩阵确定单元，用于根据不同数据模式映射的图结构，确定二分代价矩阵；

SFBP代价矩阵确定单元，用于对所述二分代价矩阵进行简化构建SFBP代价矩阵。

所述最优匹配序列和图编辑距离确定模块303具体包括：

引进元A_ij替换规则单元，用于在代价矩阵中采用引进元A_ij替换规则；所述引进元A_ij替换规则为相同的两个节点执行先插入再删除，或先删除再插入操作的代价值一致；其中i表示对一结构图中第i个节点进行删除操作，j表示在一结构图中插入另一结构图g中的第j个节点；

最优匹配序列确定单元，用于对采用引进元A_ij替换规则后的代价矩阵，采用GLA算法，确定最优匹配序列。

所述数据集成完成模块304具体包括：

第一判断单元，用于判断所述图编辑距离是否大于距离阈值；

若所述图编辑距离大于距离阈值，则不同的数据模式为不匹配，无法进行数据集成；

若所述图编辑距离小于或等于距离阈值，则根据所述最优匹配序列对结构图进行集成。

本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。对于实施例公开的系统而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。

本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处。综上所述，本说明书内容不应理解为对本发明的限制。

Claims (10)

1.一种基于近似图匹配算法的数据集成方法，其特征在于，包括：

将不同的数据模式分别进行图映射，确定相应的图结构；

利用近似图匹配算法对所映射成的图进行图匹配，确定图结构之间的代价矩阵；

根据图结构之间的代价矩阵确定图结构中节点的最优匹配序列；并根据最优匹配序列确定图编辑距离；

根据最优匹配序列以及图编辑距离对图结构之间相应位置的节点进行集成。

2.根据权利要求1所述的一种基于近似图匹配算法的数据集成方法，其特征在于，所述将不同的数据模式分别进行图映射，确定相应的图结构，具体包括：

采用SQL2Graph工具，将不同的数据模式分别进行图映射，确定相应的图结构。

3.根据权利要求1所述的一种基于近似图匹配算法的数据集成方法，其特征在于，所述利用近似图匹配算法对所映射成的图进行图匹配，确定图结构之间的代价矩阵，具体包括：

根据不同数据模式映射的图结构，确定二分代价矩阵；

对所述二分代价矩阵进行简化构建SFBP代价矩阵。

4.根据权利要求1所述的一种基于近似图匹配算法的数据集成方法，其特征在于，所述根据图结构之间的代价矩阵确定图结构中节点的最优匹配序列；并根据最优匹配序列确定图编辑距离，具体包括：

在代价矩阵中采用引进元A_ij替换规则；所述引进元A_ij替换规则为相同的两个节点执行先插入再删除，或先删除再插入操作的代价值一致；其中i表示对一结构图中第i个节点进行删除操作，j表示在一结构图中插入另一结构图g中的第j个节点；

对采用引进元A_ij替换规则后的代价矩阵，采用GLA算法，确定最优匹配序列。

5.根据权利要求1所述的一种基于近似图匹配算法的数据集成方法，其特征在于，所述根据最优匹配序列以及图编辑距离对图结构之间相应位置的节点进行集成，具体包括：

判断所述图编辑距离是否大于距离阈值；

若所述图编辑距离大于距离阈值，则不同的数据模式为不匹配，无法进行数据集成；

若所述图编辑距离小于或等于距离阈值，则根据所述最优匹配序列对结构图进行集成。

6.一种基于近似图匹配算法的数据集成系统，其特征在于，包括：

图结构确定模块，用于将不同的数据模式分别进行图映射，确定相应的图结构；

代价矩阵确定模块，用于利用近似图匹配算法对所映射成的图进行图匹配，确定图结构之间的代价矩阵；

最优匹配序列和图编辑距离确定模块，用于根据图结构之间的代价矩阵确定图结构中节点的最优匹配序列；并根据最优匹配序列确定图编辑距离；

数据集成完成模块，用于根据最优匹配序列以及图编辑距离对图结构之间相应位置的节点进行集成。

7.根据权利要求6所述的一种基于近似图匹配算法的数据集成系统，其特征在于，所述图结构确定模块具体包括：

图结构确定单元，用于采用SQL2Graph工具，将不同的数据模式分别进行图映射，确定相应的图结构。

8.根据权利要求6所述的一种基于近似图匹配算法的数据集成系统，其特征在于，所述代价矩阵确定模块具体包括：

二分代价矩阵确定单元，用于根据不同数据模式映射的图结构，确定二分代价矩阵；

SFBP代价矩阵确定单元，用于对所述二分代价矩阵进行简化构建SFBP代价矩阵。

9.根据权利要求6所述的一种基于近似图匹配算法的数据集成系统，其特征在于，所述最优匹配序列和图编辑距离确定模块具体包括：

引进元A_ij替换规则单元，用于在代价矩阵中采用引进元A_ij替换规则；所述引进元A_ij替换规则为相同的两个节点执行先插入再删除，或先删除再插入操作的代价值一致；其中i表示对一结构图中第i个节点进行删除操作，j表示在一结构图中插入另一结构图g中的第j个节点；

最优匹配序列确定单元，用于对采用引进元A_ij替换规则后的代价矩阵，采用GLA算法，确定最优匹配序列。

10.根据权利要求6所述的一种基于近似图匹配算法的数据集成系统，其特征在于，所述数据集成完成模块具体包括：

第一判断单元，用于判断所述图编辑距离是否大于距离阈值；

若所述图编辑距离大于距离阈值，则不同的数据模式为不匹配，无法进行数据集成；

若所述图编辑距离小于或等于距离阈值，则根据所述最优匹配序列对结构图进行集成。

Images