CN104199924B

CN104199924B - 选择具有快照关系的网络表格的方法及装置

Info

Publication number: CN104199924B
Application number: CN201410441120.5A
Authority: CN
Inventors: 王宁; 任红伟
Original assignee: Yangtze River Delta Research Institute Of Beijing Jiaotong University
Current assignee: Yangtze River Delta Research Institute Of Beijing Jiaotong University
Priority date: 2014-09-01
Filing date: 2014-09-01
Publication date: 2018-05-11
Anticipated expiration: 2034-09-01
Also published as: CN104199924A

Abstract

本发明公开了一种选择具有快照关系的网络表格的方法及装置，该方法包括：将网络表格的集合按照网络表格的实体列的内容的领域进行分类，其中，实体列为能够标识网络表格的记录的属性列；在分类后的网络表格集合中，根据预设规则，选择与第一表格对应的多个第二表格，其中，多个第二表格是与第一表格具有快照关系的网络表格。通过本发明，选择与第一表格具有快照关系的多个第二表格，第二表格可用于优化查询以提高查询的效率，也可以用于大数据环境，使得系统能够实时地返回部分查询结果。

Description

选择具有快照关系的网络表格的方法及装置

技术领域

本发明涉及数据处理领域，具体而言，涉及一种选择具有快照关系的网络表格的方法及装置。

背景技术

随着信息技术的发展，互联网上的资源越来越丰富，除了非结构化数据外，还有大量的网络表存在，这些网络表覆盖面广且信息量大，因此受到人们的关注。Google公司启动了WebTables项目，研究如何更好地抽取和利用网络上广泛存在的结构化数据；最近推出的Fusion Tables旨在帮助人们在云环境下进行数据集成和合作，用户可以上传表格状的数据并与其他用户分享，通过合作的方式利用众人的智慧解决数据合并过程中可能引起的冲突。为了让机器更容易地处理来自网络的表格数据，Microsoft公司利用知识库对网络表进行语义恢复，恢复其表头，并实现实体列的探测以及典型属性的提取。

实践中，网络数据的价值不仅在于数据本身，还在于数据之间的关系。只有探测出数据间潜在的关系，方能更好地利用这些数据。Xin Luna Dong尝试发现网络数据间的复制关系，以便找到数据的真正来源，从而检测数据的真假。Anish Das Sarma等人发现表格之间的合并和连接关系，合并关系可以实现实体级的补充，而连接关系可以实现实体属性级的补充，这两种关联关系的发现不仅有助于表格内容的扩展，也给搜索带来了很大的帮助。以合并关系为例，如果一个体育爱好者想在已知表A中查找运动员“Rafael Nadal”的记录，在该表没有这条记录的情况下，查询会失效。但是，如果我们事先已经发现另一张表与A表是合并关系，那么查询就可以转移到这张与A表具有合并关系的表上，从而增加了找到“Rafael Nadal”的概率。除了复制、合并以及连接关系外，网络表格之间还可以存在其它可以利用的关系。

关系表之间的快照关系可以被用于优化查询。随着互联网数据抽取技术的发展，来自网络的结构化数据日益增多，它们可以和本地数据一起用于查询和分析。设想用户需要经常在一张规模较大的网络表T₁中查找满足某个条件的元组信息，如果这部分元组恰好存在于另一张规模小很多的网络表T₂中，将用户的查询转移到T₂上进行，显然会大幅提高查询的效率。快照关系除了用于优化查询外，还有利于在大数据环境下实时地返回部分查询结果。大数据环境下，实时性和查询的精确性是需要权衡的，有时并不需要一次返回所有结果，快速返回部分结果也是有益的，而利用快照关系就可以较快地将一部分查询结果返回给用户。假设给定某种匹配条件，网络表T₁中匹配该条件的元组存在于网络表T₂中，T₂就被称为T₁匹配该条件的快照，发现网络表之间的快照关系具有重要的意义。

目前，数据管理系统需要融合来自不同源的数据，但不同源提供的数据往往会发生冲突，导致数据真假难辨。为了给用户提供更加可靠、可信的数据，Xin Luna Dong等人尝试检测数据间存在的复制关系，意在发现数据的本源，最终在冲突的数据中找出真值。为了探测出数据间的复制关系，XinLuna Dong使用Bayes模型计算数据源之间的依赖程度。算法基于如下的基本思想：如果两个数据源提供的值都是真值，并不能说明两个数据源之间具有依赖关系；相反，在两个数据源提供的值都不正确，但值是相同的情况下，这两个数据源之间存在依赖关系的概率较大。于是，在已知两个数据源提供的值同为真、同为假但值相同、提供的值不同的情况下，分别考虑它们是独立的和依赖的两种情况，建立Bayes模型，最后得到两个数据源存在依赖关系(即复制关系)的概率。Xin Luna Dong提出检测数据间存在的复制关系，目的在于探测数据的真假性，以便有效地解决多源数据间的冲突问题。虽然，复制关系的发现也需要检测数据的相似性，但它处理的数据是以记录为单位，而网络表格间的快照关系，处理的数据是以表格为单位。网络表格并不规范，往往没有完整的模式，表中的数据还会存在噪音，即便同一实体，其表现形式也有差异，需要根据匹配条件综合考虑模式和实体的一致性。

综上所述，由于网络数据的异构性和不确定性，选择具有快照关系的网络表格需要解决的技术问题如下：

(1)网络表格并不规范，往往没有完整的模式，表中的数据还会存在噪音，即便同一实体，其表现形式也有差异；

(2)对于来自不同数据源的网络表格而言，很难找到能准确匹配的快照。只能根据匹配程度评分，返回评分较高的快照。

针对相关技术中选择具有快照关系的网络表格的方法存在的上述问题，目前尚未提出有效的解决方案。

发明内容

针对相关技术中选择具有快照关系的网络表格的方法存在的上述问题，本发明提供了一种选择具有快照关系的网络表格的方法及装置，以至少解决该问题。

一方面，提供了一种选择具有快照关系的网络表格的方法，包括：将网络表格的集合按照所述网络表格的实体列的内容的领域进行分类，其中，所述实体列为能够标识所述网络表格的记录的属性列；在所述分类后的所述网络表格集合中，根据预设规则，选择与第一表格对应的多个第二表格，其中，所述多个第二表格是与所述第一表格具有快照关系的网络表格。

