一种基于多哈希函数的表关系自动关联方法

摘要

本发明公开了一种基于多哈希函数的表关系自动关联方法，包括以下步骤：步骤一、获取现有的源端数据库，并根据源端数据库的连接配置，获取待发现关联关系的所有数据表；步骤二，对每一张数据表，首先获取数据表的主键，然后针对主键数据初始化一个二进制对象，并利用构造的哈希函数将源端数据库的原始数据进行映射，计算后的二进制向量与该主键序列一一对应；步骤三，根据主外键之间的引用规则，基于主键的二进制向量，对可能与主键发生关联关系的字段进行核查，核查通过则记录本条关系。解决现有数据库表中关联关系不全、数据质量不高、人工核查费时费力等问题。

说明书

技术领域

本发明属于信息技术领域，涉及一种基于多哈希函数的表关系自动关联方法。

背景技术

得益于关系型数据库及其管理系统的出现与发展，企业在数据存储、管理以及利用的效率上有了极大的提高，也直接促进了大数据技术的产生与发展。

在关系型数据库的设计阶段，第三范式限定了具有引用关系的各数据表之间通过外键进行关联。然而在实际操作过程中，随着业务的发展，数据规模在不断扩大，数据之间出现了许多新的关联关系，这些关联关系超出了数据库设计时限定的规则范围；此外，由于系统开发人员的更换等其他原因，导致数据表之间的关联关系出现断层。关联关系的缺乏，导致在进行数据分析与数据价值挖掘等工作时面临极大的困难。

以电网行业台账数据为例，在数据库系统中存储大量的台账表。随着业务的不断拓展，表的数量与规模都在不断扩大，由于开发厂商、维护人员的不同，无法将台账表之间的拓扑关系及时准确地进行更新，这就导致了各类电网实体之间引用关系变得混乱甚至丢失。

发明内容

本发明的目的是提供一种基于多哈希函数的表关系自动关联方法，解决现有数据库表中关联关系不全、数据质量不高、人工核查费时费力等问题；采用本发明中的方法，可以基于数据自动发现各个数据表之间的引用关系，从而建立清晰、完善的数据表拓扑关系。

本发明所采取的技术方案是：

一种基于多哈希函数的表关系自动关联方法，包括以下步骤：

步骤一、获取现有的源端数据库，并根据源端数据库的连接配置，获取待发现关联关系的所有数据表；

步骤二，对每一张数据表，首先获取数据表的主键，然后针对主键数据初始化一个二进制对象，并利用构造的哈希函数将源端数据库的原始数据进行映射，计算后的二进制向量与该主键序列一一对应；

步骤三，根据主外键之间的引用规则，基于主键的二进制向量，对可能与主键发生关联关系的字段进行核查，核查通过则记录本条关系。

在本发明的一个优选实施例中，还包括步骤四，记录本条关系后构建数据表拓扑关系，通过数据表拓扑关系确认相互关联的数据。

在本发明的一个优选实施例中，通过SHA256算法,SHA512算法和MD5算法构建哈希函数。

在本发明的一个优选实施例中，所述主外键之间引用规则包括：主键是一张表的唯一标识，外键通过引用主键中的内容从而将两张表关联起来。

在本发明的一个优选实施例中，所述数据表的主键形成的二进制文件保存到磁盘。

在本发明的一个优选实施例中，根据源端数据库的原始数据集合，初始化一个合适长度的二进制向量，然后根据哈希函数对原始数据进行映射并改写二进制向量的值。

在本发明的一个优选实施例中，所述原始数据集合为数据表中的明细数据。

本发明的有益效果是：

1、本发明是基于数据表中的明细数据而不是表结构或字段信息对表之间的关联关系进行自动识别，因此关系的准确性更高。

2、各主键形成的二进制文件可以保存到磁盘上，从而可以实现重复利用，降低了关联关系发现时的时间成本。

3、本发明在进行关联关系计算时，具有高度的灵活性。用户可以根据业务规则制定相应的限定条件，并添加到计算程序中，从而进一步提升关联结果的准确性。

附图说明

图1是创建一个二进制向量并检查新元素是否存在与已有元素集合中的示意图。

具体实施方式

