深网 (deep Web) 是指不能通过一般的搜索引擎查找内容的Web站点.深网数据通常存储在后台的数据库中, 必须通过表单或者Ajax接口进行查询.其他类型的深网数据包括非文本文件 (如音频、图像等)、动态内容等.深网数据源是Web上很重要的一类数据源.早在2001年的研究^[1]表明:深网共有约7 500TB的数据, 是表层网的500倍, 分布在约20万个深网数据源中.查询深网数据源面临如下挑战^[2]:1) 完全覆盖单个领域的数据需要集成成千上万个数据源; 2) 不同数据源之间的数据存在很大的重叠; 3) 多数深网数据源是非合作的, 数据分布未知, 查询次数有限 (如Yahoo!Auto限制每个IP地址每天最多查询1 000次)^[3].因此, 选择合适的数据源进行查询不仅能够减少查询的开销, 提高用户的满意度, 而且可以减轻数据源的工作负载.

当前, 数据源的选择着重于相关数据源的选择^[4].相关数据源选择方法基于数据库摘要, 估计查询与数据源之间的相关性, 选择相关性得分前N的数据源.这些方法假定数据源之间的重叠在数据源选择时可以忽略, 并在查询结果合并时被去除.但在存在大量数据源时, 这个假定并不成立^[2]:忽略数据源之间的重叠造成不同数据源上相似查询结果的重复查询, 增加被查询数据源上的工作负载, 浪费数据源的访问资源.我们以例1来简单说明重叠数据源选择问题.

例1:如图 1所示, 给定查询Q和5个Web数据库A, B, C, D, E.查询Q总共有4个查询结果元组, 对应的在这5个数据源上的查询结果数量为3, 3, 2, 0, 1.假如用户想要查询所有的查询结果, 实际上不知道数据源之间关系时, 会按数据源查询结果数量一直向下查, A, B, C, E, D, 得到所有的4个元组.其中, 查询B, C, D时没有新增元组.事实上, 如果知道数据源之间的重叠关系, 我们只需查询A和E即可得到所有的结果元组.

尽管利用预先获取的数据源之间的重叠关系能够极大地提高数据源选择的效率, 然而有效地估计数据源之间的重叠是非常困难的.例1中, 5个数据源之间 (不仅仅是两两之间) 的重叠变量总共有2⁵=32个变量, 当数据源数量较大时, 需要估计的重叠变量数量将呈指数级爆炸增长, 这使得重叠数据源选择的过程非常困难.

当前, 重叠数据源选择工作大多假设给定覆盖率和重叠率^[5], 而实际中, 覆盖率和重叠率的获取都是不精确的.现有的考虑覆盖率和重叠率的重叠数据源选择方法主要有基于抽样的方法^[6]和基于最大熵的方法^[7].

1) 基于抽样的方法

基于抽样的方法以StatMiner (文献检索系统)^[6]为主, StatMiner研究基于查询的分层抽样方法解决静态Top-K数据源选择问题, 使得选择的K个数据源中不同结果元组最多.StatMiner对整个查询空间的查询进行分层抽样得到样本查询, 基于查询结果 (即样本数据) 将查询和数据源都划分为类 (即集合), 学习查询类和数据源集合类之间的覆盖率和重叠率.该方法有3点不足:首先, StatMiner生成样本的方法是基于查询分层抽样, 而非基于元组分层抽样, 这使得未被选择的查询没有查询结果; 其次, StatMiner需要学习所有的重叠率, 适用于少量的数据源, 而不适用于大量数据源的情况; 最后, StatMiner通过离线学习好的覆盖率和重叠率来对数据源静态排序, 因而在实际选择时会因为较大的统计数据误差影响深网查询的效果.

2) 基于最大熵的方法

基于最大熵的方法以OASIS^[7]为主.OASIS研究动态数据源排序问题, 使得用户尽快检索到更多不同的结果元组.它利用数据库查询优化技术估计各数据源的覆盖率, 并基于最大熵方法估计多数据源之间的重叠率, 在线运行查询并不断校准数据源的重叠率, 动态选择数据源.该方法能够容忍不精确和不完整的重叠率, 但它假定覆盖率是给定且精确的.其不足在于:首先, 在数据源非合作的情况下, 无法利用数据库查询优化器来获得精确的数据源覆盖率; 其次, 在线估计数据源的统计数据会产生较大的时间开销, 并不适用于深网数据源.图 2给出了我们在实验中考察不同数量数据源时求解最大熵问题所花费的时间开销 (我们随机生成20个查询, 在不同数量的数据源下调用matlab运行最大熵算法 (即OASIS) 获取的时间).

本文研究通过选择部分的数据源集合, 以更少的查询代价来尽可能多地获得所有的查询结果.针对现有工作中未考虑或仅考虑部分统计数据 (覆盖率和重叠率) 的不足, 本文首次提出元组级别的分层抽样方法, 解决重叠数据源选择问题.具体方法如下 (方法框架如图 3所示).

• 首先, 离线抽样获得分层样本.相对于简单随机抽样而言, 分层抽样能够得到更精确的统计数据.由于不同数据源存在不同的元组数量, 使用分层抽样的方法来估计查询在数据源上的统计数据并不容易, 为此, 我们提出一种误差约束的分层抽样框架, 能够保证查询的覆盖率和重叠率的误差, 从而保证重叠数据源选择的效率.主要策略是:基于决策树方法在查询属性中选择区分度大的分层属性, 给定误差界确定每一层中抽取元组的数量, 并随机抽取给定数量的样本.

• 其次, 在线估计查询的覆盖率和重叠率, 迭代地选择剩余覆盖率最大的数据源.

1) 尽管通过样本可以直观地估计查询在数据源上的结果数量, 然而估计查询的覆盖率和重叠率并不简单.我们基于历史查询, 通过分类和回归估计查询在所有数据源的查询结果, 得到查询在各数据源上的覆盖率.

2) 直观来看, 除非样本数量非常大, 否则用多数据源的样本来估计多数据源重叠率的准确性非常低.因此, 我们提出一种迭代式的重叠率估计方法:利用已查询数据源的查询结果和未查询的数据源的样本估计数据源之间的重叠率, 提高重叠率估计的精度.

3) 由于最大剩余策略需要比较所有未查询数据源的样本和已选数据源之间的重叠率, 时间复杂度较高, 我们提出一种“K近邻”的启发式重叠数据源选择算法, 以提高查询效率.

本文创新如下:(1) 我们研究了误差约束的分层抽样方法, 解决了重叠数据源选择问题; (2) 我们提出了一种在线迭代的数据源重叠率估算方法, 提高了覆盖率估计的精度; (3) 我们在最大剩余策略下提出一种启发式的重叠数据源选择算法, 提高了数据源选择的效率; (4) 基准数据集和真实数据集上的实验结果表明, 本文的方法能够在保证查询结果误差率的同时提高查询重叠数据源的效率.

1 相关工作 1.1 数据源摘要

在数据库领域, 数据源摘要往往通过直方图、小波、Sketches等^[8]方法来构建, 但这些方法均假设在数据源合作时, 事先知道数据源的数据分布, 并能对数据源进行聚合查询.

大多数Web数据源是非合作的, 仅能利用现有的查询接口来访问数据源.现有很多工作处理深网数据源上的抽样和聚合估计:文献[3]提供了对COUNT和SUM查询的无偏估计方法, 文献[9]描述了从深网中有效抽取随机样本进行聚合查询估计的方法, 文献[10]提出在动态深网中进行有效的抽样来进行聚合查询估计.上述工作主要考虑给定单个查询进行抽样估计查询的聚合统计数据, 不适合于抽取一批样本处理多查询的场景.

