基于分布拟合的网络表格间的外键关系检测方法

摘要

本发明提供了一种基于分布拟合的网络表格间的外键关系检测方法。该方法包括：检测网络表格间不同属性列之间的包含覆盖关系，根据包含覆盖关系的检测结果筛选出所述网络表格间的候选外键关系对；构建候选外键关系对中候选外键和候选主键的多维分布图，计算出候选外键和候选主键的多维分布图之间的拟合度；根据候选外键和候选主键的多维分布图之间的拟合度判断候选外键关系对是否为真正的外键关系对。本发明既适用于字符类型的外键关系检测，也适用于数字类型的外键关系检测，既能检测单列的外键关系，也能检测多列的外键关系，在具有较高的检测准确性的同时兼具较高的检测效率。

权利要求

1.一种基于分布拟合的网络表格间的外键关系检测方法，其特征在于，包括：

检测网络表格间不同属性列之间的包含覆盖关系，根据所述包含覆盖关系的检测结果筛选出所述网络表格间的候选外键关系对；

构建所述候选外键关系对中候选外键和候选主键的多维分布图，计算出所述候选外键和候选主键的多维分布图之间的拟合度；

根据所述候选外键和候选主键的多维分布图之间的拟合度判断所述候选外键关系对是否为真正的外键关系对；

所述的检测网络表格间不同属性列之间的包含覆盖关系，根据所述包含覆盖关系的检测结果筛选出所述网络表格间的候选外键关系对，包括：将待检测的网络表格集合中的表格按照列存储到列集合中，对所述列集合中的字符型属性列进行模糊匹配，对所述列集合中的数字型属性列进行数值匹配，根据所述模糊匹配和数值匹配的匹配结果查找出所述列集合中的所有单列的属性对；

从所有单列的属性对中检测出来自相同表格的多列的属性对，对于检测出的所有单列IND，查找是否存在n个来自同一个表格的属性列集合A包含于来自另一个表格的n个属性列的集合B，若存在，则将A与B组成的属性对作为多列IND；

判断所有单列的属性对和多列的属性对是否满足设定的主键唯一性条件，所述设定的主键唯一性条件包括主键中的重复值小于设定的阈值λ，将满足所述设定的主键唯一性条件的单列的属性对和多列的属性对作为候选外键关系对，每个候选外键关系对包括候选外键F和候选主键P；

所述的构建所述候选外键关系对中候选外键和候选主键的多维分布图，包括：

针对每个候选外键关系对，为候选外键F的每个列的列值进行排序，并获得该列中每个值的位置，将每列对应多维空间的一个维度，再对分布于每个维度上的每个列的列值的位置进行哈希映射，得到候选外键F的多维分布图；为候选主键P的每个列的列值进行排序，并获得该列中每个值的位置，将每列对应多维空间的一个维度，再对分布于每个维度上的每个列的列值的位置进行哈希映射，得到候选主键P的多维分布图。

2.根据权利要求1所述的方法，其特征在于，所述的计算出所述候选外键和候选主键的多维分布图之间的拟合度，包括：对所述候选外键F和候选主键P的多维分布图进行分区；

根据分区后的所述候选外键F和候选主键P的多维分布图，确定候选外键F中的值应该落入候选主键P的多维分布图的每个分区的个数，该个数称为理论频数，统计候选外键F中的值实际落入候选主键P的多维分布图的每个分区的实际个数，该实际个数称为观测频数，根据所述理论频数和观测频数计算出所述候选主键P和所述候选外键F的多维分布图之间的整体偏差；

根据所述整体偏差确定所述候选外键F和候选主键P的两个多维分布图之间的拟合度。

3.根据权利要求2所述的方法，其特征在于，所述的对所述候选外键F和候选主键P的多维分布图进行分区，包括：设定子空间的点数阈值s，对于每个k维多维分布图，在每个维度上将相应的区间划分成相等的两个部分，得到2k个子空间，将所述2k个子空间中点数超过阈值s的子空间继续划分为2k个子空间，将得到的点数超过阈值s的子空间继续进行划分，并且以这种方式迭代，直到每个子空间中的点数都小于或等于阈值s。