优选地，在所述分类后的所述网络表格集合中，根据预设规则，选择与第一表格对应的多个第二表格包括：

分别确定所述网络表格集合中的每个表格在实体因素方面的如下参数：实体的覆盖率E_base|σ(T₁,T₂)、调节因素E_adjustment(T₁,T₂)和实体的新鲜度Fr^u(T₂)；

分别确定所述每个表格的实体因素

分别确定所述第一表格和每个表格的属性重合度S_attr(T₁,T₂)；

分别确定S_Entity(T₁,T₂)和S_attr(T₁,T₂)的运算的结果；

根据所述结果，选择满足第一预设条件的预设数目个表格作为所述第二表格；

其中，T₁表示第一表格，T₂表示第二表格。

分别确定所述每个表格的实体因素

分别确定S_Entity(T₁,T₂)和S_attr(T₁,T₂)的运算的结果；

根据Bayes模型算法，分别确定所述多个第二表格在内容方面的得分；

分别确定所述得分、S_Entity(T₁,T₂)和S_attr(T₁,T₂)的运算的结果；

根据所述运算结果，选择满足第二预设条件的预设数目个表格作为所述第二表格。

优选地，通过如下方式之一确定内容方面的得分：

其中，和均表示所述内容方面的得分，A(T₁)是第一表格T₁的属性，A(T₂)是第二表格T₂的属性，a是T₁和T₂的共有属性。

优选地，通过如下方式确定

通过如下方式确定

其中e_i为第一表格T₁上满足选择条件σ的实体，count(e_i)为在初筛选阶段处理的表集Γ'中，e_i在每个表中出现次数的和，的取值为0或1；若T₂表中有e_i，则表示T₁表中满足条件σ的实体集合。

优选地，

其中为兴趣列a_k在Poi中的权重，exist(a_k∈A(T₂))的取值为0或1，若T₂表的属性中有a_k，则exist(a_k∈A(T₂))＝1；反之为0。

另一方面，还提供了一种选择具有快照关系的网络表格的装置，包括：分类模块，用于将网络表格的集合按照所述网络表格的实体列的内容的领域进行分类，其中，所述实体列为能够标识所述网络表格的记录的属性列；第一选择模块，用于在所述分类后的所述网络表格集合中，根据预设规则，选择与第一表格对应的多个第二表格，其中，所述多个第二表格是与所述第一表格具有快照关系的网络表格。

优选地，所述第一选择模块包括：

第一确定单元，用于确定所述网络表格集合中的每个表格在实体因素方面的如下参数：实体的覆盖率E_base|σ(T₁,T₂)、调节因素E_adjustment(T₁,T₂)和实体的新鲜度Fr^u(T₂)；

第二确定单元，用于分别确定所述每个表格的实体因素

第三确定单元，用于分别确定所述第一表格和每个表格的属性重合度S_attr(T₁,T₂)；

第四确定单元，用于分别确定S_Entity(T₁,T₂)和S_attr(T₁,T₂)的运算的结果；

选择单元，用于根据所述结果，选择满足第一预设条件的预设数目个表格作为所述第二表格；

其中，T₁表示第一表格，T₂表示第二表格。

优选地，所述第一选择模块包括：

第五确定单元，用于确定所述网络表格集合中的每个表格在实体因素方面的如下参数：实体的覆盖率E_base|σ(T₁,T₂)、调节因素E_adjustment(T₁,T₂)和实体的新鲜度Fr^u(T₂)；

第六确定单元，用于分别确定所述每个表格的实体因素

第七确定单元，用于分别确定所述第一表格和每个表格的属性重合度S_attr(T₁,T₂)；

第八确定单元，用于根据Bayes模型算法，分别确定所述多个第二表格在内容方面的得分；

第九确定单元，用于分别确定所述得分、S_Entity(T₁,T₂)和S_attr(T₁,T₂)的运算的结果；

第二选择模块，用于根据所述运算结果，选择满足第二预设条件的预设数目个表格作为所述第二表格。

优选地，通过如下方式之一确定内容方面的得分：

其中，和均表示所述内容方面的得分，A(T₁)是第一表格T₁的属性，A(T₂)是第二表格T₂的属性，a是T₁和T₂的共有属性，并且，

通过如下方式确定

其中e_i为第一表格T₁上满足选择条件σ的实体，count(e_i)为在初筛选阶段处理的表集Γ'中，e_i在每个表中出现次数的和，的取值为0或1；若T₂表中有e_i，则

其中为兴趣列a_k在Poi中的权重，exist(a_k∈A(T₂))的取值为0或1。若T₂表的属性中有a_k，则exist(a_k∈A(T₂))＝1；反之为0，表示T₁表中满足条件σ的实体集合。

通过本发明，采用根据预设匹配关系，选择与第一表格具有快照关系的多个第二表格，第二表格可用于优化查询以及在大数据环境下实时地返回部分查询结果。

附图说明

此处所说明的附图用来提供对本发明的进一步理解，构成本申请的一部分，本发明的示意性实施例及其说明用于解释本发明，并不构成对本发明的不当限定。在附图中：

图1是根据本发明实施例的选择具有快照关系的网络表格的方法的流程图；

图2是根据本发明实施例的网络表格间的快照关系发现的示意图；

图3是根据本发明实施例的预处理的流程图；

图4是根据本发明实施例的基于实体和属性重合度的初筛选流程图；

图5是根据本发明实施例的结合内容的增强算法发现快照表的流程图；

图6是根据本发明实施例的选择具有快照关系的网络表格的装置的结构框图。

具体实施方式

下文中将参考附图并结合实施例来详细说明本发明。需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。

图1是根据本发明实施例的选择具有快照关系的网络表格的方法的流程图，如图1所述，该方法包括如下的步骤：

步骤S102，将网络表格的集合按照所述网络表格的实体列的内容的领域进行分类，其中，实体列为能够标识网络表格的记录的属性列。

步骤S104，在分类后的网络表格集合中，根据预设规则，选择与第一表格对应的多个第二表格，其中，多个第二表格是与第一表格具有快照关系的网络表格。

优选地，在步骤S102中，根据实际需要，可以使用Freebase进行操作，也可以使用其他知识库来进行处理，在此不作限定。