下面结合附图和具体实施方式对本发明进行详细描述。

哈希表是一种数据结构，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，加快查找速度，这个映射函数称为哈希函数。

利用这种特定，首先可以在计算机内存中分配一段定长的空间用于存储二进制向量，然后构造多个哈希函数，每一个哈希函数对于输入的值均映射到一个位置上，然后将二进制向量中该位置上的值设置进行更改。可以证明，利用这种数据结构和哈希函数的映射，可以用于非常快地判断一个元素是否存在于某个集合中。

第一部分：基本原理及验证方法

所谓二进制向量的含义，即该向量的每个位置上的取值为0或者1。初始化的一个二进制向量的所有位置上的值均为0，其长度记为m。哈希函数的作用是将任意值映射成固定区间[1，m]内的一个整数。为了降低重复率，一般采用多个哈希函数，其个数记为k。对于原始集合L中的任意一个元素，经过k个哈希函数映射之后得到k个值，代表二进制向量中的k个位置，然后将这k个位置上的值改写为1。将L中所有的值进行类似的映射之后得到的新的二进制向量，就称为填充后的、与L一一对应的二进制向量。

如图1所示，假设二进制向量的长度m＝18，哈希函数个数k＝3，一共有3个元素需要进行转换。图中的向量为转换之后的二进制向量。对于一个新的值w，利用相同的3个哈希函数进行计算并得到三个位置，如果该三个位置上的值均为1，则说明w大概率存在于原始数据集合中(即3个元素)；否则，w一定不在原始数据集合中。

第二部分：误判概率分析

由于哈希函数的随机性，不同的元素也有可能被映射到相同的位置上，从而得到“该元素存在于原始集合中”的错误结论。很容易想到，如果原始集合中的数据量足够大，或者二进制向量的长度不够长，那么发生误判的概率会增大。在实际应用过程中，知道集合中的元素个数并给定一个较小的误判概率，可以推导出不高于该误判概率的所需要的最小的二进制向量的长度。

假设哈希函数的选取足够的好，对于初始化的二进制向量，一个哈希函数将一个位置设置为1的概率是

由于n及m的取值一般都很大，在极限情况下，即当

m→+∞时，有：

p(误判)＝(1-e

通过数学推导，假定n/m为固定值，那么要想使p最小，哈希函数个数k满足的条件为：

进一步，若n已知，对于设定的误判率p，将k的取值代入误判率计算公式，可以得到所需要的二进制向量的最小长度：

第三部分：构建二进制向量

根据原始数据集合，初始化一个合适长度的二进制向量。然后根据哈希函数对原始数据进行映射并改写二进制向量的值。为了复用，可以将其存储至磁盘上，注意在存储的过程中，构造的哈希函数也要一并进行存储。

第四部分：关联数据核查

利用生成目标主键的二进制向量的哈希函数来对待核查数据进行映射，计算映射后的位置上的值是否为1来判断该值是否在主键数据中。在实际应用中，由于数据质量的问题，可以设置一个阈值来允许一部分数据不在主键集合中。

具体地一种基于多哈希函数的表关系自动关联方法，包括以下步骤：步骤一、获取现有的源端数据库，并根据源端数据库的连接配置，获取待发现关联关系的所有数据表；步骤二，对每一张数据表，首先获取数据表的主键，然后针对主键数据初始化一个二进制对象，并利用构造的哈希函数将源端数据库的原始数据进行映射，计算后的二进制向量与该主键序列一一对应；步骤三，根据主外键之间的引用规则，基于主键的二进制向量，对可能与主键发生关联关系的字段进行核查，核查通过则记录本条关系。还包括步骤四，记录本条关系后构建数据表拓扑关系，通过数据表拓扑关系确认相互关联的数据。

以电网行业台账数据为例，在数据库系统中存储大量的台账表。随着业务的不断拓展，表的数量与规模都在不断扩大，由于开发厂商、维护人员的不同，无法将台账表之间的拓扑关系及时准确地进行更新，这就导致了各类电网实体之间引用关系变得混乱甚至丢失。采用上述方法，利用哈希函数，通过上述步骤，能迅速将相同或关联的台账数据进行整合，节省了人力比对，准确率高。