4.根据权利要求2所述的方法，其特征在于，所述的根据分区后的所述候选外键F和候选主键P的多维分布图，确定候选外键F中的值应该落入候选主键P的多维分布图的每个分区的个数，该个数称为理论频数，统计候选外键F中的值实际落入候选主键P的多维分布图的每个分区的实际个数，该实际个数称为观测频数，根据所述理论频数和观测频数计算出所述候选主键P和所述候选外键F的多维分布图之间的整体偏差，包括：已知包含k列属性值的候选主键P的多维分布图G，令 作为P在第i列的分区的集合，GP＝F1×...Fk被定义为P的k维分区图，由n1×...×nk个k维子空间组成，用Nsub(GP)表示分区图GP中子空间的总数：候选外键F对应于GP的第t个子空间的观测频数 被定义为F实际落在GP的第t个子空间的值的个数，通过将候选外键F第t个子空间中的属性值与P中第t个子空间中属性值进行匹配，并将其中匹配相同的属性值的个数记为观测频数候选外键F对应于GP的第t个子空间的理论频数被定义为F理论上应该落在GP的第t个子空间的值的个数，记为其中FNumall(F)表示候选外键F中所有值的个数，PNumt(P)表示GP中第t个子空间内的值的个数，PNumall(P)表示候选主键P中所有不同值的个数；

所述候选主键P和所述候选外键F的多维分布图之间的整体偏差Dev(F,P)通过以下公式计算：

5.根据权利要求4所述的方法，其特征在于，所述的根据所述整体偏差确定所述候选外键F和候选主键P的两个多维分布图之间的拟合度，包括：所述候选外键F和候选主键P的两个多维分布图之间的拟合度GOF(F,P)的计算公式如下：其中a是调整单调性的参数，a>1。

6.根据权利要求1至5任一项所述的方法，其特征在于，所述的根据所述候选外键和候选主键的多维分布图之间的拟合度判断所述候选外键关系对是否为真正的外键关系对，包括：如果所述候选外键F和所述候选主键P的两个多维分布图之间的拟合度大于设定的阈值，则判断所述候选外键F和候选主键P是一对真正的外键关系。

说明书

基于分布拟合的网络表格间的外键关系检测方法

技术领域

[0001] 本发明涉及网络信息处理技术领域，尤其涉及一种基于分布拟合的网络表格间的外键关系检测方法。

背景技术

[0002] 互联网上包含大量的结构化表格，为数据集成和检索提供了非常方便和丰富的数据集。为了增强网络表格间的联系和有效利用网络上公开的表格数据，Anish等人试图探测网络表格间潜在的关系，并找到关联表格。而外键关系作为数据库中最重要的约束之一，对于模式设计者来说是非常有价值的，可以用来指定两个语义相关的表格。然而对于来自异构数据源的大量的网络表格，在大多数情况下不会指定外键。因此，发现外键关系是理解和利用网络表格的重要步骤。

[0003] 目前，现有技术中的外键关系检测方法大都集中于识别表格间的包含依赖关系。但是，仅仅通过包含覆盖来检测外键关系是不够的，最直接的方法是找到真正外键关系应该满足的重要特征。Alexandra Rostin等人提出了一些规则，例如列名相似度、列值平均长度、列值的唯一性和覆盖率等一系列特征，并以此来发现传统关系表上的单列外键关系。但是，对于存在模式信息缺失和噪声数据的网络表格，以上方法并不适用。

[0004] Meihui Zhang等人提出利用随机性来替代上述外键关系应满足的一系列规则，并将其应用到了单列和多列外键关系检测中。该方法仅通过属性列列值的分布评估两列数据分布的随机性，并且利用随机性的大小来筛选真正的外键关系。在该方法中，Earth Mover's Distance(EMD，搬土距离)被用来衡量外键中的一组属性值转移到主键中另一组属性值集合上所需要的工作量，并以此值标示随机性大小。当外键值仅在主键的某个区域内均匀分布时，EMD仍会被计算为一个很小的值。