在实施时，可以采用多种实施方式在分类后的网络表格集合中，根据预设规则，选择与第一表格对应的多个第二表格。下面描述其中的两种实施方式。

方式一：分别确定所述网络表格集合中的每个表格在实体因素方面的如下参数：实体的覆盖率E_base|σ(T₁,T₂)、调节因素E_adjustment(T₁,T₂)和实体的新鲜度Fr^u(T₂)；

分别确定所述每个表格的实体因素

分别确定S_Entity(T₁,T₂)和S_attr(T₁,T₂)的运算的结果；

根据所述结果，选择满足第一预设条件的预设数目个表格作为所述第二表格。

需要说明的是，该方式一中第一预设条件可以根据实际需要进行设置，例如：可以为该结果在一定的数值范围内，例如，该结果大于0.1；同样的，预设数目也可以根据实际需要进行设置，例如十个或二十个。

方式二：

分别确定网络表格集合中的每个表格在实体因素方面的如下参数：实体的覆盖率E_base|σ(T₁,T₂)、调节因素E_adjustment(T₁,T₂)和实体的新鲜度Fr^u(T₂)；

分别确定每个表格的实体因素

分别确定第一表格和每个表格的属性重合度S_attr(T₁,T₂)；

分别确定S_Entity(T₁,T₂)和S_attr(T₁,T₂)的运算的结果；

根据Bayes模型算法计算所述第二表格在内容方面的得分；

分别确定得分、S_Entity(T₁,T₂)和S_attr(T₁,T₂)的运算的结果；

根据运算结果，从第二表格中，选择满足第二预设条件的预设数目个表格作为与第一表格具有网络表格间快照关系的表格。

需要说明的是，该方式二中第一预设条件可以根据实际需要进行设置，例如：可以为该结果在一定的数值范围内，例如，该结果大于0.1；同样的，预设数目也可以根据实际需要进行设置，例如十个或二十个。

需要说明的是，上述方式一和方式二中的运算可以为相关技术中的多种运算法则。例如：加法、乘法、幂，比较优的，可以采用乘法。

优选地，通过如下方式确定通过如下方式确定通过如下方式确定以及，

其中e_i为第一表格T₁上满足选择条件的实体，count(e_i)为在初筛选阶段处理的表集Γ'中，e_i在每个表中出现次数的和，的取值为0或1。若T₂表中有e_i，则表示T₁表中满足条件σ的实体集合。

优选地，

其中为兴趣列a_k在Poi中的权重，exist(a_k∈A(T₂))的取值为0或1。若T₂表的属性中有a_k，则exist(a_k∈A(T₂))＝1；反之为0。

下面将结合优选实施例进行说明，以下优选实施例结合了上述实施例及优选实施方式。

本优选实施例提供了一种选择具有快照关系的网络表格的方法，下面通过具体实施方式进行说明。

首先说明优选实施例中的网络表格及其快照关系：

在本实施例中，关于实体列：对于一张网络表格T，其中的每条记录均代表一个实体，如果T中某个属性列能够标识相应的实体，该属性列被称为网络表格T的实体列，可以记作EC(T)。

在本实施例中，关于兴趣列和匹配关系：对于表T上的操作序列σ为选择条件，F_i(x)是一个逻辑表达式，选择使逻辑表达式为真的实体；π为投影操作，Poi为一组属性，π(Poi)投影表中各实体在Poi中对应的值。T经过操作序列R可以得到另外一张表，我们定义Poi为兴趣列，R为匹配关系。为简单起见，匹配关系记作

在本实施例中，对于网络表T₁和T₂，以及匹配关系如果满足以下三个条件：

1)EC(T₂)＝EC(T₁)；

2)其中表示T_k表中实体的集合；

3)其中A(T₂)为T₂表属性列的集合，

则称T₂是T₁上满足匹配关系R的快照表，T₂与T₁的关系为快照关系。

下面具体说明本优选实施例方法的总体框架。

与关系数据库中的表格不同，网络表格来自不同的数据源，不一定有完整的模式信息。对于没有模式信息的网络表格，可以利用知识库恢复其语义信息，以下的实施方式均假设每张网络表格都经过语义恢复获得了相应的模式信息。

选择具有快照关系的网络表格可以包括如下三个步骤：

步骤(1)预处理过程使用Freebase对表格数据集进行按域分类。

需要说明的是，在该步骤中，可以按照实体列的内容的领域进行分类，由于网络表格内容比较庞大，通过分类，可以降低计算规模。

另外，Freebase只是一种优选的实施方式，在实施中，可以根据实际需要，选择不同的工具进行实施。

(2)基于实体和属性重合度选择出与给定表结构(相当于上述实施例中的第一表格)相似的表(相当于上述实施例中的第二表格)。

(3)基于表格内容的增强算法根据属性列内容建立Bayes模型。

通过步骤(3)，可以提高快照关系发现的准确率。

如图2所示，图2给出发现网络表格间快照关系的框架，该框架给出选择具有快照关系的网络表格方法的示意图，如图2所示，利用AcsDB库，生成候选兴趣列，根据选择条件和兴趣列，得到匹配关系R；将网络表格的集合使用Freebase库进行预处理，得到按照域分类的表集，然后进行初筛选，得到结构相似的表；根据内容增强步骤，得到在T上满足R的快照表。需要说明的是，图2中示出的Freebase库、AcsDB库仅用作示例说明，在实际实施中也可以采用相关技术中的其他数据库，此处的描述并不用于对本申请技术方案的限制。

需要说明的是，在实施时，可以只执行步骤(1)和步骤(2)，也可以执行步骤(1)、步骤(2)和步骤(3)。

下面对本优选实施例中的预处理步骤进行详细描述。

此阶段的主要任务是将网络表格的集合用Freebase按表的域进行分类，以降低快照关系发现的计算复杂度。

来自不同数据源的网络表格涉及内容广泛，快照关系只会存在于描述实体的领域一致的网络表格之间。为了提高快照关系的发现效率，减少后续计算复杂度，首先对网络表格的集合进行预处理，根据表格实体列的内容判断其所在的领域，然后按领域进行分类。

优选地，可以使用Freebase知识库判断实体所在的领域。Freebase用来判断实体在现实世界中所属的类别和其拥有的特性。使用Freebase搜索一个给定实体，会返回该实体一系列的归类，表格的域可以由表格内实体所在的域决定。

