论文摘要：由于在Web数据库中存在着海量的信息，而这些信息隐藏在具有特定查询能力的查询接口后，从而为了解Web数据库的分布、更新等内容特征带来的困难，最终阻碍了DeepWeb数据集成。文章基于这一问题提出了一种新的数据采样方法，这种方法可以以增量的方式通过查询接口从Web数据库中获取近似随机样本，同时利用已经保存在本地的样本记录生成下次查询。

关键词：图模型；Web；数据库；取样

随着Web的迅速发展，当今的Web已经成为一个巨大的信息源，数据库采样是一个从数据库随机选取记录的过程，可以获得数据库中有用的统计。文章提出的一种“Web数据库取样由于不受查询接口属性表现形式的限制，为此可以在本地模拟试验中表现出优异的性质。

1WDB-Sample基本思想
　　WDB-Sample的基本思想可以分为四大步：第一步是从一个任意的有效查询开始进行查询；第二步是从以上查询所返回的结果中抽取记录；第三步是将获得的记录放于本地样本库；最后是从样本库中选取一个记录并将其作为Web数据库的下一次查询。然后转入第二步。
　　对Web数据库的采样需要应对两个挑战，其一是所获得的样本的偏差，要求样本的数据分布与Web数据库保持一致；其二是获得样本的代价，要保证通过尽量少的查询次数来获得这些样本。

2一种基于Web数据库的图模型
　　2.1Web数据库模型概述
　　这里我们提出一种全新的基于Web数据库图模型，这一模型可以通过图游历的方式达到对于Web数据库的采样。这一模型中的每个顶点以及每个边都附加了一个唯一的查询，而对于每个顶点相当于记录在集合R中的只有顶点对应的那个记录。而对于每条边相当于仅有记录集合R中与该边所连接的两个顶点所对应的记录。此外，WebDatabasegraph（WG）与WDB所提供的查询接口的查询能力之间相关，因为所涉及到的所有的查询均是查询接口中可以表达的。从而导致两个记录在WG中是存在一条边主要由是否存在一个查询接口可表达的查询可以满足两个记录，换句话来讲决定于顶点与边上附加的查询接口能力。为此即使是针对于具有相同内容的WDB，如果二者的查询接口的能力不同也会导致查询能力的差异。
　　2.2基于WG的Web数据库采样方法思想
　　借助于图模型可以将任意的一个WDB在记录层上转换为图进行表达，从得到的图模型可以得到支路之间的关联关系。如果要对WDB增量式的采样方法，正如上文所述的WDB-Sample思想，需要解决样本的选取、查询的选择以及终止条件。但是下面我们主要对如何在WG中采用图游历的思想实现对WDB增量式的采样。
　　鉴于我们难以越过查询接口而直接获得WDB的所有记录，为此基于WG的Web的数据采样思想如下所述：首先从任意的一个查询Q0开始，并提交WDB；其次将查询得到的结果记录保存于本地RL，并对得到的记录RL建立WGL；在此基础上判定是否达到终止条件，如果是则停止，反之进入下一步；通过对建立的WGL的分析，从RL中选择合适的记录形成下一次查询，转入开始的第一步。
　　尽管在进行开始查询中使用人工选择的Q0点开始具有一定的主观性，但是只要保证Q0的查询结果足够多就可以保证Q0是WG中度较大的一个，从而避免不同查询带来的采样差异。同时随着RL中的记录数量不断增加，WGL随着扩大，为此我们仅需要将每次的查询记录添加到当前的WGL中，而不是重新构建WGL，其中WGL是WG的一个子图。而采样中最为关键的问题是第三步、第四步，其问题体现在：如何根据WGL从当前的记录中选择合适记录、
　　2.3WDB-Sampler算法
　　前面已经对WDB-Sampler算法的采样思想进行了简述，不再复述。这里指出一点：对于每次的查询结果，我们仅获取第一页中的记录。这样做是基于以下两个考虑：首先是要对这次查询中更多次的记录需要不断地翻页，而翻页本身也是一种查询操作。其二是由于所有的查询结果均满足此次查询，为此会导致偏差的增加。
　　2.4记录的选择
　　为了进行查询操作需要从当前存储的本地记录中选择一个个合适的记录作为查询，而这也正是recordselector的功能。所选择的的查询记录要可以获得更多新的记录。基于WG进行解释，也就是从当前的WGL中选择一个顶点v，然后通过v查询到更多的尚不属于WGL的顶点。为此查询中我们将WGL中的顶点按其度进行从低到高的排列，并选择度最小的顶点。度最小的顶点可能是在WG中的度较小，也可能是在WG中有很多与之相邻的新顶点。为此如果发现获得纪录少于k则可以丢弃这一顶点并选择其余顶点中度最小。
　　2.5查询的生成
　　选择了WGL中的一个顶点后就可以从中选定一个记录，然后利用queryGenerratot生成下一次查询。由于一个记录可以得到若干查询，为此对于每一个记录都要根据RL中的记录建立相应的统计信息。
　　2.6采样过程终止
　　如果在图模型数据取样中不设置采样终止条件，那么采样过程就会一直进行下去，从而在理论上可以获得WDB中的所有记录，但是我们仅需要足够的样本记录，而非全部。为此需要设定两个常量nq与？啄，其中nq是一个大于1的自然数，而？啄介于0-1。其意义为：如果查询中连续nq次的查询结果有超过？啄的部分的重复记录，那么就表明采样结束。一般将nq设置为5-10，而？啄为5%-15%。
　　2.7样本偏差的修正
　　在实际的取样中所获得的RL作为样本一般具有较大的偏差，为此需要采取措施对偏差加以修正。由于在WDB的结果页面中会给出一个满足当前记录查询的记录数量的统计数字，为此我们记录采样中的所有的Q{Q1，Q2……，Qm}，同时为每个查询记录其结果数量。然后逐渐的对RL删减，从而使得Q如果作为随机查询集合就会通过下面公示得到的偏差尽可能小。
　　当然，这一采样方法并非完美，还需要后续工作者进一步的进行晚上、升级。首先采样中设置的一系列参数仅仅是经验性的，为此需要进行理论分析；其次上面对于采样代价的评估仅仅是通过对Web数据库的访问次数来进行衡量，为此更为合理的评估方法有待进一步开发；最后这一采样方法在多种数据库的试验还需要进行，从而不断地完善、改进，进一步的降低样本的偏差。

3结束语
　　当下随着DeepWeb的快速发展，DeepWeb已经逐渐成为数据集成领域的重要研究课题。鉴于Web数据库仅能借助于特定的查询方式进行接口访问，而且数据库数量巨大，为此需要通过对Web数据库的采样来了解其内容特征。基于以上研究文章提出了一种增量式的Web数据库采用方法，即WDB-Sample，这一采样方法通过将上述的Web数据库转化为图形来予以表示，从而达到了对增量的采样。由于这种采样方法在查询中不受属性表达形式的限制，为此在实际应用中可以在较小代价下得到高质量的样本。

参考文献
　　[1]LawrenceS，GilesC.SearchingtheWorldWideWeb.Science，1998，5360（280）：98.