[0005] 上述现有技术中的外键关系检测方法存在的问题如下：

[0006] (1)由于网络表格并不规范，数据会存在噪声及表头缺失的问题，目前大部分依靠表格结构特征的外键检测方法只适用于传统关系表，并不适用于网络表格。

[0007] (2)目前的外键检测算法大都只适用于字符型外键关系的检测，并不适用于数字型外键关系的检测。

[0008] (3)目前的外键检测算法是对单列外键关系进行检测，或者，通过随机性进行多列外键关系检测，这些方法并不能保证外键在主键中分布的随机性，由于不能解决局部随机性问题，效果并不理想。

发明内容

[0009] 本发明实施例提供了一种基于分布拟合的网络表格间的外键关系检测方法，以克服现有技术的问题。

[0010] 为了实现上述目的，本发明采取了如下技术方案。

[0011] 一种基于分布拟合的网络表格间的外键关系检测方法，包括：

[0012] 检测网络表格间不同属性列之间的包含覆盖关系，根据所述包含覆盖关系的检测结果筛选出所述网络表格间的候选外键关系对；

[0013] 构建所述候选外键关系对中候选外键和候选主键的多维分布图，计算出所述候选外键和候选主键的多维分布图之间的拟合度；

[0014] 根据所述候选外键和候选主键的多维分布图之间的拟合度判断所述候选外键关系对是否为真正的外键关系对。

[0015] 进一步地，所述的检测网络表格间不同属性列之间的包含覆盖关系，根据所述包含覆盖关系的检测结果筛选出所述网络表格间的候选外键关系对，包括：

[0016] 将待检测的网络表格集合中的表格按照列存储到列集合中，对所述列集合中的字符型属性列进行模糊匹配，对所述列集合中的数字型属性列进行数值匹配，根据所述模糊匹配和数值匹配的匹配结果查找出所述列集合中的所有单列的属性对；

[0017] 从所有单列的属性对中检测出来自相同表格的多列的属性对，对于检测出的所有单列IND，查找是否存在n个来自同一个表格的属性列集合A包含于来自另一个表格的n个属性列的集合B，若存在，则将A与B组成的属性对作为多列IND；

[0018] 判断所有单列的属性对和多列的属性对是否满足设定的主键唯一性条件，所述设定的主键唯一性条件包括主键中的重复值小于设定的阈值λ，将满足所述设定的主键唯一性条件的单列的属性对和多列的属性对作为候选外键关系对，每个候选外键关系对包括候选外键F和候选主键P。

[0019] 进一步地，所述的构建所述候选外键关系对中候选外键和候选主键的多维分布图，包括：

[0020] 针对每个候选外键关系对，为候选外键F的每个列的列值进行排序，并获得该列中每个值的位置，将每列对应多维空间的一个维度，再对分布于每个维度上的每个列的列值的位置进行哈希映射，得到候选外键F的多维分布图；为候选主键P的每个列的列值进行排序，并获得该列中每个值的位置，将每列对应多维空间的一个维度，再对分布于每个维度上的每个列的列值的位置进行哈希映射，得到候选主键P的多维分布图。

[0021] 进一步地，所述的计算出所述候选外键和候选主键的多维分布图之间的拟合度，包括：

[0022] 对所述候选外键F和候选主键P的多维分布图进行分区；

[0023] 根据分区后的所述候选外键F和候选主键P的多维分布图，确定候选外键F中的值应该落入候选主键P的多维分布图的每个分区的个数，该个数称为理论频数，统计候选外键F中的值实际落入候选主键P的多维分布图的每个分区的实际个数，该实际个数称为观测频数，根据所述理论频数和观测频数计算出所述候选主键P和所述候选外键F的多维分布图之间的整体偏差；

[0024] 根据所述整体偏差确定所述候选外键F和候选主键P的两个多维分布图之间的拟合度。