根据Freebase返回的结果，为每个实体设立一个域的集合表格中实体集E的候选域集为D(E)，则表的域d满足两个条件：

1)d∈D(E)

2)其中count(d)为d在所有D(e_i)中出现的次数。

预处理阶段的程序流程如图3所示，可以包括如下步骤：

步骤S301，输入为网络表格的集合。

步骤S302，将集合中表的路径存入orgList中。

步骤S303，按Freebase的分类创建域的文件夹，用来存放按域分类的表格。

步骤S304至步骤S308，读取表格中的实体列内容，经过Freebase分析后，返回表格的域，然后将表格转储到相应的文件夹内。

经过预处理，网络表格会按表格的域进行分类，同一个文件夹内表格的域相同。判断出给定表的域后，就可以从对应的文件夹中取出规模较小的表格的集合作为后续操作的数据集，从而降低了计算量。

在本优选实施例中，需要基于实体和属性重合度的初筛选，下面对基于实体和属性重合度的初筛选的步骤进行详细描述。

该阶段的主要任务是根据匹配关系R，从表集中选择与给定表T₁(上述实施例中的第一表格)结构相似的表。匹配关系R由选择条件和兴趣列两部分组成，结构相似指属性尽可能地包含匹配关系中的兴趣列，且描述的实体尽可能地包含给定表上满足匹配关系中选择条件的实体。

优选地，关于实体因素：

若T₂是给定表T₁上满足匹配关系R的快照，那么T₂中的实体应该尽可能多地包含T₁上满足R中σ条件的实体。由于网络表格的不确定性，不能用严格的规则来限定它们。事实上，T₂中也极有可能含有T₁表中不存在的实体，我们需要一个调节因素来衡量这些独有实体对T₂是T₁快照的可能性的影响。此外，还有一个不容忽视的因素——实体新鲜度。如果两张网络表格A和B都是T₁的快照，它们对于T₁的实体覆盖率相等，不同之处在于，A中描述的实体在其它表中普遍存在，而B中描述的实体在表集中很少出现，那么我们就认为表B的实体新鲜度高于A。换句话说，B就相当于新闻报道中的独家新闻，B中的实体不普遍存在却应该得到重视。所以，有必要赋予这样的表B一个较高的实体因素的得分。

综合上述的分析，T₂表在实体因素方面的得分需要考虑实体的覆盖率E_base|σ(T₁,T₂)、调节因素E_adjustment(T₁,T₂)和表中实体的新鲜度Fr^u(T₂)这三个因素。

优选地，各因素的计算方法可以采用(1)～(3)所示出的公式进行处理。

其中表示T₁表中满足条件σ的实体集合，表示T₂的实体集合。

其中e_i为给定表T₁上满足选择条件的实体，count(e_i)为在初筛选阶段处理的表集Γ'中，e_i在每个表中出现次数的和。的取值为0或1。若T₂表中有e_i，则反之为0。公式(3)可以归一化为公式(4)。

最后，结合实体覆盖率、调节因素和表中实体的新鲜度，T₂表在实体因素方面的最终得分记为S_Entity。为方便表示，我们将E_base|σ(T₁,T₂)简记为E_base，将E_adjustment(T₁,T₂)简记为E_adjustment。于是，得到评分公式(5)。

其中μ为参数，用来控制函数在E_base和E_adjustment两个指标下取得最大值的情况：

若E_adjustment≠0，则当μ＝ε(ε为实数，实验控制取值，默认为0)时，S_Entity(T₁,T₂)取最大值；

若E_adjustment＝0，则当μ＝-1时，S_Entity(T₁,T₂)取最大值。

优选地，关于兴趣列的生成与使用：

快照表的发现基于匹配关系R，而R中需要指定经常查询的列。采用Google公司发布的AcsDB模式数据库为用户推荐表中经常查询的列，称为兴趣列Poi。选择模式中经常与实体列一起出现的属性作为兴趣列。系统按经常出现的概率由高到低推荐兴趣列，用户选择其中的一部分属性作为希望生成快照的兴趣列，确定兴趣列后系统为其自动生成权重。因为实体列相同的表才有可能是快照关系，所以默认实体列为兴趣列中的一项。

假设给定表T₁中的实体列为a_e，则表T₁的模式中属性a出现的条件概率P(a|a_e)按公式(6)得到。

得到表中每个属性的概率值后，若用户从推荐的兴趣列中指定了n个属性(包含实体列)作为最后的兴趣列Poi＝{a₁,…,a_n}，其中a₁＝a_e，则T₂表在属性重合度方面的得分S_attr(T₁,T₂)按公式(7)计算。

优选地，关于初筛选的评分：

在初筛选阶段主要考虑实体和属性重合度两方面的因素，这一部分的最终得分见公式(8)。实体和属性这两个因素相当于表格的结构，经过这一步的判断，我们可以筛选出与给定表T₁在结构上有较高相似度的表。

S_frame(T₁,T₂)＝S_Entity(T₁,T₂)×S_attr(T₁,T₂) (8)

图4是初筛选阶段的流程图，输入数据有匹配关系R、给定表T₁、处理表集的路径，输出是各表在此阶段的得分。仅当所有表都处理结束后才能计算出各表的实体新鲜度，所以程序设有两层循环。第一层：计算各表与给定表的实体覆盖率和调节因素，这两个值与其它表的内容无关，可以先计算出来。同时，在第一层需要对表中实体进行统计，以方便第二层计算表的实体新鲜度。第二层：根据第一层实体统计的结果，计算出各表的实体新鲜度，并结合第一层的实体覆盖率和调节因素计算出各表在初筛选阶段的得分。最后，将结果写入存储文件frame.txt中，作为下一阶段评分程序的输入。包括如下步骤：

步骤S401，计算给定表满足条件的实体以及表的属性集合A(T₁)。

步骤S402，初始化统计满足选择条件的实体出现次数的count数组。

步骤S403，得到T₂表的E_T2和其上属性的集合A(T₂)，填写count数组。

步骤S404，分别得到实体覆盖率和调节因素。

步骤S405，根据R中的Poi和A(T₂)计算表在属性上的得分。

步骤S406，根据调节因素得到μ的值。

步骤S407，统计count二维数组中每个实体的出现次数。