常见的数据源分析工作主要利用分层抽样方法^{[6, 11, 12]}.分层抽样是指将数据空间划分为多个层次, 然后在每层中随机抽样, 通过在数据分布广的层次抽取较多的样本, 在数据分布窄的层次抽取较少的样本来提高聚合查询估计的准确率, 因此在处理选择度低的查询时有较高的准确率.文献[6](StatMiner) 考虑深网数据源中基于查询的分层抽样, 分层方式是考虑所有查询空间的查询, 选择一部分的查询并获得查询结果作为样本数据.这种方法仅能处理少量查询.其他深网上的分层抽样工作大多集中在数据挖掘领域:文献[11]考虑在结构化深网上进行关联规则挖掘和差分规则挖掘, 但其抽样目的在于整体最小化抽样代价和估计误差; 文献[12]考虑在结构化深网上利用分层抽样方法进行K-means聚类分析, 其目标在于通过抽样更好地获得真实数据集的聚类信息 (聚类的中心和抽样比例).上述工作仅考虑在单数据源上分层抽样, 处理数据挖掘等分析任务, 无法应用于重叠数据源.

1.2 数据源选择

在非结构化数据源中, 数据源的选择主要是基于大文档和小文档的方法, 现有研究^{[13, 14]}都是基于小文档方法, 即从数据源获得代表性的样本文档集合, 在样本文档集合上建立倒排索引来进行查询, 获得相关数据源集合.在非结构化数据源中, 重叠数据源的估计是通过比较样本文档集合之间的重叠估计真实的重叠.文献[15]考虑在重叠文档数据源中, 通过抽样利用bloom过滤器来估计两两数据源中的文档的重叠从而选择低重叠的数据源, 但这种方法无法估计多数据源之间的重叠.

在结构化数据源 (Web数据库) 中, 同样可以构建数据库的摘要选择数据源^[16]:通过查询获取查询结果, 获得属性值-频率的统计数据, 建立直方图.但在深网数据源中, 我们无法直接获得属性值-频率的聚合估计值来建立直方图; 同时, 直方图数据无法用来估计数据源之间的重叠率.

基于抽样的重叠数据源选择工作主要是StateMiner^[6]方法.StatMiner假设数据源和查询的关联被转化为类 (集合) 层次; 基于样本数据, 可以学习出类间 (而非数据源间) 覆盖率和重叠率的统计数据, 选择top-K数据源集合, 使得不同的查询结果数量最多.本文与StatMiner方法的不同在于:

1) 本文考虑选择一部分数据源来得到所有查询结果, 使得总体查询开销最小.而StatMiner目标是选择top-K个数据源.

2) StatMiner是基于查询进行分层抽样, 在整个查询空间中进行抽样, 再去得到查询结果作为样本.而我们的方法是对给定查询层次, 基于其查询结果进行抽样, 在每层简单随机抽样, 使得结果数量少的查询仍然能够得到比较精确的结果.

3) StatMiner假设所有的查询都是需要通过离线学习好的覆盖率和重叠率来对数据源静态排序, 适用于少量的数据源.但实际中, 由于产生较大的统计数据误差影响数据源选择的效率; 同时, 在大量数据源选择时, 需要计算大量的统计数据, 因而非常耗时.而本文利用离线样本和在线的数据源查询结果即可得到较为精确的统计数据, 可以处理大量数据源的选择.

基于统计模型的重叠数据源选择工作主要是基于最大熵的方法OASIS^[7], OASIS考虑动态的数据源排序, 通过最大熵模型估计数据源之间的重叠率, 在线执行查询, 更新统计数据, 得到下一步要查询的数据源.本文与OASIS的不同在于:

1) OASIS目标是对数据源进行排序, 使用户尽快得到更多的查询结果, 需要查询所有的数据源.而本文的方法仅需查询一部分数据源就可以得到所有的结果.

2) OASIS仅根据查询优化器来获得数据源的覆盖率和部分数据源的重叠率, 忽略对样本数据的获取; 同时, 在线查询数据源获取查询在数据源上的统计数据, 增加了查询的开销.而我们通过对数据源进行分层抽样, 能够估计查询在数据源上的统计数据, 减少访问数据源的次数.

3) OASIS在估计数据源的重叠率时需要花费较大的时间开销, 如图 2所示, 在仅有15个数据源时, OASIS估计重叠率耗时280s.而我们利用离线样本和在线查询结果, 能够精确、快速地在线估计重叠率, 适用于大量深网数据源.

4) OASIS之所以能够迭代地更新统计数据, 在于其假定可以实时发送查询到数据源获得统计数据, 而这不适用于非合作深网数据源 (限制每天查询的次数).

5) OASIS仅考虑一个查询在多个数据源上的重叠率.本文研究不同选择度查询在多个数据源上的重叠率.

除了重叠数据源选择的研究, 其他数据源选择工作考虑了数据源的质量^[17]、时新性^[18]、可信性^[19]、收益^[20]等因素.Rekatsinas等人^[17]研究数据源质量评估和数据源选择问题, 他们利用知识库来评价数据源的质量, 将数据源选择问题建模为多目标优化问题 (如数据质量和查询代价), 并允许用户交互式地选择数据源.Rehatsinas等人^[18]还研究了动态数据源选择问题, 使得集成代价约束下选择的数据源返回的结果集合新鲜性最大.他们利用历史数据建模数据源的变化规律, 并估计数据源的时新性, 利用时新性优化目标的子模性质提出一种有效的局部搜索方法选择时新的数据源.Balakrishnan等人^[19]考虑数据源可信性评价问题, 他们在查询多数据源时, 向多个数据源发送同样的查询集合, 基于查询结果一致性来评价数据源的可信性.Dong等人^[20]研究如何选择数据源集合来平衡数据集成的精度和集成代价, 他们提出了一种单调的数据集成模型, 选择最大化总体的集成数据的精度的数据源集合.和上述工作相垂直, 本文主要考虑重叠数据源选择问题, 未来我们将考虑在重叠数据源选择问题中加入数据源的质量等因素.

综上所述, 当前重叠数据源的研究无法同时很好地估计覆盖率和重叠率.本文提出一种元组水平的分层抽样方法, 能够很好地估计覆盖率和重叠率, 并提出一种启发式的重叠数据源选择算法, 可以降低查询时间.

2 基础知识和问题定义 2.1 深网数据库模型

为了讨论方便且限于文章篇幅, 本文主要讨论类别数据, 并且不考虑有空值的元组.但我们的方法不止适用于类别数据, 同样也可以适用于数值数据, 比如数值数据可被离散化为类别数据.令Ω={d₁, d₂, …, d_h}为给定的深网数据源 (或数据库) 集合, 每个深网数据源d∈Ω, d有|d|个元组t₁, t₂, …, t_|d|和n个属性A₁, A₂, …, A_n(我们通过数据集成中的模式映射技术Global-As-View^[21]建立数据源间的模式映射关系), d中没有重叠元组 (数据表通常通过定义主键约束来避免出现数据的冗余存储, 因此不会出现重叠元组).令Dom(·) 表示返回1个或多个属性的值域函数, Dom(A_i) 表示属性A_i的领域; Dom(A_i, A_k) 表示属性A_i和A_k值域的笛卡尔乘积; |Dom(A_i)|表示Dom(A_i) 的基数 (cardinality), 即属性A_i可能取值的数量.后文我们也称查询结果的数量为查询的基数.

用户仅能通过查询接口, 即填写网页中的表单访问数据源d.因此, 一个用户查询Q为

${\rm{SELECT}}*{\rm{FROM}}\;d\;{\rm{WHERE}}\;{A_{i1}} = {v_{i1}}\;\& \ldots \& \;{A_{is}} = {v_{is}},$