[0025] 进一步地，所述的对所述候选外键F和候选主键P的多维分布图进行分区，包括：

[0026] 设定子空间的点数阈值s，对于每个k维多维分布图，在每个维度上将相应的区间划分成相等的两个部分，得到2k个子空间，将所述2k个子空间中点数超过阈值s的子空间继续划分为2k个子空间，将得到的点数超过阈值s的子空间继续进行划分，并且以这种方式迭代，直到每个子空间中的点数都小于或等于阈值s。

[0027] 进一步地，所述的根据分区后的所述候选外键F和候选主键P的多维分布图，确定候选外键F中的值应该落入候选主键P的多维分布图的每个分区的个数，该个数称为理论频数，统计候选外键F中的值实际落入候选主键P的多维分布图的每个分区的实际个数，该实际个数称为观测频数，根据所述理论频数和观测频数计算出所述候选主键P和所述候选外键F的多维分布图之间的整体偏差，包括：

[0028] 已知包含k列属性值的候选主键P的多维分布图G，令 作为P在第i列的分区的集合，GP＝F1×...Fk被定义为P的k维分区图，由n1×...×nk个k维子空间组成，用Nsub(GP)表示分区图GP中子空间的总数：

[0029]

[0030] 候选外键F对应于GP的第t个子空间的观测频数 被定义为F实际落在GP的第t个子空间的值的个数，通过将候选外键F第t个子空间中的属性值与P中第t个子空间中属性值进行匹配，并将其中匹配相同的属性值的个数记为观测频数

[0031] 候选外键F对应于GP的第t个子空间的理论频数被定义为F理论上应该落在GP的第t个子空间的值的个数，记为

[0032]

[0033] 其中FNumall(F)表示候选外键F中所有值的个数，PNumt(P)表示GP中第t个子空间内的值的个数，PNumall(P)表示候选主键P中所有不同值的个数；

[0034] 所述候选主键P和所述候选外键F的多维分布图之间的整体偏差Dev(F,P)通过以下公式计算：

[0035]

[0036] 进一步地，所述的根据所述整体偏差确定所述候选外键F和候选主键P的两个多维分布图之间的拟合度，包括：

[0037] 所述候选外键F和候选主键P的两个多维分布图之间的拟合度GOF(F,P)的计算公式如下：

[0038]

[0039] 其中a是调整单调性的参数，a>1。

[0040] 进一步地，所述的根据所述候选外键和候选主键的多维分布图之间的拟合度判断所述候选外键关系对是否为真正的外键关系对，包括：

[0041] 如果所述候选外键F和所述候选主键P的两个多维分布图之间的拟合度大于设定的阈值，则判断所述候选外键F和候选主键P是一对真正的外键关系。

[0042] 由上述本发明的实施例提供的技术方案可以看出，本发明实施例的算法既适用于字符类型的外键关系检测，也适用于数字类型的外键关系检测，既能检测单列的外键关系，也能检测多列的外键关系；最后，对该外键检测算法进行优化，给出时间复杂度较低的多次划分算法，以便有效地扩展到大型网络表格中。本发明实施例的算法在具有较高的检测准确性的同时兼具较高的检测效率。

[0043] 本发明附加的方面和优点将在下面的描述中部分给出，这些将从下面的描述中变得明显，或通过本发明的实践了解到。

附图说明

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

[0045] 图1为本发明实施例提供的一种基于分布拟合的网络表格间的外键关系检测方法的实现原理图；

[0046] 图2为本发明实施例提供的一种基于分布拟合的网络表格间的外键关系检测方法的处理流程图；

[0047] 图3为本发明实施例提供的一种候选外键关系的查找流程图；

[0048] 图4为本发明实施例提供的一种分布拟合检验流程图；

[0049] 图5为本发明实施例提供的一种多维分布图的多次划分示意图；

[0050] 图6为本发明实施例提供的一种优化分区算法流程图。

具体实施方式

[0051] 下面详细描述本发明的实施方式，所述实施方式的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施方式是示例性的，仅用于解释本发明，而不能解释为对本发明的限制。