步骤S408，根据表T₂的实体及count数组计算得到实体新鲜度得分。

步骤S409，根据已经得到的实体覆盖率、调节因素、实体新鲜度得分以及μ，计算表T₂在实体方面的得分。

步骤S410，计算表T₂在初筛选阶段的得分。

优选地，关于基于表格内容的增强算法：

即使两张表有同样的实体和同样的属性，同一实体对应属性上的值也可能不同，如果值不同的属性又恰是指定的兴趣列，两表就不是快照关系。这一阶段采用Bayes模型探测表格在共同属性上内容的一致性，从而更加准确地发现网络表格间的快照关系。

优选地，可以使用Bayes分析方法来计算T₁表和T₂表是快照关系的概率。

需要说明的是，若T₂(相当于上述实施例中的第二表格)和T₁(相当于上述实施例中的第一表格)只是结构相同，描述的实体相同，属性下的值都是独立给出的，并没有相互复制，那么可以称T₂独立于T₁。如果T₂和T₁是相互独立的，同一实体在某个属性上的值可能相同也可能不同。同样，如果T₂是T₁的快照，来自不同数据源的表格在同一实体上的值相同的概率应大于不同的概率。为了建立Bayes模型，需要这样几个参数：n(n>1)，指一个实体在某个属性上可能给出值的个数；r(0<r≤1)，当T₂是T₁的快照时，T₂表给出的值与T₁相同的概率。

对表格中的两个集合和感兴趣：表示T₂表在某个属性上给出与T₁相同值的实体集合，k_s为该集合的大小；表示在该属性上给出不同值的实体集合，k_d为相应集合的大小。

首先考虑T₁和T₂是独立的，记为T₂⊥T₁。因为一个实体在某个属性上的值有n种可能解，两张表各自给出某一个值的概率为1/n。所以，对两张表来说，同一个实体在某个属性(若为a)上给出相同值的概率为:

同理，给出不同值的概率为:

将公式(9)和公式(10)扩展到该属性的所有实体上，则在属性a上的条件概率为:

为了后续表示方便，我们将简记为Ψ，则公式(11)简化为:

接下来，我们用同样的方法考虑T₁和T₂是快照关系的情况。若T₂是T₁的快照，记为T₂→T₁。T₂中属性的值应该与T₁中对应属性的值相同。但是对网络表格而言，也存在另一种情况，T₂是T₁的快照表，但是T₂中的某些值被更改了，导致两张表的值不一致。所以，引入概率r表示快照中的值为原值的概率。

同理可得公式(13)～(15)：

最终，可以根据Bayes模型得到T₂→T₁的条件概率见公式(16)。

这里θ＝P(T₂→T₁)，此参数为预先设定的概率值，而参数n和r满足

对表集中的一张表来说，公式(16)有这样的特性：

1)即k_s+k_d的和不变；

2)将代入P_a(T₂→T₁|Ψ)，最终P_a(T₂→T₁|Ψ)为关于参数k_s的递增函数，所以，k_s增加，表T₂是T₁上快照的概率值随之增加。

最终，记两张表在内容上的得分为S_content(T₁,T₂)，这里给出三种计算方法:

A(T₁)是表T₁的属性，A(T₂)是表T₂的属性，a是表T₁和T₂的共有属性。

这三种方法都对两张表中的共有属性逐一进行判断，虽然计算精度高，但存在共同的缺点：对某些属性进行了不必要的判断导致耗时严重。在某类实体中具有明显代表性的属性，称为代表属性，判断它们的值的一致性意义较大。所以，再次利用AcsDB来获得最有判断意义的属性。

给定一张表中属性的集合A(T)，|A(T)|≥1，AcsDB库返回该集合共同出现的频率freq(A(T))。我们可以利用AcsDB找到实体所在模式的代表属性，一般情况下，代表属性上的值最有可能出现不一致，而直接对这样的属性进行判断，会提高快照关系发现的效率。因此，我们用公式(20)发现表格T中的代表属性:

其中a_e为模式中实体列的列头，所以S_content(T₁,T₂)为:

优选地，关于结合实体内容的评分：

经过前面的讨论，要想确定T₂是T₁的快照，需要保证T₂在描述的实体和其属性上保持一致，且内容上要尽可能一致。得到S_frame(T₁,T₂)以及P(T₂→T₁|Ψ)，将P(T₂→T₁|Ψ)简记为S_content(T₁,T₂)，用公式(22)结合这两个得分。得分越高说明是给定表T₁满足匹配关系R上快照的概率越大。

S_snapshot(T₁,T₂)＝S_frame(T₁,T₂)×S_content(T₁,T₂) (22)

最后，图5给出结合内容增强算法发现快照表的流程。该过程的输入为初筛选过程的输出文件frame.txt和给定表T₁，输出为给定表T₁上满足匹配关系R的top-k张快照表。此过程主要为一层循环操作，使用基于表格内容的增强算法得到每张表的S_content，再结合初筛选得到的S_frame，最后按公式(22)得到表是给定表上满足匹配关系R的快照表的得分S_snapshot。可以按照S_snapshot由高到低对表排序，将top-k张表存储在snapshot.txt中。

具体地，包括如下步骤：

步骤S501，得到表中属性的集合A(T₁)，并得到各属性列对应的<entity,value>。

步骤S502，用AcsDB发现T₁表中候选的代表属性集合，并按频率由高到低排序。

步骤S503，根据候选代表属性得到T₂表的代表属性。

步骤S504，取出代表属性列对应的<entity,value>，并与T₁表中对应列的值进行比较，得到k_s和k_d。其中，k_s表示T₂表与T₁表在代表属性上具有相同值的个数；k_d表示T₂表与T₁表在代表属性上具有不同值的个数。

在本步骤中，候选代表属性是针对给定表T₁而言的，也就是T₁表属性根据在AcsDB中出现的频率排序，若一个候选代表属性首次出现在T₂表中，那么这个首次出现的属性就是T₂表的代表属性。

例如：

假设T₁表的属性有：player,country,points,movement.

T₂表的属性有:

player,sex,points,rank.

除去实体列和与实体列共同出现次数为0的属性，并将剩余属性按出现次数由高到低排序，候选代表属性为：points,country

其中points首次出现在T₂表中，所以T₂表的代表属性为points.

步骤S505，用Bayes模型计算得到表在代表属性上的得分。