其中, v_ik为Dom(A_ik) 中的取值.在访问限制的约束下, 尽管在一个周期中我们无法响应所有的查询, 但可以利用多周期^[10]来获得对应的数据源上的所有元组.

Q(d) 为Q在数据源d上满足查询Q的元组集合, |Q(d)|为Q在d上的基数.类似地, Q(Ω) 为Q在Ω上的查询结果元组集合, |Q(Ω)|为Q在Ω上的基数 (我们假定Q(Ω) 是去除冗余元组后的集合).

定义 1(覆盖率).数据源d关于Q的覆盖率为C(d)=|Q(d)|/|Q(Ω)|.令D⊆Ω为数据源集合Ω的子集, D关于Q的覆盖率定义为$C\left( D \right)={\left| {{\bigcup }_{d\in D}}Q\left( d \right) \right|}/{\left| Q\left( \mathit{\Omega } \right) \right|}\;$(我们假定覆盖率和重叠率是相对于给定的Ω而言).

定义 2(重叠率).数据源集合D⊆Ω关于查询Q的重叠率为$O\left( D \right)={\left| {{\bigcap }_{d\in D}}Q\left( d \right) \right|}/{\left| Q\left( \mathit{\Omega } \right) \right|}\;$其中, $\left| {{\bigcap }_{d\in D}}Q\left( d \right) \right|$为D中每个数据源都满足查询Q的元组的数量.

定义 3(查询代价). Q查询数据源d的代价为cost(Q, d)=ta(d)+tr(Q(d)), 其中, ta(d) 是查询数据源d的连接代价, tr(Q(d)) 为查询结果Q(d) 的传输代价.Q在查询数据源集合D⊆Ω的查询代价为$cost(Q,D)=\sum\nolimits_{d\in D}{cost(Q,d)}$.

2.2 符号定义 (见表 1)
2.3 问题描述

定义 4(重叠数据源选择问题).给定数据源集合Ω、数据源样本S={S(d)|d∈Ω}、历史查询集合 (实验中, 我们利用抽样过程中生成的查询作为历史查询), 重叠数据源选择问题为:选择数据源子集$\bar{D}\subseteq \Omega ,$在约束条件$C(\bar{D})=1$时, 最小化总查询代价$cost(Q,\bar{D}).$

定理 1.

1) 重叠数据源选择问题是集合覆盖问题的推广^[22], 是NP难问题;

2) 贪心方法 (基于最大剩余覆盖) 求解集合覆盖问题是多项式时间的$\ln \left( \left| {{\bigcup }_{d\in \mathit{\Omega }}}d \right|+1 \right)$近似算法.

证明:

1) 重叠数据源选择问题的数学规划问题为

$\left. \begin{array}{l} {\rm{Minimiz}}\;{\sum _{d \in \mathit{\Omega }}}{x_d} \cdot \mathit{cos}t(\mathit{Q},d)\\ {\rm{Subject}}\;{\rm{to}}\;C\left( {{ \cup _{d \in \mathit{\Omega }}}{x_d}d} \right){\rm{ = 1}} \end{array} \right\}$

(1)

${{x}_{d}}\in \left\{ 0,1 \right\},d\in \mathit{\Omega }$

(2)

其中, 令U=Q(Ω) 为Q在所有数据源上不同查询结果的全域, 那么对于任一数据源d∈Ω, Q(d) 是U的子集.因此, 所有的Γ={Q(d)|d∈Ω}自然地构成了U的子集族, 而cost(Q, d) 即为费用函数:$\mathit{\Gamma }\to {{\mathbb{R}}^{+}}$.因此, 重叠数据源选择问题可归约为:找Γ的子集族, 覆盖U(对应约束 (1)), 使得该子集族的总体费用cost(Q, D) 最小 (对应目标函数).

2) 由文献[23]可证.

直观地看, 数据源间查询结果之间的重叠越少, 总查询代价就越少.因此, 解决重叠数据源选择问题需要考虑如下两个问题:

① 估计查询在数据源上的统计数据 (覆盖率和重叠率);

② 基于给定的统计数据如何选择数据源.

针对问题①, 由于在线查询数据源计算查询在数据源上的覆盖率和重叠率代价很大, 因此, 采用离线对数据源分层抽样来估计查询在各数据源的基数 (见第3.1节); 在估计数据源的覆盖率时, 本文利用分类和回归的方法估计查询在Ω上的基数 (见第3.2节); 而在估计查询在多数据源上的重叠率时, 我们基于离线样本和已选数据源的查询结果来估计数据源之间的重叠率 (见第3.3.1节).针对子问题②, 本文基于估计的重叠率提出启发式的最大剩余覆盖优先的重叠数据源选择算法 (见第3.3.2节).

3 基于分层抽样的重叠数据源选择

本节我们详细描述基于分层抽样的重叠数据源选择算法.首先介绍数据源分层抽样, 然后提出数据源覆盖率计算, 最后介绍重叠数据源选择.

3.1 误差约束的数据库分层抽样

本文采用分层抽样而非均匀抽样的原因是:均匀抽样给不同的层分配层次数量比例的样本, 当抽样比例低、层中的数据量少时, 无法抽取层次中的样本.现有的分层抽样方法^[24]尽管可以通过获取属性的值域来确立层次, 但它们无法通过查询接口来进行随机抽样, 因此无法有效地控制查询结果的误差.本文扩展Arjun^[3]随机“下钻”获取随机样本的方法来实现任意数量样本的分层抽样.据我们所知, 现有利用分层抽样方法来解决数据源选择问题的只有StatMiner^[6], 但StatMiner是基于查询的分层抽样, 使得抽样中未被选择的查询层次没有查询结果, 产生较大的查询结果误差.下面我们先给出分层抽样的描述, 然后给出我们的基于误差抽样的方法.

给定数据源d(d有|d|个元组和n个属性A={A₁, A₂, …, A_n})、分层属性集合Φ⊆A.在d的所有元组中, 定义d(Φ) 为属性集合Φ上不同值x的集合, 因此, 对应于每个x都有d中的元组集合d(x)={t:t∈d且t在属性值集合Φ上取值为x}, 记d中属性集Φ上分组数量为|d(Φ)|.

分层抽样的任务为:给定查询基数的相对误差ε > 0, 从d中选择样本S(d)⊆d.对每个具体的层次d(x), 存在对应的样本集合S_x(d)⊆S(d) 为d(x) 的子集, 在S_x(d) 上运行查询估计查询基数.下面我们将给出单个数据源误差约束的分层抽样方法.

A.确定抽样层次Φ:

选择分层属性集合可以由系统设计者自行制定或者使用自动化方法 (比如决策树学习) 基于信息增益的策略对属性选择排序.对于分层属性Φ, 我们通过属性值域发现方法^[25]得到所有的层次{x₀, …, x_|d(Φ)|−1}.

例2:在TPC-W基准数据库Book表中, 我们基于属性Φ=(Year, Subject) 进行分层抽样, Year有70个不同值, Subject有24个不同值, 总共最多有1 680个层次.比如, Book中所有元组在Φ上的值为 (2000, ‘HISTORY’) 的元组构成一个层次.