[0052] 本技术领域技术人员可以理解，除非特意声明，这里使用的单数形式“一”、“一个”、“所述”和“该”也可包括复数形式。应该进一步理解的是，本发明的说明书中使用的措辞“包括”是指存在所述特征、整数、步骤、操作、元件和/或组件，但是并不排除存在或添加一个或多个其他特征、整数、步骤、操作、元件、组件和/或它们的组。应该理解，当本发明实施例称元件被“连接”或“耦接”到另一元件时，它可以直接连接或耦接到其他元件，或者也可以存在中间元件。此外，这里使用的“连接”或“耦接”可以包括无线连接或耦接。这里使用的措辞“和/或”包括一个或更多个相关联的列出项的任一单元和全部组合。

[0053] 本技术领域技术人员可以理解，除非另外定义，这里使用的所有术语(包括技术术语和科学术语)具有与本发明所属领域中的普通技术人员的一般理解相同的意义。还应该理解的是，诸如通用字典中定义的那些术语应该被理解为具有与现有技术的上下文中的意义一致的意义，并且除非像这里一样定义，不会用理想化或过于正式的含义来解释。

[0054] 为便于对本发明实施例的理解，下面将结合附图以几个具体实施例为例做进一步的解释说明，且各个实施例并不构成对本发明实施例的限定。

[0055] 本发明实施例提出了一种可以适用于网络表格，能同时处理数字型和字符型外键关系，单列和多列外键关系的外键检测算法，该算法具有较高的准确性和执行效率。

[0056] 本发明综合考虑多种数据类型的外键关系以及网络表格的噪声数据，提出一种基于分布拟合的外键关系检测算法。首先，通过检测网络表格间的包含覆盖关系来找到候选外键关系，为了处理网络表格中的不一致数据，通过放宽外键关系需满足的条件来进行候选外键关系的筛选；其次，受数理统计中分布拟合思想的启发，认为外键列中的值应该与主键列中的值具有相同的分布，并利用分布拟合检验从所有候选外键关系中找到真正的外键关系。

[0057] 本发明实施例提供的一种基于分布拟合的网络表格间的外键关系检测方法的实现原理图如图1所示，具体处理流程如图2所示，包括如下的处理步骤：

[0058] 步骤1、检测网络表格间不同属性列之间的包含覆盖关系，根据所述包含覆盖关系的检测结果筛选出所述网络表格间的候选外键关系对。

[0059] 步骤2、构建所述候选外键关系对中候选外键和候选主键的多维分布图，计算出所述候选外键和候选主键的多维分布图之间的拟合度。

[0060] 步骤3、根据所述候选外键和候选主键的多维分布图之间的拟合度判断所述候选外键关系对是否为真正的外键关系对。

[0061] 图3为本发明实施例提供的一种候选外键关系的查找流程图，具体处理过程包括：与关系数据库中的表格不同，网络表格来自不同的数据源，不一定有完整的模式信息，因此只能利用属性值来查找外键关系。同时，本发明实施例从三个方面放宽外键关系应满足的特性，以适应网络表格中的数据噪声和数据不一致的特点。

[0062] (1)列值匹配性。对于网络表格中不同类型的列值，本发明实施例采用不同的匹配方法。对字符串类型的数据，本发明实施例使用基于Jaro Winkler Distance的模糊相似度匹配方法，并设置一个阈值δ来处理网络表中的噪声数据。对于数值型数据，本发明实施例使用数值匹配。

[0063] 当查找单列IND时，我们需要对列间的包含覆盖率进行检测，将包含覆盖率高于某个阈值μ的属性对作为单列IND输出。检测过程中，我们通过匹配两列间的属性值，根据具有匹配关系的属性值的个数计算列之间的包含覆盖率。对于字符串类型的数据，我们采用Jaro–Winkler Distance方法进行模糊匹配，将高于阈值δ的属性值作为匹配值，低于阈值δ的属性值作为不匹配值。对于数值型数据，采用精确匹配的结果作为属性值是否匹配的依据。