步骤S506，结合表T₂初筛选的得分，计算得分是给定表上满足指定匹配关系的快照表的得分。

需要说明的是，在附图的流程图示出的步骤可以在诸如一组计算机可执行指令的计算机系统中执行，并且，虽然在流程图中示出了逻辑顺序，但是在某些情况下，可以以不同于此处的顺序执行所示出或描述的步骤。

在另外一个实施例中，还提供了一种选择具有快照关系的网络表格的软件，该软件用于执行上述实施例及优选实施例中描述的技术方案。

在另外一个实施例中，还提供了一种存储介质，该存储介质中存储有上述选择具有快照关系的网络表格的方法的流程图；该存储介质包括但不限于：光盘、软盘、硬盘、可擦写存储器等。

本发明实施例还提供了一种选择具有快照关系的网络表格的装置，该选择具有快照关系的网络表格的装置可以用于实现上述选择具有快照关系的网络表格的方法及优选实施方式，已经进行过说明的，不再赘述，下面对该选择具有快照关系的网络表格的装置中涉及到的模块进行说明。如以下所使用的，术语“模块”是可以实现预定功能的软件和/或硬件的组合。尽管以下实施例所描述的系统和方法以软件来实现较佳，但是硬件，或者软件和硬件的组合的实现也是可能并被构想的。

图6是根据本发明实施例的选择具有快照关系的网络表格的装置的结构框图，如图6所示，该装置包括：分类模块62，第一选择模块64，下面对上述结构进行详细说明。

分类模块62，用于将网络表格的集合按照所述网络表格的实体列的内容的领域进行分类，其中，所述实体列为能标识所述网络表格的记录的属性列；第一选择模块66，用于在所述分类后的网络表格集合中，根据预设规则，选择与第一表格对应的第二表格，其中，所述第二表格与所述第一表格具有网络表格间快照关系。

优选地，第一选择模块包括：第一确定单元，用于确定所述网络表格集合中的每个表格在实体因素方面的如下参数：实体的覆盖率E_base|σ(T₁,T₂)、调节因素E_adjustment(T₁,T₂)和实体的新鲜度Fr^u(T₂)；

第二确定单元，用于分别确定所述每个表格的实体因素

其中，T₁表示第一表格，T₂表示第二表格。

需要说明的是，该方式中第一预设条件可以根据实际需要进行设置，例如：可以为该结果在一定的数值范围内，例如，该结果大于0.1；同样的，预设数目也可以根据实际需要进行设置，例如十个或二十个。

优选地，第一选择模块包括：

第六确定单元，用于分别确定所述每个表格的实体因素

优选地，通过如下方式之一确定内容方面的得分：

其中，和均表示所述内容方面的得分。A(T₁)是第一表格T₁的属性，A(T₂)是第二表格T₂的属性，a是T₁和T₂的共有属性。

优选地，

通过如下方式确定

其中e_i为第一表格T₁上满足选择条件σ的实体，count(e_i)为在初筛选阶段处理的表集Γ'中，e_i在每个表中出现次数的和，的取值为0或1；若T₂表中有e_i，则表示T1表中满足条件σ的实体集合。

优选地，

需要说明的是，上述方式中的运算可以为相关技术中的多种运算法则。例如：加法、乘法、幂，比较优的，可以采用乘法。

通过上述实施例，提供了一种选择具有快照关系的网络表格的方法及装置，对于来自不同数据源的网络表格而言，很难找到能准确匹配的快照关系。发现给定网络表上满足某种匹配关系的快照，并给出评分的考虑因素及具体的方法。快照表一方面可以用来优化表格上的查询，如果存在表T在匹配关系R下的较小规模的快照表，那么当用户的查询列和条件与匹配关系R相当时，就可以将查询转移到快照表上，从而降低查询时间。另一方面，在大数据环境下，为实时地返回查询结果，有时并不需要一次返回所有结果，部分结果也是有意义的。

需要说明的是，传统的关系数据库中某张表的快照是通过查询生成的，快照中的数据与查询是准确匹配的。但是本申请中的选择具有快照关系的网络表格与传统的方式不同，是通过判断预设的规则，在多个表格中选择到评分较高的若干网络表格。

本发明实现了如下技术效果：

1)首次提出发现网络表格间的快照关系，并设计评分的理论模型及算法，该算法权衡表中实体和属性重合度因素，能够发现较高质量的快照表；

2)网络表格间的快照关系发现中引入实体新鲜度的概念，并给出表中实体新鲜度的计算方法，在同样的匹配条件下，算法会更多地关注能提供新鲜实体的表；

3)设计基于Bayes模型的表格内容增强算法，能更加准确地判断属性列上值的一致性，从而提高快照关系发现的准确率。

4)在基于Bayes模型的表格内容增强算法中，选择某类实体中具有明显代表性的属性，并直接对这样的属性进行判断，提高了快照关系发现的效率。

需要说明的是，这些技术效果并不是上述所有的实施方式所具有的，有些技术效果是某些优选实施方式才能取得的。

显然，本领域的技术人员应该明白，上述的本发明的各模块或各步骤可以用通用的计算装置来实现，它们可以集中在单个的计算装置上，或者分布在多个计算装置所组成的网络上，可选地，它们可以用计算装置可执行的程序代码来实现，从而可以将它们存储在存储装置中由计算装置来执行，或者将它们分别制作成各个集成电路模块，或者将它们中的多个模块或步骤制作成单个集成电路模块来实现。这样，本发明不限制于任何特定的硬件和软件结合。

以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims

1.一种选择具有快照关系的网络表格的方法，网络表格间的快照关系，处理的数据是以表格为单位，其特征在于，包括：

将网络表格的集合按照所述网络表格的实体列的内容的领域进行分类，其中，所述实体列为能够标识所述网络表格的记录的属性列；

在所述分类后的所述网络表格集合中，根据预设规则，选择与第一表格对应的多个第二表格，其中，所述多个第二表格是与所述第一表格具有快照关系的网络表格；

在所述分类后的所述网络表格集合中，根据预设规则，选择与第一表格对应的多个第二表格包括：

分别确定所述每个表格的实体因素