由于各数据源元组数量不同, 因此对不同数据源抽取的样本数量不一.我们提出基于查询结果误差约束的抽样方法, 利用Chernoff Bound (Chernoff bound.https://en.wikipedia.org/wiki/Chernoff_bound) 来控制抽样的数量.核心想法是:在每一层中抽取样本的数量, 能够保证估计的查询结果误差在给定范围.

B.确定每层样本量N_x:

给定x∈{x₀, …, x_|d(Φ)|−1}, d (x), 查询Q, 置信度0 < δ < 1, 构造指示函数:任取元组t_i∈d(x), 如果t_i∈Q(d(x)), Y_i=1;否则, y_i=1.则$\Pr \left[ {{Y}_{i}}=1 \right]=p=\frac{\left| Q(d(x) \right|}{\left| d(x) \right|},\Pr \left[ {{Y}_{i}}=0 \right]=1-\frac{\left| Q(d(x)) \right|}{\left| d(x) \right|}$, 则${{Y}_{1}},...,{{Y}_{{{N}_{x}}}}$是独立的泊松观测.

令$\bar{Y}=\sum{_{i=1}^{{{N}_{x}}}}{{Y}_{i}},\mu =E\left[ {\bar{Y}} \right]={{N}_{x}}p$, 对于任意给定的相对误差ε > 0, 由Chernoff Bound有:

$\Pr [|\bar{Y}-E[\bar{Y}]|\ge {{N}_{x}}p\varepsilon ]\le 2\exp (-{{N}_{x}}p{{\varepsilon }^{2}}/(2+\varepsilon ))=1-\delta $

(3)

因此, 层次x确定抽取的样本数量为

${{N}_{x}}=\min \left\{ \begin{array}{*{35}{l}} \left\lceil \frac{(2+\varepsilon )|d(x)|}{|Q(d(x))|{{\varepsilon }^{2}}}\cdot \ln \frac{2}{1-\delta } \right\rceil\\ |d(x)| \\ \end{array} \right.$

(4)

总的样本数量$N=\sum\nolimits_{x\in \{{{x}_{0}},\ldots ,{{x}_{|d(\mathit{\Phi })|-1}}\}}{{{N}_{x}}}$.由公式 (4), N_x与|d(x)|成正比, 与|Q(d(x))|成反比, 并且当|Q(d(x))|=|d(x)|时得到最小数量的样本, 对应的查询为查询所有d_x中的结果 (SELECT * FROM d_x).对于层内元组数量大于$KS(\varepsilon )=\left\lceil \frac{(2+\varepsilon )}{{{\varepsilon }^{2}}}\cdot \ln \frac{2}{1-\delta } \right\rceil $的层次而言, 其抽样数量都是KS(ε); 而对于层内元组数量小于KS(ε) 的层次, 其抽样数量为|d(x)|.

例3:给定置信度δ=0.8, 相对误差ε=0.2, 假定查询Q为SELECT * FROM Book, 则层次x₁=(2000, ‘HISTORY’) 中共有757个元组, 由公式 (4), 我们需要抽取127个元组; 层次x₂=(1970, ‘POLITICS’) 共有12个元组, 由公式 (4), 需抽取12个元组.

C.每层简单随机抽样选择样本S_x:

由于我们仅能利用查询接口获取随机样本, 我们利用文献[3]中提出的随机“下钻”生成查询的方法来获取样本, 对每个x, 从d(x) 中简单随机抽样, 构成样本S_x(d).其中, 每个样本元组由如下步骤生成:

Step 1.给定x, 我们获得查询Q:Φ=x在d上的基数|Q(d(x))|.当|Q(d(x))| > topK(topK为每个网页中最大的输出元组数量), 转至Step 2;否则, 转至Step 3.

Step 2.当|Q(d(x))| > topK时, 采用随机下钻的方法生成新的查询Q':Φ=x & A_i=v_i, 其中, A_i为A\Φ中随机选择的属性, v_i为随机选择的属性值, 转至Step 1.

Step 3.当|Q(d(x))|≤topK时, 我们从查询结果中随机选择一个元组 (我们通过蓄水池抽样^[26]的方法来获得这些样本), 如果该元组已被选择, 则回到Setp 2;否则, 将该元组加入样本集合.

重复上述3步, 直到获得N_x个不同的元组为止.

例4:给定查询Q(d):Year=2000 & Subject=‘HISTORY’, |Q(d)|=757, 因此, 我们需要去“下钻”.考虑未被选择的属性, 随机选择Publisher=1(编号为1的出版社), 生成新的查询查询Q':Year=2000 & Subject=‘HISTORY’ & Publisher=1, 其结果数量为15, 小于页面最大的元组数量topK(实验中我们设定为20), 从中随机选择一个元组.然后继续从Q(d) 开始选择不重叠的元组, 直至找到127个元组.实验中, 为了提高抽样的效率, 我们选择Q(d) 的前$\left\lceil {{N}_{x}}/topK \right\rceil $个页面来获取N_x个结果元组.

通过分层抽样, 整个样本空间S(d) 是d中所有不相交的分层样本S_x(d) 的并集, 在Φ上的分层样本由N_x确定.我们将抽取的样本数据存入图 3所示的样本数据库中, 并且在样本数据库中, 对于抽取的每个元组, 增加抽样比属性 (sampleratio) 为N_x/|d(x)|, 以及元组来自数据源的sourceid.对于d(Φ) 中的每个值x, 如果|d(x)|≤N_x, 即抽样比sampleratio为1, 那么样本包含所有从原始表中抽取的元组, 该层提供精确的查询结果; 当|d(x)| > N_x时, 我们用抽取的N_x个元组估计查询的基数.利用抽取的样本S(d) 来估计查询Q在d上基数的期望为

$E[Q] = \sum\limits_{x \in \left\{ {{x_0}, \ldots ,{x_{|d(\mathit{\Phi })| - 1}}} \right\}} {|{Q_x}| \cdot \frac{{{N_x}}}{{|d(x)|}}} $

(5)

其中, Q_x为查询Q在分层样本S_x的结果元组集合.$\frac{{{N}_{x}}}{|d(x)|}$为抽样的概率, 对应的方差为

$Var(Q) = \sum\limits_{x \in \left\{ {{x_0}, \ldots ,{x_{|d(\mathit{\Phi })| - 1}}} \right\}} {\left( {1 - \frac{{{N_x}}}{{|d(x)|}}} \right){{\left( {\frac{{|d(x)|}}{{|d|}}} \right)}^2}\frac{{Var({Q_x})}}{{|d(x)|}}} $

(6)

其中, Var(Q_x) 为查询Q在分层样本S_x的方差.

对于基本的聚合算子AVG, SUM, COUNT, 由于在每一层中的抽样是基于简单随机抽样, 因此由公式 (5) 可知E[Q]是无偏的; 同时, N_x直接确定了Q估计的基数, 由公式 (6) 可知, 这些聚合算子的方差反比于N_x.

3.2 估计查询在数据源上的覆盖率

估计查询在数据源上的覆盖率需要计算查询在Ω上的基数|Q(Ω)|, 我们选择基于查询模板的机器学习方法计算|Q(Ω)|^[27].我们通过抽取查询在属性相关特征上的值, 利用基于回归的方法学习不同查询在Ω上的基数.这里的查询模板是指基于SQL查询对应的select子句、from子句和where子句中分别对应的属性和表.

在计算单个数据源上的查询基数时, 我们考虑用抽样样本而不用学习的方法, 是因为我们抽取一次样本就可以计算多次不同查询的结果.而在估算多个数据源上的查询结果时, 由于总体样本数据量比较大, 因此难以用基于样本的方法来算总体的查询结果数量, 因此在估计总体的查询数量时, 我们采用现有的黑盒式的机器学习方法, 利用现有的机器学习工具包liblinear (http://www.csie.ntu.edu.tw/~cjlin/liblinear/) 来实现.下面是机器学习方法的训练阶段和预测阶段的处理流程.

A.训练阶段

1) 对查询进行分类, 按照查询的约束的类型来分类; 2) 提取查询的特征, 包括属性、属性值、属性个数、查询结果数量; 3) 基于分组的查询, 每组查询进行线性回归, 确定回归模型LR (logistic regression)(http://en.wikipedia.org/wiki/Logistic_regression) 的参数.

B.预测阶段

1) 对查询基于模板选择回归模型; 2) 提取查询中的模板特征; 3) 基于学习出来的LR模型和查询特征值估计查询在所有数据源上的结果数量|Q(Ω)|=LR(Q).