[0064] (2)主键唯一性。由于网络表格没有规范化，它很难满足主键唯一性。本发明实施例允许主键中有少量的重复值，并设置一个阈值λ用于处理主键的非唯一性，即主键中的重复值小于设定的阈值λ。

[0065] (3)包含覆盖性。为了处理数据不一致问题，本发明实施例放宽了候选属性对之间必须满足的包含关系，并为上述包含关系设置阈值μ。

[0066] 首先获取网络表格集合，将网络表格集合中的表格按照列存储到列集合中。作为外键关系检测的第一步，本发明实施例首先需要找到所有满足包含覆盖关系的属性对，该属性对包括单列的属性对，称作单列IND(inclusion dependency,包含覆盖对)，以及多列的属性对，称作多列IND。对上述列集合中的字符型属性列进行模糊匹配，对上述列集合中的数字型属性列进行数值匹配，其中数值匹配采用精确匹配的方法，模糊匹配采用了Jaro–Winkler Distance方法。根据上述模糊匹配和数值匹配的匹配结果查找出上述列集合中的所有单列IND。

[0067] 当查找单列IND时，我们需要对列间的包含覆盖率进行检测，将包含覆盖率高于阈值μ的属性对作为单列IND输出。检测过程中，我们通过匹配两列间的属性值，根据具有匹配关系的属性值的个数计算列之间的包含覆盖率。对于字符串类型的数据，我们采用Jaro–Winkler Distance方法进行模糊匹配，将高于阈值δ的属性值作为匹配值，低于阈值δ的属性值作为不匹配值。对于数值型数据，采用精确匹配的结果作为属性值是否匹配的依据。

[0068] 检测所有的单列IND中是否有包含来自相同表格的多列IND。对于检测出的所有单列IND，我们查找是否存在n个来自同一个表格的属性列集合A包含于来自另一个表格的n个属性列的集合B，若存在，我们则将A与B组成的属性对作为多列IND。

[0069] 随后针对所有单列IND以及多列IND，判断它们是否满足本发明实施例设定的主键唯一性条件，将满足上述主键唯一性条件的单列IND和多列IND作为候选外键关系对，每个候选外键关系对中包括候选外键F和候选主键P。单列IND形成的候选外键关系对中的候选外键F和候选主键P中只包括单列。

[0070] 图4为本发明实施例提供的一种分布拟合检验流程图，通过分布拟合从所有的候选外键关系中找到真正的外键关系。从图4中可以看出本发明实施例的分布拟合过程主要分为以下四个部分：

[0071] (1)多维分布图构建。对于每个候选外键关系对，本发明实施例为候选外键F的每个列的列值进行排序，并获得该列中每个值的位置。将每列对应多维空间的一个维度，再对分布于每个维度上的每个列的列值的位置进行哈希映射，得到候选外键F的多维分布图。同理，可以得到候选主键P的多维分布图。

[0072] (2)多维分布图分区。为了得到候选外键F和候选主键P的两个多维分布图之间的拟合程度，本发明实施例将候选外键F和候选主键P的两个多维分布图进行分区。直观地说，当且仅当两个多维分布图在每个分区中的分布高度拟合时，两个多维分布图才算高度拟合。

[0073] (3)频数统计。在对候选外键F和候选主键P的两个多维分布图进行分区之后，本发明实施例需要确定候选外键F中的值应该落入候选主键P的多维分布图的每个分区的个数，该个数称为理论频数。同时，本发明实施例还需要统计候选外键F中的值实际落入候选主键P的多维分布图的每个分区的实际个数，该实际个数称为观测频数。

[0074] (4)拟合度计算。在得到所述候选主键P的多维分布图中每个分区的理论频数和观测频数之后，本发明实施例可以通过评估所述候选主键P的所有分区的理论频数和观测频数之间的整体偏差来计算候选外键F和候选主键P的两个多维分布图之间的拟合度。显然，整体偏差值越小，拟合度越高。如果候选外键F和候选主键P的两个多维分布图之间的拟合度大于设定的阈值，则判断候选外键F和候选主键P是一对真正的外键关系。