<mrow> <msub> <mi>S</mi> <mrow> <mi>E</mi> <mi>n</mi> <mi>t</mi> <mi>i</mi> <mi>t</mi> <mi>y</mi> </mrow> </msub> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>)</mo> </mrow> <mo>=</mo> <msup> <mi>Fr</mi> <mi>u</mi> </msup> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>)</mo> </mrow> <mo>*</mo> <mi>exp</mi> <mrow> <mo>(</mo> <mo>-</mo> <mfrac> <msup> <mrow> <mo>(</mo> <msub> <mi>E</mi> <mrow> <mi>b</mi> <mi>a</mi> <mi>s</mi> <mi>e</mi> <mo>|</mo> <mi>&sigma;</mi> </mrow> </msub> <mo>(</mo> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>)</mo> <mo>-</mo> <msub> <mi>E</mi> <mrow> <mi>a</mi> <mi>d</mi> <mi>j</mi> <mi>u</mi> <mi>s</mi> <mi>t</mi> <mi>m</mi> <mi>e</mi> <mi>n</mi> <mi>t</mi> </mrow> </msub> <mo>(</mo> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>)</mo> <mo>+</mo> <mi>&mu;</mi> <mo>)</mo> </mrow> <mn>2</mn> </msup> <mn>2</mn> </mfrac> <mo>)</mo> </mrow> <mo>;</mo> </mrow>

分别确定S_Entity(T₁,T₂)和S_attr(T₁,T₂)的运算的结果；

其中，T₁表示第一表格，T₂表示第二表格；

通过如下方式确定

<mrow> <msup> <mi>Fr</mi> <mi>u</mi> </msup> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>)</mo> </mrow> <mo>=</mo> <mfrac> <mrow> <mi>F</mi> <mi>r</mi> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>)</mo> </mrow> </mrow> <mrow> <munder> <mi>max</mi> <mrow> <msub> <mi>T</mi> <mi>k</mi> </msub> <mo>&Element;</mo> <msup> <mi>&Gamma;</mi> <mo>&prime;</mo> </msup> </mrow> </munder> <mi>F</mi> <mi>r</mi> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mi>k</mi> </msub> <mo>)</mo> </mrow> </mrow> </mfrac> <mo>;</mo> </mrow>

其中e_i为第一表格T₁上满足选择条件σ的实体，count(e_i)为在初筛选阶段处理的表集Γ'中，e_i在每个表中出现次数的和，的取值为0或1；若T₂表中有e_i，则表示T₁表中满足条件σ的实体集合,

网络表之间的快照关系为:假设给定某种匹配条件，网络表T₁中匹配该条件的元组存在于网络表T₂中，T₂就被称为T₁匹配该条件的快照；

若E_adjustment≠0，则当μ＝ε,ε为实数，实验控制取值，默认为0时，S_Entity(T₁，T₂)取最大值；

若E_adjustment＝0，则当μ＝-1时，S_Entity(T₁，T₂)取最大值。

2.根据权利要求1所述的方法，其特征在于，根据Bayes模型算法，分别确定所述多个第二表格在内容方面的得分；

3.根据权利要求2所述的方法，其特征在于，

通过如下方式之一确定内容方面的得分：

<mrow> <msubsup> <mi>S</mi> <mrow> <mi>c</mi> <mi>o</mi> <mi>n</mi> <mi>t</mi> <mi>e</mi> <mi>n</mi> <mi>t</mi> </mrow> <mrow> <mi>s</mi> <mi>u</mi> <mi>m</mi> </mrow> </msubsup> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>)</mo> </mrow> <mo>=</mo> <munder> <mo>&Sigma;</mo> <mrow> <mi>a</mi> <mo>&Element;</mo> <mi>A</mi> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>)</mo> </mrow> <mo>&cap;</mo> <mi>A</mi> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>)</mo> </mrow> </mrow> </munder> <msub> <mi>P</mi> <mi>a</mi> </msub> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>&RightArrow;</mo> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>|</mo> <mi>&Psi;</mi> <mo>)</mo> </mrow> <mo>;</mo> </mrow>

<mrow> <msubsup> <mi>S</mi> <mrow> <mi>c</mi> <mi>o</mi> <mi>n</mi> <mi>t</mi> <mi>e</mi> <mi>n</mi> <mi>t</mi> </mrow> <mrow> <mi>a</mi> <mi>v</mi> <mi>g</mi> </mrow> </msubsup> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>)</mo> </mrow> <mo>=</mo> <mfrac> <mrow> <munder> <mo>&Sigma;</mo> <mrow> <mi>a</mi> <mo>&Element;</mo> <mi>A</mi> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>)</mo> </mrow> <mo>&cap;</mo> <mi>A</mi> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>)</mo> </mrow> </mrow> </munder> <msub> <mi>P</mi> <mi>a</mi> </msub> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>&RightArrow;</mo> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>|</mo> <mi>&Psi;</mi> <mo>)</mo> </mrow> </mrow> <mrow> <mo>|</mo> <mi>A</mi> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>)</mo> </mrow> <mo>&cap;</mo> <mi>A</mi> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>)</mo> </mrow> <mo>|</mo> </mrow> </mfrac> <mo>;</mo> </mrow>

<mrow> <msubsup> <mi>S</mi> <mrow> <mi>c</mi> <mi>o</mi> <mi>n</mi> <mi>t</mi> <mi>e</mi> <mi>n</mi> <mi>t</mi> </mrow> <mi>min</mi> </msubsup> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>)</mo> </mrow> <mo>=</mo> <munder> <mi>min</mi> <mrow> <mi>a</mi> <mo>&Element;</mo> <mi>A</mi> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>)</mo> </mrow> <mo>&cap;</mo> <mi>A</mi> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>)</mo> </mrow> </mrow> </munder> <msub> <mi>P</mi> <mi>a</mi> </msub> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>&RightArrow;</mo> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>|</mo> <mi>&Psi;</mi> <mo>)</mo> </mrow> <mo>;</mo> </mrow>

<mrow> <msubsup> <mi>S</mi> <mrow> <mi>c</mi> <mi>o</mi> <mi>n</mi> <mi>t</mi> <mi>e</mi> <mi>n</mi> <mi>t</mi> </mrow> <mrow> <mi>r</mi> <mi>e</mi> <mi>p</mi> </mrow> </msubsup> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>)</mo> </mrow> <mo>=</mo> <msub> <mi>P</mi> <mrow> <mi>r</mi> <mi>e</mi> <mi>p</mi> </mrow> </msub> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>&RightArrow;</mo> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>|</mo> <mi>&Psi;</mi> <mo>)</mo> </mrow> <mo>;</mo> </mrow>