例5:给定历史查询Q(Ω):SELECT * FROM Ω WHERE PubYear between 1930 and 1935 & Subejct= ‘HISTORY’ & Cover=‘Hardback’, 我们基于训练阶段的结果得到特征向量 (1, 1, 1, 0, 30, 6, 3, 6), 其中, 向量中的前3个1代表where条件中出现的属性Pubyear, Subject和Cover, 0代表未出现的属性Publisher, 30和6代表出现的年份和持续的时间, 6, 3和6代表Pubyear, Subject和Cover值在所有取值中的顺序.查询的|Q(Ω)|值为737.

基于抽样样本和学习的总体样本数据大小估算Q在数据源d_i上的覆盖率为C(d_i)=|Q(d_i)|/|Q(Ω)|.然后, 我们对覆盖率由大到小进行排序.不失一般性, 我们假设得到的数据源为d₁, …, d_h.

• 数据源样本抽样讨论

观测:通过TPC-W数据集上的实验我们发现, |Q(Ω)|和cost(Q) 之间存在如下规律.

1) 当|Q(Ω)|≥9835时 (图 4, 查询选择度约为0.1), 得到Q(Ω) 需要查询Ω.原因在于, 当Q(Ω) 较大时, 数据分布较广, 此时|Q(Ω)|和cost(Q) 成正比例关系 (如图 5所示).比如, 当我们想要获得|Ω|时, 我们需要去查询所有的数据源.

2) 当|Q(Ω)| < 9835时 (如图 4所示), 我们通过样本估计|Q(Ω)|的误差较大, 想要准确估计|Q(Ω)|需要查询较多的数据源.比如, 我们想要查询单个元组, 从大量的数据中抽样难以估计准确的查询基数, 进而需要查询更多的数据源.

结论:例3假定查询为查询所有数据源上的元组, 但我们需要处理不同选择条件的查询, 因此需要选择合适的查询基数决定抽样数量.查询基数较大时, 由公式 (4) 知抽取的样本数量较少, 用样本回答其他查询基数小的查询误差会比较大; 查询基数数量少时, 我们抽取的样本数量比较多, 可以很好地回答所有的查询, 但对应的抽样数量大.因此结合图 4, 我们折中考虑查询选择度为0.1来推导我们实验中抽样数量.

3.3 重叠数据源选择 3.3.1 数据源重叠率估计

精确估计查询在数据源之间的重叠是很困难的, 我们将讨论两种基于样本估计查询在数据源上重叠率的方法:完全基于样本的方法和部分基于样本的方法.

完全基于样本的方法是通过不同数据源之间的样本估计数据源之间的重叠率.以图 6为例, 按照覆盖率排序, 我们知道C(d₁) > C(d₂) > C(d₃), 那么先查询d₁, 然后选择查d₂还是d₃.选择数据源的原则是考虑最大剩余覆盖的数据源, 即考虑|Q(d₂)-Q(d₁)|和|Q(d₃)-Q(d₁)|的大小, 完全基于样本的策略是:通过样本中重叠的元组来估计原始的数据源重叠元组的数量.假设查询Q在数据源样本S(d₁) 和S(d₂) 上查询结果元组集合为Q(S(d₁)) 和Q(S(d₂)), 那么我们可以推导出^[15]查询Q在据源d₁和d₂中的重叠率为

$O(Q({d_1}),Q({d_2})) \approx \frac{{|Q({d_1})| \times |Q({d_2})| \times |Q(S({d_1})) \cap Q(S({d_2}))|}}{{|Q(S({d_1}))| \times |Q(S({d_2}))| \times |Q(\mathit{\Omega })|}}$

(7)

其中, |Q(d_i)|可以通过样本S(d_i), 基于公式 (5) 估计出来 (i=1, 2).通过公式 (7), 我们可以估计|Q(d₂)-Q(d₁)|=|Q(d₂)|-|O(Q(d₁), Q(d₂))|×|Q(Ω)|.类似地, 我们可以估算|Q(d₃)-Q(d₁)|.然而由公式 (7) 可知:当样本数量很少时, 要么结果数量为0, 要么结果非常大, 通过这种方法估计查询在不同数据上的结果数量误差非常大.因此, 我们将利用部分基于样本的方法来估计数据源之间的重叠率.

部分基于样本的方法是通过已查询的数据源结果和未查询数据源的样本来估计数据源之间的重叠率.如图 7所示, 按照覆盖率排序, 我们知道C(d₁) > C(d₂) > C(d₃), 需要估计|Q(d₂)-Q(d₁)|和|Q(d₃)-Q(d₁)|的大小来选择剩余覆盖最大的数据源.我们已获得Q(d₁), 通过比较Q(d₁) 和Q(S(d₂)) 的相同元组来估计Q(d₁) 和Q(d₂) 中重叠元组的数量.

$O(Q({{d}_{1}}),Q({{d}_{2}}))\approx \frac{|Q({{d}_{2}})|\times |Q({{d}_{1}})\cap Q(S({{d}_{2}}))|}{|Q(S({{d}_{2}}))|\times |Q(\mathit{\Omega })|}$

(8)

其中, |Q(d_i)|可以通过样本S(d_i), 基于公式 (5) 估计出来 (i=1, 2).

通过公式 (8), 我们可以估计|Q(d₂)-Q(d₁)|, 进一步可以估计|Q(d₃)-Q(d₁)|的大小.这样, 我们只需一个数据源的样本就能估计两个数据源的重叠元组数量.同时, 样本数量越多, 我们估计的重叠率就越准确.从而我们有如下定理.

定理 2.假定已查询的数据源为D_Sel, 查询结果集合为Q(D_Sel), d_k为未选数据源集合D_Unsel中的任一数据源, 则查询Q关于D_Sel和d_k的重叠率估计量为$O(Q({{D}_{Sel}}),Q({{d}_{k}}))\approx \frac{|Q({{d}_{k}})|\times |Q({{D}_{Sel}}))\cap Q(S({{d}_{k}}))|}{|Q(S({{d}_{k}}))|\times |Q(\mathit{\Omega })|}.$

证明:令$M=Q({{D}_{Sel}})\cap Q({{d}_{k}}),{{m}_{k}}=Q(S({{d}_{k}}))\cap M$.对d_k简单随机抽样, 有|m_k|=|Q(S(d_k))|×M/|Q(d_k)|.已知Q(D_Sel) 和Q(S(d_k)), 我们用$\left| Q({{D}_{Sel}})\cap Q(S({{d}_{k}})) \right|$来近似|m_k|, 即有$O(Q({{D}_{Sel}}),Q({{d}_{k}}))\approx \frac{|Q({{d}_{k}})|\times |Q({{D}_{Sel}}))\cap Q(S({{d}_{k}}))|}{|Q(S({{d}_{k}}))|\times |Q(\mathit{\Omega })|}.$

尽管我们给出了部分基于样本的数据源重叠率估计方法, 然而重叠率估计的准确性主要由查询和抽样样本确定.直观上, 各数据源仅有完整查询结果的部分数据, 因此查询在不同数据源上的基数很大, 抽样数量越多, 估计的准确性越高.值得说明的是, 随着查询的数据源越来越多, 合并的查询结果集合越来越趋近于完整的结果, 这使得未被选择的数据源和已得到的查询结果之间的重叠率估计越来越准确.后面, 我们将通过实验来说明查询选择度和抽样数量对查询在数据源上的重叠率影响.