[0075] 为了判断两个分布的拟合程度，本发明实施例尝试构造它们的多维分布图。

[0076] 定义1.多维分布图：对于给定的具有k列的P或F，P或F中的所有值可以散列为k维空间中的点。本发明实施例将由坐标轴和这些点组成的散点图称为P或F的多维分布图。

[0077] 为了构造P的多维分布图，本发明实施例首先对P中每列的值重新排序。对于数值型，本发明实施例将它们按值排序；对于字符串，本发明实施例按字母顺序对它们进行排序。在定义好每列值的顺序之后，本发明实施例根据每个值在列中的顺序执行哈希映射，将P中所有值散列为k维空间中的点。

[0078] 为了精确地评估两个分布之间的拟合程度，本发明实施例需要将它们的多维分布图划分成若干子空间，并评估每对子空间之间的拟合程度。

[0079] 定义2.分区图：已知包含k列属性值的P的多维分布图G，令 作为P在第i列的分区的集合(不同列可能有不同的分区个数)。GP＝F1×...Fk被定义为P的k维分区图，由n1×...×nk个k维子空间组成。

[0080] 本发明实施例使用Nsub(GP)来表示分区图GP中子空间的总数

[0081]

[0082] 定义3.观测频数：给定P的分区图GP，以及F对应于P的多维分布图，F对应于GP的第t个子空间的观测频数 被定义为F实际落在GP的第t个子空间的值的个数。

[0083] 观测频数通过将F第t个子空间中的属性值与P中第t个子空间中属性值进行匹配，并将其中匹配相同的属性值的个数记为观测频数

[0084] 定义4.理论频数：给定P的分区图GP，以及F对应于P的多维分布图，F对应于GP的第t个子空间的理论频数被定义为F理论上应该落在GP的第t个子空间的值的个数，记为[0085]

[0086] 其中FNumall(F)表示F中所有值的个数；PNumt(P)表示GP中第t个子空间内的值的个数；PNumall(P)表示P中所有不同值的个数。由于网络表格格式并不严密，主键的唯一度达不到100％，因此P中可能存在重复值，此处P中不同值的个数PNumall(P)为剔除重复属性值后的属性值个数。

[0087] GP的各子空间中F的理论频数与观测频数的差值反映了该子空间中局部分布的拟合程度。差值越小，拟合度越好。因此，为了评估两个分布的整体拟合程度，本发明实施例定义总体偏差，总体偏差是局部分布之间的局部偏差的总和。

[0088] 定义5.总体偏差：给定P的分区图GP，以及F对应于P的多维分布图，F对应于P的总体偏差Dev(F,P)可以通过以下公式计算：

[0089]

[0090] 在得到候选外键关系对(F,P)的总体偏差值后，本发明实施例可以评估这个候选外键关系对中F和P的拟合程度。为了使结果更直观，本发明实施例将偏差值归一化，改变其单调性，定义6中给出拟合度的定义。

[0091] 定义6.拟合度：给定P的分区图GP，以及F对应于P的多维分布图，F对应于P的拟合度GOF(F,P)为：

[0092]

[0093] 其中a是调整单调性的参数，本发明实施例设置a>1。

[0094] 在计算出所有候选外键关系的拟合度后，本发明实施例可以通过评估他们的拟合度大小来确定这些候选外键关系对是否真正的外键关系。评估过程中的输入数据为上一阶段得到的候选外键关系集合，输出为Top-k个拟合度最大的候选外键关系对。首先进行多维分布图构建；然后分区；随后对每个分区计算理论频数和实际频数；并通过计算总体的偏差值进而得到分布拟合度。最后根据计算得到的拟合度排序后，取Top-k个候选外键关系对存储到文件中，作为输出。