其中，和均表示所述内容方面的得分，A(T₁)是第一表格T₁的属性，A(T₂)是第二表格T₂的属性，

P(T₂→T₁|Ψ)记为S_content(T₁，T₂)，

将记为Ψ,表示T₂表在某个属性上给出与T₁相同值的实体集合，表示在该属性上给出不同值的实体集合，

T₂是T₁的快照，记为T₂→T₁，

P_a(T₂→T₁|Ψ)为根据属性a的值计算的条件概率，a是表T₁和T₂的共有属性,

P_rep(T₂→T₁|Ψ)为根据代表属性rep的值计算的条件概率，代表属性是采用Google公司发布的AcsDB模式数据库获得的最具有判断意义的属性。

4.根据权利要求2至3中任一项所述的方法，其特征在于，

<mrow> <msub> <mi>S</mi> <mrow> <mi>a</mi> <mi>t</mi> <mi>t</mi> <mi>r</mi> </mrow> </msub> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>)</mo> </mrow> <mo>=</mo> <munder> <mo>&Sigma;</mo> <mrow> <msub> <mi>a</mi> <mi>k</mi> </msub> <mo>&Element;</mo> <mi>P</mi> <mi>o</mi> <mi>i</mi> </mrow> </munder> <mfrac> <mrow> <mi>P</mi> <mrow> <mo>(</mo> <msub> <mi>a</mi> <mi>k</mi> </msub> <mo>|</mo> <msub> <mi>a</mi> <mi>e</mi> </msub> <mo>)</mo> </mrow> </mrow> <mrow> <munder> <mo>&Sigma;</mo> <mrow> <msub> <mi>a</mi> <mi>i</mi> </msub> <mo>&Element;</mo> <mi>P</mi> <mi>o</mi> <mi>i</mi> </mrow> </munder> <mi>P</mi> <mrow> <mo>(</mo> <msub> <mi>a</mi> <mi>i</mi> </msub> <mo>|</mo> <msub> <mi>a</mi> <mi>e</mi> </msub> <mo>)</mo> </mrow> </mrow> </mfrac> <mo>*</mo> <mi>e</mi> <mi>x</mi> <mi>i</mi> <mi>s</mi> <mi>t</mi> <mrow> <mo>(</mo> <msub> <mi>a</mi> <mi>k</mi> </msub> <mo>&Element;</mo> <mi>A</mi> <mo>(</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>)</mo> <mo>)</mo> </mrow> <mo>;</mo> </mrow>

其中为兴趣列ɑ_k在Poi中的权重，exist(a_k∈A(T₂))的取值为0或1，若T₂表的属性中有a_k，则exist(a_k∈A(T₂))＝1；反之为0；

采用Google公司发布的AcsDB模式数据库为用户推荐表中经常查询的列，称为兴趣列Poi；给定表T₁中的实体列为ɑ_e。

5.一种选择具有快照关系的网络表格的装置，其特征在于，包括：

分类模块，用于将网络表格的集合按照所述网络表格的实体列的内容的领域进行分类，其中，所述实体列为能够标识所述网络表格的记录的属性列；

第一选择模块，用于在所述分类后的所述网络表格集合中，根据预设规则，选择与第一表格对应的多个第二表格，其中，所述多个第二表格是与所述第一表格具有快照关系的网络表格；

所述第一选择模块包括：

第二确定单元，用于分别确定所述每个表格的实体因素

<mrow> <msub> <mi>S</mi> <mrow> <mi>E</mi> <mi>n</mi> <mi>t</mi> <mi>i</mi> <mi>t</mi> <mi>y</mi> </mrow> </msub> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>)</mo> </mrow> <mo>=</mo> <msup> <mi>Fr</mi> <mi>u</mi> </msup> <mrow> <mo>(</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> <mo>)</mo> </mrow> <mo>*</mo> <mi>exp</mi> <mrow> <mo>(</mo> <mo>-</mo> <mfrac> <msup> <mrow> <mo>(</mo> <msub> <mi>E</mi> <mrow> <mi>b</mi> <mi>a</mi> <mi>s</mi> <mi>e</mi> <mo>|</mo> <mi>&sigma;</mi> </mrow> </msub> <mo>(</mo> <mrow> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> </mrow> <mo>)</mo> <mo>-</mo> <msub> <mi>E</mi> <mrow> <mi>a</mi> <mi>d</mi> <mi>j</mi> <mi>u</mi> <mi>s</mi> <mi>t</mi> <mi>m</mi> <mi>e</mi> <mi>n</mi> <mi>t</mi> </mrow> </msub> <mo>(</mo> <mrow> <msub> <mi>T</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>T</mi> <mn>2</mn> </msub> </mrow> <mo>)</mo> <mo>+</mo> <mi>&mu;</mi> <mo>)</mo> </mrow> <mn>2</mn> </msup> <mn>2</mn> </mfrac> <mo>)</mo> </mrow> <mo>;</mo> </mrow>

其中，T₁表示第一表格，T₂表示第二表格；通过如下方式确定

其中e_i为第一表格T₁上满足选择条件σ的实体，count(e_i)为在初筛选阶段处理的表集Γ'中，e_i在每个表中出现次数的和，的取值为0或1；若T₂表中有e_i，则表示T₁表中满足条件σ的实体集合；

若E_adjustment＝0，则当μ＝-1时，S_Entity(T₁，T₂)取最大值。

6.根据权利要求5所述的装置，其特征在于，所述第一选择模块包括：

第五确定单元，用于根据Bayes模型算法，分别确定所述多个第二表格在内容方面的得分；

第六确定单元，用于分别确定所述得分、S_Entity(T₁,T₂)和S_attr(T₁,T₂)的运算的结果；

7.根据权利要求6所述的装置，其特征在于，

通过如下方式之一确定内容方面的得分：

通过如下方式确定

其中为兴趣列a_k在Poi中的权重，exist(a_k∈A(T₂))的取值为0或1；若T₂表的属性中有a_k，则exist(a_k∈A(T₂))＝1；反之为0，表示T₁表中满足条件σ的实体集合；