3.3.2 重叠数据源选择算法

正如我们在第3.3.1节中介绍的, 完全利用样本的方法会产生较大的误差, 因此, 我们利用基于部分样本的方法来估计数据源之间的重叠.由于数据源选择问题是集合覆盖问题的推广, 直观的想法就是利用贪心算法来求解数据源选择问题, 我们已在定理1中说明:在准确计算数据源查询结果时, 贪心算法求解集合覆盖问题是多项式时间的$\ln \left( \left| \bigcup\nolimits_{d\in \mathit{\Omega }}{d} \right|+1 \right)$方法.但由于抽样导致估计查询结果的精度不同, 每次选择剩余覆盖最大的数据源是不精确的, 因此, 我们无法直接在利用样本估计覆盖率的情况下给出基于样本的贪心方法的近似保证, 但我们将在实验部分讨论贪心方法的误差.

给定估计的覆盖率和备选的h个数据源.选择数据源的基本想法是:基于覆盖率大小顺序, 选择未选数据源中 (相比已选数据源) 剩余覆盖最大的数据源.首先, 我们给出基于样本的最大剩余覆盖数据源优先的算法OverlappingSourceSelection (如图 8所示), 即每次从未被查询的数据源中选择估计的剩余覆盖率最大的数据源.假设已查询的数据源集合为D_Sel, 合并的查询结果为Q(D_Sel), 未查询的数据源集合为D_Unsel, 我们需要估计每个数据源d_i∈D_Unsel和D_Sel之间的重叠率.算法如图 8所示.算法的第3行~第5行估计未选数据源和已选数据源查询结果间的重叠率; 第6行是选择新增元组数量最多的数据源; 第7行~第9行运行查询计算数据源d_t中新增元组的数量, 并移除已查询的数据源; 第10行是跳过新增覆盖率为0的数据源.算法在总体数据源覆盖率为1或D_Unsel为空时停止.算法1的时间复杂度为O(h²)×f(Q)+cost(Q, D_Sel), 其中, f(Q) 为每次估计已查询结果RS和未查询数据源d_t之间重叠率的时间.由于总共有h个数据源而每次都需要和剩下所有的数据源进行比较, 总共最多需要比较h(h-1) /2次, 因此, 在本地估计重叠率的总的时间为O(h²)×f(Q), 而在线查询的代价为cost(Q, D_Sel), 即, 查询所有选择的数据源D_Sel对应的开销.

由于算法1考虑Q(D_Sel) 与每个d_i∈D_Unsel的重叠, 时间复杂度较高, 因此我们每次仅考虑D_Unsel中覆盖率较大的前k个数据源, 提出算法2, 即KOverlappingSourceSelection算法.直观的原理是, 覆盖率较大的数据源更有可能存在剩余覆盖大的数据源.假定D_Unsel中覆盖率最大的前k个数据源为K(D_Unsel), k值太小, 只能找到局部最优的剩余覆盖大的数据源; 而k值较大, 估计重叠率会产生较大开销.因此, 我们通过实验确定如何选择k值.实验中我们发现, 当k=1时m对应的算法效果最好, 具体算法如图 9所示.

由于算法2中比较已选数据源和重叠数据源之间的重叠率只需考虑前k个数据源, 因此对应的时间复杂度为O(kh)×f(Q)+cost(Q, D_Sel), 其中, f(Q) 为每次估计计算已查询结果RS和未查询数据源d_t之间重叠率的时间.由于总共有h个数据源, 而每次都需要和未被选择的数据源中覆盖率最大的k个进行比较, 总共最多需要比较kh次, 因此在本地估计重叠率的总的时间为O(kh)×f(Q), 而在线查询的代价cost(Q, D_Sel) 为查询数据源集合D_Sel的代价.

4 实验结果及分析 4.1 实验准备

TPC-W数据集.我们用TPC-W基准^[28]生成97 671个不同的元组, 存储在关系表Book(book_id, pubyear, publisher, subject, cover) 中.我们考虑将这些元组划分到100个数据源 (即100个数据表), 每个元组随机分配到1个~20个数据源中.但选择的2 0个数据源的范围通过Zipf分布确定, 对应的参数z=1.各数据源统计数据见表 2.我们在Book关系表中选择相对区分度大的pubyear和subject作为分层属性.通过查询在线书店 (京东、当当等), 我们观测数据源的平均的连接时间为200ms~800ms, 每个元组的平均传输时间为0.3ms.实验中, 利用这些统计数据模拟数据源的连接时间和数据的传输时间.此外, 通过观察在线书店的页面, 我们设置topK=20.

Abebooks数据集.我们使用公开的在线数据Abebooks数据集^[29], 该数据集包含895个数据源, 1 265个不同的元组, 共24 819个元组.我们使用文献[7]中的方法将其扩展成1 260个数据源, 1 265个不同的元组, 共33 865元组.各数据源统计数据见表 2.我们选择相对区分度大的pubyear和subject作为分层属性.通过在线测试, 数据源的连接时间为141ms~300ms, 每个元组的传输时间为0.35ms, 这里, topK=20.

抽样方法.我们比较3种主要的抽样方法:简单随机抽样、基于查询的分层抽样和基于元组的分层抽样方法.我们建立样本表Sample(book_id, pubyear, publisher, subject, cover, sampleratio, sourceid), 相对于Book表, 我们增加了字段抽样概率sampleratio和数据源sourceid.

简单随机抽样.随机选择一个初始查询条件 (查询属性和属性值), 当查询结果大于单个网页显示的最大元组值topK时, 我们随机增加查询条件 (查询属性和属性值), 直到查询结果小于等于topK为止, 保存查询结果.重复这一过程, 直到获得所需数量的样本为止.

基于查询的分层抽样 (即StatMiner^[6]提出的抽样方法).在所有的层次中, 我们随机选择1个层次, 获取并保存该层次所有的查询元组.重复上述过程, 随机选择另一层次, 直到获得所需数量的样本.值得注意的是, 由于每次查询只能获得单个网页上的查询元组, 因此当单个层次中的结果数量远大于topK时, 我们需要发送多个查询来获得该层次的所有查询元组.

基于元组的分层抽样.本文提出的方法.实验中, 如果确定抽取的样本数量N_x, 我们通过查询该层次查询结果中的前$\left\lceil {{N}_{x}}/topK \right\rceil $个页面来获取N_x个结果元组.

算法.我们实现并比较如下数据源选择算法.

• Random:随机选择数据源的数量.

• Coverage^[5](Coverage):按覆盖率大小降序选择最大覆盖率的数据源.