[0095] 为了从候选外键关系中找出真正的外键关系，本发明实施例为所有的单列和多列的候选外键关系对构造多维分布图，然后将每个P的多维分布图划分成小的子空间。划分多维分布图最简单的方法是平等地划分每个维度，子空间被分割得越细，得到的GOF越准确。但是，随着子空间的增多，GOF计算的成本呈现指数级增长，特别是对于大型的网络表格。

[0096] 图5为本发明实施例提供的一种多维分布图的多次划分示意图，事实上，当多维分布图被均等地划分为各个小分区时，图中所有点在子空间中的分布可能并不均匀，甚至会出现一些空的子空间，其中没有任何点。出于以上原因，本发明实施例提出优化的分区方法，以确保本发明实施例的外键检测算法遇到大型网络表格时仍然可以快速地评估GOF。

[0097] 本发明实施例采用多遍划分的策略。对于每个k维多维分布图，首先在每个维度上将相应的区间划分成相等的两个部分，得到2k个子空间。下一步本发明实施例只划分其中点数超过s的子空间，并且以这种方式迭代，直到每个子空间中的点数都小于或等于s。在m次划分之后，分区图GP中的子空间的总数Nsub(GP)变为：

[0098] Nsub(GP)＝2k+(m-1)(2k-1)   (5)

[0099] 如图5所示，给定k＝2和s＝5，本发明实施例只需要对P的多维分布图进行两次划分，就可以确保每个子空间中的点数小于或等于5。分割后，分区图中包含7个子空间，这意味着本发明实施例仅需计算7个理论频数。与原始分割方法(16个子空间与16个理论频数)相比，本发明实施例的多次划分方法可以大大降低成本。

[0100] 图6为本发明实施例提供的一种优化分区算法流程图。输入为分区大小和k维多维分布图，输出为经过多次划分后得到的分区。本发明实施例首先通过将原始多维分布图的每个维度等分为两部分得到初始分区图。然后，本发明实施例在初始分区图中找出点数超过分区大小的一组子空间，对于其中的每个子空间进行二次划分。经多次迭代，本发明实施例得到最终的分区图。

[0101] 综上所述，本发明实施例的算法既适用于字符类型的外键关系检测，也适用于数字类型的外键关系检测，既能检测单列的外键关系，也能检测多列的外键关系；最后，对该外键检测算法进行优化，给出时间复杂度较低的多次划分算法，以便有效地扩展到大型网络表格中。本发明实施例的算法在具有较高的检测准确性的同时兼具较高的检测效率。

[0102] 本发明实施例的算法针对网络表格中存在数据噪声以及数据不一致的特点，放宽了候选外键需满足的列值匹配性、主键唯一性、包含覆盖性三个特征，以提升网络表格中候选外键关系检测的准确性。该算法从候选外键关系中检测出真正的外键关系，根据属性值分布的拟合程度来判断候选外键关系成为真正外键关系的可能性。为了更准确地根据拟合度找出外键关系，将分布图分区，为解决大型网络表格中分区不断增加导致时间复杂度增加的问题，提出基于多次划分的分区算法减少计算量，提高了算法的运行效率，使得算法可以扩展到大型网络表格上。

[0103] 本领域普通技术人员可以理解：附图只是一个实施例的示意图，附图中的模块或流程并不一定是实施本发明所必须的。

[0104] 本说明书中的各个实施例均采用递进的方式描述，各个实施例之间相同相似的部分互相参见即可，每个实施例重点说明的都是与其他实施例的不同之处。尤其，对于装置或系统实施例而言，由于其基本相似于方法实施例，所以描述得比较简单，相关之处参见方法实施例的部分说明即可。以上所描述的装置及系统实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本实施例方案的目的。本领域普通技术人员在不付出创造性劳动的情况下，即可以理解并实施。

[0105] 本领域普通技术人员可以理解：实施例中的装置中的部件可以按照实施例描述分布于实施例的装置中，也可以进行相应变化位于不同于本实施例的一个或多个装置中。上述实施例的部件可以合并为一个部件，也可以进一步拆分成多个子部件。

[0106] 以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求的保护范围为准。