• Maxent算法^[6](OASIS)(OASIS使用LINDO软件, 但免费版Lindo最多能够计算300个变量, 因此我们使用Matlab来求解最大熵问题):利用最大熵模型在线估计数据源之间的重叠率, 查询数据源不断校正数据源的覆盖率, 选择最优剩余覆盖的数据源.其中, 用Matlab中的非线性interior-point算法 (http://cn.mathworks.com/help/optim/ug/fmincon-interior-point-algorithm-with-analytic-hessian.html) 求解最大熵问题.

• OverlappingSourceSelection (OSS):本文提出的基于样本最优算法.

• KOverlappingSourceSelection (KSS):本文提出的基于样本的启发式数据源选择算法.

• Full-knowledge (最优算法)(Optimal):基于精确的统计数据以及最大剩余覆盖策略查询数据源得到的时间.

我们用Java 1.6在Windows7上 (3.2GHZ Intel Core i5 CPU和8G的RAM) 实现了上述所有的算法, 并用PostgreSQL 9.4数据库来存储数据.

评价标准.我们随机选出20条不同选择度的查询作为测试查询, 其中, 查询结果的选择度分布在0.006~0.79之间.为简单起见, 将选择度在0.006~0.1之间的查询称为低选择度查询 (0.1对应查询结果数量为9 835), 选择度在0.1~0.2之间的查询称为中选择度查询, 0.2~0.79之间的查询称为高选择度查询.实验中, 考虑3类选择度查询中的均值.我们考虑如下两个方面的评价尺度:(1) 在抽样方法中, 我们考虑抽样的代价 (即获得样本所需要发送数据源的查询数量) 和查询基数的误差 (包括覆盖率相对误差和重叠率相对误差); (2) 在数据源选择的过程中, 我们考虑查询性能 (查询的平均执行时间和查询的数据源数量) 和查询基数的相对误差.

4.2 TPC-W合成数据集

首先需要说明的是, 基于查询的抽样方法不能直接获得其潜在的数据分布, 因此无法直接分析查询在其样本上的误差.因此, 我们对每个数据源分别用不同的抽样方法抽取5%, 7.5%, 10%, 12.5%的元组作为样本数据.

4.2.1 统计数据精度对比

表 3和表 4分别展示了不同的抽样方法随样本数量变化时, 不同选择度查询的覆盖率和重叠率的平均相对误差.

从表 3的实验结果来看,

(1) 本文提出的基于元组的分层抽样方法对应的查询覆盖率误差最小; 简单随机抽样方法估计的覆盖率误差最大, 均大于1.其原因在于, 简单随机抽样相对于基于元组的分层抽样会在元组数量少的层次中抽取较少的元组, 因此误差较大; 而基于查询的分层抽样方法仅选择一部分层次代表整个数据源, 其误差也大于基于元组的抽样方法的查询覆盖率误差, 但相对于简单随机抽样而言基于查询层次来抽样, 使得新的查询在已选的层次上对应的误差较小, 而在未选的层次上误差较大, 但总体的误差比均匀抽样时的误差要低.

(2) 3种抽样方法的覆盖率误差都会随着样本数量的增加而减小, 覆盖率误差均随着查询选择度的增加而减小.

从表 4中容易看出, 基于元组的分层抽样方法对应的查询覆盖率误差最小.其原因在于, 样本数量增加, 查询选择度增加, 使得满足查询的样本元组越多, 估计的覆盖率就越准确.表 4的实验结果整体上和表 3中的趋势一致, 然而由于查询在数据源之间重叠结果一般小于查询在对应数据源上的查询结果, 对应的相对误差较大, 这使得重叠率的相对误差比覆盖率的误差更大, 尤其是对分层抽样方法 (覆盖率更准确).

表 5展示的是在少量 (10个) 数据源时最大熵方法和分层抽样方法估计的重叠率的相对误差 (我们仅考虑10个数据源是因为matlab求解最大熵问题非常耗时), 其中, 最大熵方法和分层抽样方法中都是首先通过分层抽样方法估计的覆盖率再估计重叠率.从实验结果来看:(1) 最大熵方法估计的重叠率的误差远大于基于元组分层抽样方法估计的重叠率的误差; (2) 基于分层抽样估计的相对误差随着查询选择度的增加和样本数量增加而减小, 但最大熵的方法估计的重叠率误差却维持在较高的水平.其原因在于:

• 首先, 由于估计的覆盖率 (即最大熵方法的输入) 本身存在误差.

• 其次, 由于OASIS是通过伸缩性地放松约束条件求解最大熵问题, 因此同样的输入会产生较大的误差; 而基于元组的分层抽样方法能够利用在线的查询结果来不断校准数据源之间的重叠率, 因此对应的误差较小.

表 6展示了不同抽样方法生成相同比例样本数据所需的查询数量.从实验结果来看, 基于分层抽样方法所需要的查询数量最少; 而随着样本数量的增加, 查询的数量在不断增加.值得注意的是:(1) 基于元组分层抽样的方法在7.5%和10%的样本时查询数量是一样的, 这是因为此时每一层中查询的元组都在相同的页面中; (2) 简单随机抽样方法由于需要不断“下钻”, 因此需要更多的查询, 而基于元组的抽样方法和基于查询的抽样方法随着样本数量的增加而越来越趋近, 这是因为两种方法都是通过对层次中的元组进行抽样所致 (选择页面中的元组所致).

4.2.2 执行时间对比

图 10(a)和图 10(b)分别对应不同选择度查询和不同样本下OSS算法的效率、查询基数误差和查询的数据源数量.从图 10(a)我们可以看到:

(1) 查询选择度越高, 则查询执行时间增大, 查询结果的相对误差越小, 在12.5%的样本上, 所有查询对应的误差率能够保证在0.5%以下.值得注意的是, 对于高选择度查询, 查询的执行时间随着样本数量增加而变缓, 其原因在于, 样本数量增加导致覆盖率和统计率估计的误差较小, 使得查询的数据源数量变少 (如图 10(b)所示).

(2) 随着样本元组数量变大, 查询结果的误差在不断减小, 其中, 高选择度查询误差最小, 低选择度查询的误差最大.如图 10(b)所示, 随着样本数量的增加, OSS查询的数据源数量逐渐增加并逐渐趋于稳定.

图 10(c)和图 10(d)分别对应不同选择度查询和不同样本下KSS算法在不同的k值时所对应的查询执行时间、查询结果误差和查询数据源数量.从图 10(c)可以看到, 随着k值增大, 不同选择度查询的执行时间增加.这是因为KSS需要估计多个数据源和已选数据源结果之间的重叠率, 但对应的查询结果误差并不是随着K值的增加而减小, 因为估计的数据源查询结果元组数量较少使得估计的最大剩余覆盖对应的误差变大 (图 10(c)中, 低选择度查询的误差在增加).图 10(d)显示, 查询的数据源数量随着k值的增大基本不变.其原因在于, 按最大剩余覆盖选择数据源基本上选k=1时对应的数据源.

综合图 10中OSS和KSS的分析, KSS的执行时间和查询基数误差上均优于OSS.而KSS在k=1时对应的误差率和查询执行时间均为最优.下面我们用使用KSS算法 (k=1) 与现有方法进行比较.

图 11展示的是KSS和其他不同的数据源选择算法在查询时间、误差上的分析.从图 11(a)~图 11(c)不难看到:KSS算法的执行时间在小数据量样本时, 优于最优的时间, 代价是较大的误差 (如图 11(d)所示); 而Coverage算法在低选择度查询时优于Random算法, 但在其他选择度查询时性能近似.其原因在于, 中选择度和高选择度查询需要查询的数据源较多, 因而相对的查询的数据源数量近似, 查询时间趋于一致; 随着样本数量增大, KSS的执行时间不断增加, 其并超过Optimal的查询时间.值得注意的是, 图 11(a)~图 11(c)中, KSS和Optimal相交的点对应的样本数量随查询选择度增加而增加.其原因在于:(1) 样本数量增大, 估计查询的覆盖率和重叠率时间增大; (2) 样本数量越多, 查询选择度越大.结合图 11(d)不难得出, 其对应的结果误差在不断减小, 查找的元组就越来越多.总体上, 我们可以将查询结果误差控制在1.2%以内.

表 7分析了仅有10个数据源时, KSS (K=1) 和OASIS算法在查询效率上的对比 (OSASIS需要估计所有的重叠率变量, 使用matlab运算最大熵算法耗时很长).从表 7中不难看出, 估计数据源重叠变量的时间占据了OASIS的主要时间, 平均每次估计耗时15 375ms, 远大于KSS查询数据源的时间; 同时也可以看出, KSS算法近似于Optimal算法的运行时间.

表 8和表 9分别分析了KSS在不同抽样方法下对应的查询执行时间和查询基数误差.

从表 8我们可以看到, 基于元组的分层抽样方法和基于简单随机抽样方法的查询执行时间近似, 但均高于基于查询的分层抽样的时间.其原因在于基于查询的分层抽样仅抽取一部分的层次, 因而对未抽取的层次估计的查询基数为0, 从而忽略很多数据源, 导致查询时间快, 查询基数的误差较大 (见表 9).尽管基于元组的分层抽样方法和简单随机抽样方法在查询执行时间上近似, 但在查询结果误差上, 前者显然要优于后者.其原因在于, 基于元组的抽样方法能够提供更精确的覆盖率和重叠率估计.值得说明的是, 在估计覆盖率和统计率时, 简单随机抽样方法估计的统计数据的误差要远大于基于查询的分层抽样方法的误差; 在估计总体的查询结果误差时, 简单随机抽样的结果要劣于后者.其原因在于, 简单随机抽样是均匀地在每层抽取等比例的样本, 导致估计的覆盖率和重叠率率远大于真实的统计数据, 使得在运行KSS时不会跳过某些数据源; 而基于查询的分层抽样方法由于仅选择一部分的层次, 估计的覆盖率和率低于真实的数值, 使得KSS容易跳过某些数据源, 最终, 总体的查询结果误差较大.

4.3 Abebooks真实数据集

本节我们分析Abebooks真实数据集上的实验结果.和TPC-W数据集一样, 我们对每个数据源分别用不同的抽样方法抽取5%, 7.5%, 10%, 12.5%的元组作为样本数据.

4.3.1 统计数据精度对比

表 10和表 11分别展示了Abebooks数据集上不同抽样方法随样本数量变化时, 不同选择度查询的覆盖率和重叠率的平均相对误差.

表 10的实验结果展示了与TPC-W数据集上相似的结果.

(1) 本文提出的基于元组的分层抽样方法对应的查询覆盖率误差最小, 简单随机抽样方法估计的覆盖率误差最大, 但简单随机抽样的误差要远小于TPC-W数据及上的误差.其原因在于, 真实数据集上数据源的元组数量较少, 因此简单随机抽样相对来说趋近于基于查询的抽样.

(2) 3种抽样方法的覆盖率误差都会随着样本数量的增加而减小, 覆盖率误差均随着查询选择度的增加而减小.

表 11的实验结果也容易看到, 基于元组的分层抽样方法对应的查询覆盖率误差最小.其原因在于, 样本数量增加, 查询选择度增加, 使得满足查询的样本元组越多, 估计的覆盖率就越准确.

表 12展示的是在Abebooks数据集上少量 (10个) 数据源时, 最大熵方法和分层抽样方法估计的重叠率的相对误差.从实验结果来看, 也展示了与TPC-W数据集上相似的性质:(1) 最大熵方法估计的重叠率的误差远大于基于元组分层抽样方法估计的重叠率的误差; (2) 基于分层抽样估计的相对误差随着查询选择度和样本数量的增加而减小.

表 13展示了不同抽样方法生成相同比例样本数据所需的查询数量:基于查询的分层抽样方法需要的查询数量最少, 基于元组的分层抽样方法其次, 而简单随机抽样方法最多.其原因在于, 简单随机抽样方法由于需要不断“下钻”, 因此需要更多的查询, 而基于查询的方法仅需确定层次属性值对应的查询, 单个数据源仅需较少的查询来访问数据量少的数据源.

4.3.2 查询执行时间对比

图 12(a)和图 12(b)分别对应不同选择度查询和不同样本下OSS算法的效率、查询基数误差和查询的数据源数量.我们可以看到, 查询选择度越高, (1) 查询执行时间增大, 查询结果的相对误差越小, 选择度越高的查询结果误差越小 (如图 12(a)所示); (2) 查询的数据源数量在不断减少并逐渐趋于稳定, 选择度高的查询的数据源数量越多 (如图 12(b)所示).

图 12(c)和图 12(d)分别对应不同选择度查询和不同样本下, KSS算法在不同k值下所对应的查询执行时间、查询结果误差和查询数据源数量.从图 12(c)可以看出, 随着k值的增大, 不同选择度查询展现了与合成数据集上不同的性质:(1) 随着K值的增加, 查询时间缓慢增长; (2) 查询结果误差不断减小, 并趋近于稳定; (3) 查询的数据源数量在缓慢减少.其原因在于, 从OSS中我们发现, 在Abebooks上, 对于任意查询, 我们仅需少量数据源 (不超过20) 即可查询到所有的结果 (如图 12(d)所示), 因此, 我们不需要去查询后面那些覆盖率低且增益少的数据源.

综合图 12中OSS和KSS的分析, KSS的执行时间和查询基数误差上均优于OSS.而KSS在k=3时对应的误差率和查询执行时间均为最优.下面我们用使用KSS算法 (k=3) 与现有方法进行比较.

图 13展示的是Abebooks数据集上KSS和其他不同的数据源选择算法在查询时间、误差上的分析.

从图 13(a)~图 13(c)不难看出:

(1) KSS的执行时间高于Optimal, 低于Coverage和Random; 同时, Coverage和KSS算法的执行时间随着样本比例增加而缓慢增加, 其原因在于需要查询样本的数量相对增加.

(2) KSS略高于Coverage的执行时间, 其原因在于KSS能够利用数据源间的重叠来减少查询开销.

图 13(d)展示的是不同选择度查询对应的查询结果误差.随着样本数量和查询选择度的增加, 查询结果的误差越来越小, 大部分的误差都在1.2%以下.

表 14分析了仅有10个数据源时, KSS (K=3) 和OASIS算法在查询效率上的对比.从表 14中不难看出:

• 估计数据源重叠变量的时间占据了OASIS的主要时间, 平均每次估计耗时14 837ms, 远大于KSS查询数据源的时间.

• 同时也可以看出, KSS算法近似于Optimal算法的运行时间.

表 15和表 16分别分析了KSS在不同抽样方法下对应的查询执行时间和查询结果数量误差.

从表 15不难看出:

• 由于数据源的数据量少, 同时查询所有数据源所需要的数据源数量较少, 使得这3种方法的查询执行时间近似.

• 但由于分层抽样方法更高的覆盖率和重叠率的估计精度, 使得KSS的误差相对较小, 同时查询的执行时间更长.

和TPW-W数据集类似, 表 16展示了Abebooks上不同抽样方法生成相同比例样本数据所需的查询数量:基于查询的分层抽样方法需要的查询数量最少, 基于元组的分层抽样方法其次, 而简单随机抽样方法最多.

综上所述, 基于元组的抽样方法尽管抽样代价趋近于基于查询的抽样方法, 但能保证较高的覆盖率和重叠率的估计误差; 虽然OASIS能够伸缩性地解决多重叠数据源排序问题, 但是在深网数据源的环境下, 我们提出的KSS算法能够得到更高的效率和更小的误差.

5 总结与展望

在海量深网数据源查询的过程中, 探索和利用数据源之间的重叠能够极大提高深网查询的效率.本文提出一种元组水平的分层抽样方法来估计和利用查询在数据源上的统计数据, 选择高相关、低重叠的数据源.该方法分为两个阶段:离线阶段, 我们基于元组水平对数据源进行分层抽样, 获得样本数据; 在线阶段, 我们基于样本数据迭代地估计查询在数据源上的覆盖率和重叠率, 并采用一种启发式策略以高效地发现低重叠的数据源.本文在基准数据集和真实数据集上进行实验, 结果表明, 在能够保证用户精度需求的同时, 与传统方法相比, 能够显著提高效率.