? 如果是a i分类属性,则v rj=v i.
1.3 样本偏差评价方法
由于只能通过具有特定查询能力的查询接口来获取WDB中的记录,因此在理论上是无法保证S真正的客观性的.直觉上,如果S具有真正的随机性,则对于任何一个查询Q i,必然满足下面的关系:
|()|||
|()|||
i
S i
R Q WDB
R Q S
≈.
为了能够客观地评价S的质量,我们需要一组随机的查询RandomQ{Q1,Q2,…,Q n},分别在WDB和S中进行查询,通过比较同一查询下各自查询结果的数量,得到对样本偏差的一个评价,我们给出形式化的公式:
()
Quality S=
S为空无意义,因此,|S|>0;另外,如果R S(Q i)为空,则为其赋一个足够小的值来代替.
184
Journal of Software 软件学报 V ol.19, No.2, February 2008 通过公式(1)我们可以看出,对于一个WDB 的样本集合S ,Quality (S )越趋近于0,表示该样本记录集合的偏差越小;反之,Quality (S )越大,表示样本记录集合偏差越大,客观性越低.
不可否认的是,通过公式(1)对S 的评价结果与RandomQ 有直接的关系.极端情况下,如果对于每个查询Q i , WDB 只返回一个记录,那么样本记录集合将返回0个或1个记录,这会使偶然性增大.因此,在实验部分我们将介绍如何产生随机的查询.
1.4 采样代价
除了保证样本集合S 的质量以外,另一个关键问题是采样的代价Cost (S ).在本文中,我们简单地把它定义为获得S 通过查询接口向WDB 提交查询的次数.这是因为一般情况下,本地的执行时间远小于Web 中的网络数据传输时间,由于WDB 的自主性,无法用一个常量来表示每次查询的执行时间,所以我们以向WDB 提交查询的次数来代替.文献[14,15]也都采用相同的代价估算方法.
需要注意的是,在现实中,WDB 经常因返回查询结果的记录数量较多而分多次提供给用户,即在结果页面中每次只返回k 个记录,如果用户想得到后续的记录,则必须通过翻页得到,这就相当于发送一次查询请求.比如,从Amazon 查询有关“Java”的图书,共得到46 979个记录,每次只返回用户12个记录,用户如果要看到更多的结果,就要通过不断地翻页来实现,而每次翻页就相当于向Amazon 发送了一次查询请求.
实际上,样本质量和采样代价是矛盾的:如果为了提高样本质量,必然要提交更多的查询来获得更多的记录,就会使采样代价提高.正如前面已经提到过的,针对这个矛盾,本文的目的是如何以尽可能小的代价来获得尽可能高质量的样本.
2 一种Web 数据库图模型
本节我们提出一种新的Web 数据库图模型,通过该模型我们以图游历方式达到对Web 数据库采样的目的.我们首先提出若干相关定义、性质和定理,然后对这种Web 数据库图模型进行深入讨论.
定义1(强查询). 对于两个查询Q 1和Q 2,如果A (Q 1)?A (Q 2),且对于?a i ∈A (Q 2)满足下面3个条件,那么,我们称Q 1是Q 2的一个强查询:
? 如果是a i 关键词属性,则Q 1在a i 上的值是Q 2在a i 上值的超集;
? 如果是a i 范围属性,则Q 1在a i 上的取值范围是Q 2在a i 上的子范围;
? 如果是a i 分类属性,则Q 1在a i 上的值等于Q 2在a i 上的值.
例:表3给出3个关于图书的查询示例,其中涉及了文本(书名)、数字(价格)和分类(类别)3类属性.Q 1分别是Q 2和Q 3的强查询.
Table 3 Examples of strong query
表3 强查询示例
Title Price Category
Q 1 Thinking in Java ?30,40?
Computer Q 2 Thinking in Java Null Null
Q 3 Java ?20,50?
Computer 根据定义1,我们可以得到下面两个性质:
性质1(包含性). 如果Q 1是Q 2的强查询,那么R (Q 1)?R (Q 2).
证明:?记录1i Q R R ∈,对于属性a j ∈A (R i )∩A (Q 2)的值v j 分别作如下考虑:
? 如果a j 是关键词属性,则由于v j 是Q 1在a i 上的值的超集,而Q 1在a i 上的值是Q 2在a i 上值的超集,所以v j 与Q 2在a i 上的值的交集不为空;
? 如果a j 是范围属性,则v j 必然在Q 1在a i 上的取值范围内,而Q 1在a i 上的取值范围是Q 2在a i 上的子范围,v j 在Q 2在a i 上的取值范围内;
? 如果a j 是分类属性,则v j 等于Q 1在a i 上的值,而Q 1在a i 上的值等于Q 2在a i 上的值,所以v j 等于Q 1在
刘伟等:一种基于图模型的Web数据库采样方法185
a i上的值.
从以上3个方面可以得出,R i必然满足Q2,即R(Q1)?R(Q2). □性质2(传递性). 如果Q1是Q2的强查询,而Q2是Q3的强查询,那么Q1必然是Q3的强查询.
证明:根据定义1,A(Q1)?A(Q2)?A(Q3).对于属性a j∈S(Q1)分别作如下考虑:
? 如果a j是关键词属性,Q1在a i上的值是Q2在a i上值的超集,而Q2在a i上的值是Q3在a i上值的子集,则Q1在a i上的值是Q3在a i上值的超集;
? 如果a j是范围属性,Q1在a i上的取值范围是Q2在a i上的子范围,而Q2在a i上的取值范围是Q3在a i 上的子范围,则Q1在a i上的取值范围是Q3在a i上的子范围;
? 如果a j是分类属性,Q1在a i上的值等于Q2在a i上的值,而Q2在a i上的值等于Q3在a i上的值,则Q1在
a i上的值等于Q3在a i上的值.
从以上3个方面可以得出,Q1必然是Q3的强查询. □定义2(弱查询). 如果Q1是Q2的一个强查询,那么Q2是Q1的一个弱查询.
根据定义2,我们同样可以得到与上面两个性质类似的性质,这里不再赘述和证明.
定义3(查询相关记录). 给定一个记录集合{R1,R2,…,R n},如果通过提交某一个查询Q,使得它们可以同时出现在同一个查询结果中,则称它们彼此是关于查询Q相关的;反之,则称它们是非查询相关的.
例:设一个WDB的查询接口可以根据图书的名称、作者和类别3个属性进行查询.表4给出了3个记录,其中,R1和R2可以通过作者属性同时查询出来,而R3则不能通过任何查询与R1或R2同时出现在同一查询结果集中,因此,我们说R1和R2是查询相关的,而R3与R1或R2是查询不相关的.通过这个例子也可以看出,两个记录是否查询相关,与查询接口的表达能力是密切相关的,如果查询接口中有出版社的属性,而R3与R1又恰好是同一出版社出版的,那么它们就是查询相关的了.
Table 4Examples of query-related records
表4查询相关记录示例
Title Author
Catrgory
1
R2Thinking in C++ Bruce Eckel Computer
potter J.K. Rowing Novel
R3 Harry
定理1. 给定一个查询相关的记录集合R{R1,R2,…,R n},设Q{Q1,Q2,…,Q m}为R所有相关查询的集合.如果Q 非空,那么必然存在一个查询Q i(1≤i≤m)是这个集合中其他任意一个查询Q j(1≤j≤m,j≠i)的强查询.我们把Q i称作记录集合R的最强查询.
证明:证明分为两步:首先构造一个特定的查询Q i(1≤i≤m),然后证明该查询为Q中的其他任意一个查询Q j(1≤j≤m,j≠i)的强查询.
第1步,构造查询Q i:需要确定Q i中有哪些属性以及每个属性上的取值.
对于?a k∈A(IR),考虑如下:
? 如果a k是关键词属性,并且其中各个记录在a k上的取值有非空的交集,则Q i包含a k,并且在a k上的取值为各个记录在a k上的取值的交集;如果交集为空,则Q i不包含a k.
? 如果a k是范围属性,则Q i包含a k,并且Q i在a k上的取值范围介于R中记录在a k上取值的最大值和最小值之间.
? 如果a k是分类属性,如果R中各个记录在a k上的取值相同,则Q i包含a k,并且Q1在a k上也取该值;否则,Q i 不包含a k.
第2步,证明Q i(1≤i≤m)是这个集合中其他任意一个查询Q j(1≤j≤m,j≠i)的强查询.
对于?a k∈A(Q j)作如下考虑:
? 如果a k是关键词属性,则Q j在a k上的所有关键词必然出现在R中每一个记录在a k上的值中,所以也必然出现在Q i在a k上的关键词集合中;
186 Journal of Software软件学报 V ol.19, No.2, February 2008
? 如果a k是范围属性,则R中每一个记录在a k上的值必然在Q j于a k上的取值范围内,所以,Q i在a k上的取值范围是Q j在a k上的子范围;
? 如果a k是分类属性,则R中每一个记录在a k上的值必然等于Q j在a k上的取值,所以,Q i在a k上的取值等于Q j在a k上的取值.
因此,根据定义1,Q i是Q j的强查询.进而定理得证. □定义4(Web数据库图模型(Web database graph,简称WG). 对于一个给定的WDB,它的图模型表示为WG(V,E).其中,V是顶点的集合,每个顶点v i都与WDB的记录R i一一对应,即|V|=|WDB|.E是无向边的集合,如果两个记录是查询相关的,那么,它们对应的顶点之间存在一条相连的边.对于每一个顶点,附加对应记录的最强查询;对于每一条边,附加的查询为该边所连接的两个顶点对应记录的最强查询.
在该图模型中,每个顶点和每条边都附加了一个唯一的查询,查询的生成方法在定理1中已经给出.对于每个顶点,相当于记录集合R中只有顶点对应的那个记录;对于每条边,相当于记录集合R中只有该边所连接的两个顶点对应的记录.
需要指出的是,WG是与WDB所提供的查询接口的查询能力密切相关的,因为前面我们已经指出,本文中涉及的查询都是查询接口中可表达的.因此,两个记录在WG中是否存在一条边,取决于是否存在一个查询接口可表达的查询使得这两个记录同时满足该查询.进一步来说,顶点和边上附加的查询也同样由查询接口的表达能力所决定.因此,对于两个具有相同内容的WDB,如果它们的查询接口在查询能力上不同,那么所产生的WG也是不同的.实际上,已经有一些工作通过把一个数据库转化成图的形式去解决特定的问题,我们将在相关工作中进行简要的介绍.
3 基于WG的Web数据库采样方法
利用图模型WG可以把任意一个WDB在记录层次上转化为图的表示.我们可以从图中揭示出记录之间在查询上的关联关系.前面我们已经简要介绍了对WDB增量式的采样方法(如图2所示),并给出了需要解决的3个问题:样本的选取、查询的选择和终止条件.这一节,我们将详细讨论如何在WG中采用图游历的思想来实现对WDB增量式的采样.
由于我们无法越过查询接口直接得到WDB中的所有记录,因此也无法为一个给定的WDB建立真正的WG.实际上,我们也并非有意为要采样的WDB建立一个完整的WG,而是从当前WG中一个随机的点开始进行游历,实现对WDB的采样.基于WG,采样过程的基本思想重新描述如下:
? 第1步,从任意一个查询Q0开始,并提交给WDB;
? 第2步,把查询结果中的记录保存在本地中R L,对当前已经保存下来的记录R L建立WG L;
? 第3步,判断是否达到终止条件:如果是,则终止,否则进入下一步;
? 第4步,通过对当前WG L的分析,从R L中选取一个合适的记录形成下一次的查询,转第1步.
在第1步中,我们使用任意的查询Q0作为采样的开始,虽然Q0是通过人工产生,不可避免地带有主观性,但人工选择时只要保证Q0的查询结果足够多,比如大于100,就保证了Q0是WG中度较大的一个点,从而可以避免不同初始查询带来的采样差异.
在第2步中,随着R L中保存记录数量的不断增多,WG L也在不断地扩大(加入新的顶点和边),因此,我们对WG L采取增量式的维护方式,即把每次查询返回的记录添加到当前的WG L中,而不是每次对当前的R L重新构建WG L.显然,WG L是WG的一个子图.对WG L的扩展,根据定义4很容易实现,这里就不再过多地介绍.
采样过程中最关键的步骤是第3步和第4步,共包括3个问题(在本文开始部分提到的3个问题):
(1) 如何根据WG L从当前的样本记录集合中选取一个合适的记录?
(2) 被选中的记录应该生成什么样的查询?
(3) 这个采样过程在什么情况下结束?
下面,我们首先根据基本思想形式化地给出WDB-Sampler的算法描述,然后针对上面的问题提出解决
刘伟 等:一种基于图模型的Web 数据库采样方法
187 策略.
3.1 WDB-Sampler 算法 WDB-Sampler 算法是对采样过程形式化的描述(如图4所示),其思想前面已经给出,这里不再重复.其中有一点需要说明的是:对每次的查询结果,我们只获取第1页中的记录.这是因为我们基于如下两点考虑:第一,前面已经提到,要获取此次查询结果中更多的记录需要不断翻页,而翻页操作实际上相当于一次查询;第二,所有查询结果都是满足此次查询的,因此根据公式(1),会导致偏差急剧增大.
Algorithm WDB-Sampler
Input R 0: A record in WDB . Output s
S {R 0,R 1,…,R n }: A set of records, which are sample from WDB . Begin e
te L
initialize WG L ; // the initial WG L is empty initialize R L ; // the initial R L is empty, and it is us d to store the records obtained with each query add R 0 to R L ; WG L =buildGraph (R 0); //build WG L with only one node R 0 while StopCriteria is not reached do
v c =recordSelector (WG L ); //select an appropria node (record) v c from WG L to generate the next query
Q c =queryGenerator (v c ); //generate the query Q c with the selected record v c R c =queryWDB (Q c ); //query WDB with Q c and then obtain the top-k records from the first result page
Add R c to R L ; //input R c into R and remove the duplicated records
WG L =graphExpanding (WG L ); //expand WG according to the fresh records
end S =amendDeviation (R L );
return S ; End Fig.4 WDB-Sampler: Web database sampling algorithm
图4 WDB-Sampler:Web 数据库采样算法
算法中recordSelector,queryGenerator 和StopCriteria 分别对应着本节开始所提出的3个问题,它们也是该算法的关键.本节的剩余部分将对它们逐一进行讨论.
3.2 记录的选择(recordSelector )
为了产生下一次的查询,我们需要从当前保存在本地的记录集合中选取一个合适的记录作为查询,这就是recordSelector 所要完成的功能.我们选择记录的目的是为了能让其产生的查询得到更多新的记录.从WG 的角度来看,就是从当前WG L 中选取一个顶点v ,使得通过v 可以找到更多的不在WG L 中的顶点.因此,我们的选择方案是:把WG L 中的顶点按照它们的度从低到高排序,选取度最小的顶点.WG L 中顶点的度小,这有两种可能:在WG 中有很多与其邻接的顶点(新的记录)还没有访问到,或者该顶点在WG 中的度也小.因此,如果该顶点生成的查询获得记录数量小于k ,则丢弃该顶点并重新选择剩余顶点中度最小的.
3.3 查询的生成(queryGenerator )
当选定WG L 中的一个顶点后,即从中选定了一个记录R c ,下一步就是queryGenerator 如何利用这个记录生成下一次的查询.显然,一个记录可以生成若干可能的查询.为了得到更多新的记录,对于每一个a i ∈A (IR ),我们根据R L 中的记录为其建立如下的统计信息:
? 如果a k 是关键词属性,则统计R L 中的记录所有出现的关键词及它们各自的出现频率;
? 如果a k 是范围属性,则为其建立一个数轴,将R L 中的记录在该属性上的值映射到这个数轴上;
? 如果a k 是分类属性,则统计R L 中的记录在该属性上各个分类取值的频率.
基于这些统计信息,由当前选定记录R c 生成查询Q c 的规则是:
? 对于Q c 中的关键词属性,我们首先统计:(1) R c 在该属性上的关键词;(2) 在WG L 中与R c 相邻记录在该
188
Journal of Software 软件学报 V ol.19, No.2, February 2008 属性上的关键词及频率.如果R c 中关键词不出现在它的相邻记录中,那么从这些关键词中选择在R L 中出现频率最低的那一个;否则,选择在它的相邻记录中出现频率最低的那一个.
? 对于Q c 中的范围属性,预定义一个区间长度δ,选择这样一个取值范围:长度为δ,且使得在这个范围中,在WG L 中与R c 相邻记录中出现得最少.
? 对于Q c 中的分类属性,选择在WG L 中与R c 相邻记录在属性上出现频率最低的那个取值.
3.4 采样过程的终止(StopCriteria )
如果没有终止条件,采样过程可以一直进行下去,在理论上可以得到WDB 中所有的记录,但这并非我们的目的.我们的目的是得到足够可以作为样本的记录.直觉上,如果连续多次使得每次查询结果中总有一定比例的记录与R L 中的记录重复,那么我们可以认为已经游历到了WG 中的大部分空间中.因此,我们设定两个常量n q 和σ,n q 是一个大于1的自然数,σ是一个0~1的百分比,其意义表示,如果连续n q 次每次查询结果中总有超过σ比例的重复记录,那么采样过程就会终止.通常,n q 设为5~10之间,σ设为5%~15%.
3.5 样本偏差的修正
事实上,如果我们把当前获得的R L 作为样本,一般会有较大的偏差(公式(1)).因此,我们需要采取措施来修正偏差.根据我们的观察,通常WDB 在结果页面中会给出一个统计数字来表示满足当前查询的记录数量.因此,我们保存采样过程中的所有Q {Q 1,Q 2,…,Q m },同时为每个查询时记录查询结果的数量.
1|||()||()|
|||()|()|()|m L j
j L j L
i i L i R R Q R Q R R Q Deviation Q R Q m ==?∑ (2)
我们进行样本偏差修正的基本思想是:通过对R L 逐步地删减,使得Q 如果作为随机查询集合,则利用公 式(1)得到的偏差尽可能地小.修正的过程描述如下:
第1步,我们利用公式(2)对每一个查询Q i 作偏差估计,得到偏差的最大的查询Q max ;
第2步,如果Deviation (Q max )小于设定的值ε,终止,当前的为可用样本;否则,用Q max 查询R L ,得到所有满足的记录;
第3步,对这些记录统计它们各自在Q 中可满足查询的数量(不包括Q d ),设R min 为可满足查询的数量最少的记录;
第4步,从R L 中将R min 移除,同时从WG L 中将相应顶点移除,转第1步.
从上面的描述可知,该过程是离线完成的(即不需要与WDB 有任何的交互),可以从WDB-Sampler 算法中分离出来,选择一个合适的时机完成.因此,即使因R L 数量大,造成修正代价较高,也不会对采样的代价造成影响. 4 实 验
为了客观评估Web 数据库采样方法,我们根据WDB-Sampler 算法实现了一个原型,并在本地模拟的Web 数据库以及真实的Web 数据库上进行了验证.下面首先介绍实验中使用的数据集,然后给出实验结果及相应的分析.
4.1 数据集
在本实验部分,我们使用两种数据集:一个本地模拟Web 数据库和两个真实Web 数据库.下面对它们分别进行简要介绍.
4.1.1 本地模拟Web 数据库
工作通(JobTong):招聘信息集成数据库,它集成了从当前国内流行的招聘网站(智联招聘、中华人才网、前程无忧网、易才等)爬取下来的招聘信息.尽管我们把它看作模拟实验数据,其中的数据全部是从现实的WDB 获取的真实信息.我们使用了它在2007年7月15日之前的备份数据库,共存储了982 951条记录.我们手工为其设计了一个虚拟的查询接口:职位名称(关键词属性)、公司名称(关键词属性)、薪水要求(范围属性)、学历要
刘伟等:一种基于图模型的Web数据库采样方法189
求(分类属性).
4.1.2 真实Web数据库
当当网(https://www.wendangku.net/doc/1313498040.html,/):大型电子商务网站,尽管它提供各种商品的在线销售,我们只关注其中主要的图书记录.它不但提供了图书的高级查询接口(https://www.wendangku.net/doc/1313498040.html,/book_search.html),可以在书名(关键词属性)、译作者(关键词属性)、出版社(关键词属性)、价格(范围属性)、出版时间(范围属性)上进行查询,而且还提供了图书的分类链接(https://www.wendangku.net/doc/1313498040.html,/zhuanti2006/book/2001.shtml).利用图书的分类链接,我们可以获得每个分类的数量,从估算出到全部图书的近似总数为62万.由于许多图书同时属于多个分类,因此,这一数字并不十分准确,仅作为参考.
中国图书网(https://www.wendangku.net/doc/1313498040.html,/):大型电子商务网站,只出售图书.它提供了高级查询接口(http:// https://www.wendangku.net/doc/1313498040.html,/book_find/advancedFind.asp),可以在书名、作者、出版社、出版时间上进行查询.在其主页中宣称共有图书58万种,我们用它作为该网站图书记录总数.
4.2 随机查询生成
前面我们已经给出评估样本质量的标准(公式(1)),但需要一组查询分别在样本记录集合S和Web数据库上执行.查询的随机性对样本偏差的计算有直接的影响,而且查询的数量也要足够大,这样才能保证样本偏差与实际情况相符.基于这种考虑,我们提出一种简单的查询自动生成方法来代替人工生成查询.这种方法利用已经存储在本地的样本记录来生成:首先从样本记录中随机选取一个,然后再从该记录中随机选取一个属性值作为查询.从生成方法可以看出,这与前面所提出的方法存在根本的不同:前者要求返回结果数量尽可能地多,这样可以避免偶然性的发生.
另外,为了进一步保证偏差评估的客观性,在随即查询生成的过程中,我们丢弃了重复的查询和在采样过程中用过的查询.
4.3 实验结果及分析
下面分别给出在本地模拟Web数据库和真实Web数据库上的实验结果,并同时对结果进行分析讨论.
4.3.1 本地模拟Web数据库
本节所做实验在本地工作通数据库进行,相应的参数设置为n q=7,σ=15%.为了模拟的真实性,我们在采样过程中每次获取查询结果的top-k个记录,同时为了验证k(一个Web数据库每页最多可显示的记录数量)与样本质量的关系,分别赋予k不同的值在此前提下进行采样得到下面的统计数据.
(1) 样本质量分析
我们分别随机生成100,200和500个查询对表5中展示的4次采样(最终样本)作偏差分析,得到图5所示的结果.
Table 5Statistics on local simulating Web databases
表5在本地模拟Web数据库上的统计数据
Total record number
k
Query
number
Obtained record
number
Distinct record
number
Sampling
ratio (%)
Sample
number 10 4 086 40 860 38 275 4.16 36 204 15 2 912 43 680 39 942 4.44 36 811 20 2 273 45 460 41 059 4.62 37 339
982 951
30 1 642 49 260 41 731 5.01 36 974
从图5中我们可以得到3个结论:第一,样本偏差总体来看较小,平均在10%左右;第二,在其他条件不变的情况下,样本偏差是与k成反比的;第三,用于检测样本偏差的随机查询的数量较少时(100)可能会使测量的偏差与实际情况背离较大,数量较大时(200和500)可以认为测量值与实际值相符.
190
l.19, No.2, February 2008 Journal of Software 软件学报 V o 16.00%
14.00%
12.00%
10.00%8.00%6.00%
4.00%
2.00%
0.00%S a m p l e b i a s
k =10 k =15 k =20 k =25
Random queries Fig.5 Local WDBs sample bias related simulation experiments
图5 本地模拟WDB 样本偏差相关实验
(2) 采样代价分析
从图6可以得出两个结论:一是随着Web 数据库每页显示的结果数量的增加,采样代价会逐渐减小;二是在k 值大于30以后,采样代价的下降趋于平缓.这首先反映出样本偏差和查询代价是成反比的;另外,我们并不能通过增长k 来无限制地降低采样代价.在现实中,一个Web 数据库的k 的大小如果是可改变的,我们就可以根据实际需要在样本偏差和查询代价之间作出权衡.
Fig.6 Relationship between k and query cost
图6 k 与查询代价的关系
4.3.2 真实Web 数据库
本节所做实验在两个真实的Web 数据库进行,分别是当当网和中国图书网,因为对真实的Web 数据库进行采样需要用Wrapper 程序从结果页面中抽取记录,复杂性要远高于本地数据库上的实验,因此,我们把相应的参数设置为n q =5,σ=5%,略小于前面的设置.其k 值的大小分别为20和10,所获得的实验数据见表6.
Table 6 Statistics on real Web databases
表6 在真实Web 数据库上的统计数据
WDB
Record number k Query number Obtained record number Distinct record number Sampling ratio (%) Sample number Dangdang
620 000 10 1 327 13 270 12 446 2.01 11 962 BooksChina 580 000 20 852 17 040 15 184 2.94 14 325
(1) 样本质量分析
我们分别随机生成100和200个查询对表6中展示的对两个Web 数据库的采样(最终样本)作偏差分析,得到图7所示的结果.
4000
3500
3000
2500
2000
1500
1000
500
04500
Q u e r y n u m b e r k 10 152030
407550
刘伟 等:一种基于图模型的191 Web 数据库采样方法
Fig.7 Real WDBs sample bias related simulation experiments
图7 真实WDB 样本偏差相关实验
从图7中我们可以得到3个结论:第一,样本偏差总体平均在20%左右,整体要高于本地的实验结果;第二,随着随即查询数量的增多,样本偏差同样会逐渐减小;第三,中国图书网的样本偏差要明显小于当当网的样本偏差.产生第1个结论的原因,一个是我们把n q 和σ设得较小,另一个是由于我们无法准确知道这两个Web 数据库的大小.第2个结论十分直接,这里不再作解释.第3个结论是由于当当网的记录总量是我们根据每个分类累加所得,而事实上分类之间存在一定的重复,因而会大于实际值;而从中国图书网可以看出,其提供的数字虽然不是确切数字,但与事实数字应该十分接近.这也说明了我们的方法需要Web 数据库大小的一个准确数字,而对Web 数据库大小的估计也是我们目前开展的工作之一.
(2) 采样代价分析
与在模拟Web 数据库上的实验结论类似,采样代价仍然与k 值成反比,这里不再赘述.
5 相关工作
随机采样技术在数据库领域已经得到了大量深入的研究[10?13],传统的数据库采样技术被用来降低从数据库获取数据的代价,其应用包括直方图的估计方法和近似处理等.然而,对Web 数据库采样的研究至今还未得到太多的关注.随着Web 的飞速发展以及Web 数据库数量的急剧增长,Web 数据库采样无论在理论上还是在应用中都成为Web 数据库集成领域中迫切需要解决的问题.
真正针对Web 数据库采样提出的工作有HIDDEN-DB-SAMPLER [14].它首先把Web 数据库简单化为一个布尔数据库,即每个属性上只能取为1或为0的布尔值,如图8(a)所示,进而把这个布尔数据库构建为一棵树模型,如图8(b)所示.树的每一层对应着一个属性,某一层上非叶节点的分支对应着该属性的一个取值,叶节点对应着Web 数据库中的一个记录.这样,对Web 数据库的一个查询可以表示为从根节点开始的一条路径,比如,通过(0,0,1)就可以到达t 1所在的节点.其采样的基本思想是:从根节点开始,由两个分支中随机选取一个向下走,直至到达一个叶节点,如果该叶节点上存在一个记录,就把该记录作为样本保存.随后,又把简单的布尔类型扩展到一般的数字和分类属性上.但它的局限性也是明显的,在本文开始部分我们已经讨论了它的局限性,这里不再 赘述.
我们需要关注的其他工作是Web 中对搜索引擎或文档数据库(text database)的采样.对搜索引擎采样的研究已经有许多工作,这里我们对近年来具有代表性的一些工作进行介绍.文献[16]提出了利用搜索引擎返回的top-k 个结果在文档集合中随机漫步(random walk)的思想,为每个样本文档附加权值来修正其偏差,从而得到近似均匀分布的样本集合.随机漫步的思想类似于本文所提出的图游历的思想,但两者的主要区别在于:搜索引擎中的文档是由一组关键词构成;而Web 数据库中的记录则是结构化的,存在非文本类型的属性.搜索引擎的采样方法也是通过向公共接口提交关键词查询来获得样本文档,查询生成的方法或者是手工产生[17],或者是利用用户的查询日志产生[18].而我们的方法则是从一个随机的查询开始,利用返回结果中的记录来产生下一次的查询.
目前,已有一些工作通过把一个数据库转化成图的形式去解决特定的问题.文献[15]为实现对Web 数据库的爬取,把数据库中的每个属性值看作图中的一个顶点,根据如下规则建立顶点之间的关联:(1) 属于同一个记25.00%20.00%15.00%10.00%
30.00%
B i a s e s t i m a t i o n 5.00%
0.00%Dangdang
Bookschina
192 Journal of Software 软件学报 V ol.19, No.2, February 2008 录;(2) 属于同一属性且值相同.该方法可以有效地实现从Web 数据库中获取大量的记录,虽然也可以作为一种增量式的采样方法,但它的目标是为了找到更多的新记录,难以保证样本的质量.文献[19]为实现在关系数据库上基于关键词的搜索,把数据库中的每个记录看作图中的一个顶点,按照记录之间外键关系建立顶点之间的关联.虽然该方法提出的图模型也是记录层次的,但由于Web 数据库是自治的,因此我们无法获得Web 数据库的模式信息,也无法根据主外键为Web 数据库建立图模型.
Fig.8 Illustration of HIDDEN-DB-SAMPLER
图8 HIDDEN-DB-SAMPLER 示例
6 结论和未来工作
随着Deep Web 的迅速发展,Deep Web 数据集成逐渐成为数据集成领域的一个热点研究问题.由于Web 数据库的数量巨大而且只能通过具有特定查询能力的查询接口进行访问,因此需要通过对Web 数据库的采样了解它们的内容特征.本文提出了一种增量式的Web 数据库采样方法WDB-Sampler,通过把一个Web 数据库转化成图来表示,达到对其进行增量采样的目的.该方法不受查询接口中属性表达形式的限制,本地模拟实验和真实Web 数据库上的实验表明,该方法可以在较小代价下获取高质量的样本.
不可否认,该工作有一些地方在未来仍然需要进一步的完善和探讨:第一,我们在采样过程中设置了若干参数,这些参数的取值是我们在实现过程中根据经验得到的,还需要在理论上进行分析;第二,对采样代价的评估目前只是通过对Web 数据库的访问次数来衡量,还需要进一步给出更合理的评估方法;第三,我们下一步将在更多的Web 数据库上开展实验,发现和改进需要完善之处,进一步降低样本的偏差.
References :
[1] Chang KCC, He B, Li CK, Patel M, Zhang Z. Structured databases on the Web: Observations and implications. SIGMOD Record,
2004,33(3):61?70.
[2] https://www.wendangku.net/doc/1313498040.html,. The deep Web: Surfacing hidden value. 2000. https://www.wendangku.net/doc/1313498040.html,
[3] He H, Meng WY, Yu C, Wu ZH. WISE-Integrator: An automatic integrator of Web search interfaces for e-commerce. In: Proc. of
the 29th Int’l Conf. on Very Large Data Bases. San Fransisco: Morgan Kaufmann Publishers, 2003. 357?368.
[4] Wu WS, Yu C, Doan AH, Meng WY. An interactive clustering-based approach to integrating source query interfaces on the deep
Web. In: Proc. of the 24th ACM SIGMOD Int’l Conf. on Management of Data. Paris: ACM Press, 2004. 95?106.
[5] Peng Q, Meng WY, He H, Yu C. WISE-Cluster: Clustering e-commerce search engines automatically. In: Proc. of the 6th ACM
Int’l Workshop on Web Information and Data Management. Washington: ACM Press, 2004. 104?111.
[6] He B, Tao T, Chang KCC. Clustering structured Web sources: A schema-based, model-differentiation approach. In: Proc. of the 9th
Int’l Conf. on Extending Database Technology. Heraklion: Springer-Verlag, 2004. 536?546.
[7] Zhao HK, Meng WY, Wu ZH, Raghavan V, Yu C. Fully automatic wrapper generation for search engines. In: Proc. of the 14th Int’l
World Wide Web Conf. Chiba: ACM Press, 2005. 66?75.
[8] Zhai YH, Liu B. Web data extraction based on partial tree alignment. In: Proc. of the 14th Int’l World Wide Web Conf. Chiba:
ACM Press, 2005. 76?85.
t 3
A 3A 2A 1t 41t 2
t 1
00000011111t 3A 3A 2A 1t 4
011t 2t 100000111101(a) (b)
刘伟 等:一种基于图模型的Web 数据库采样方法
193 [9] Chang KCC, He B, Zhang Z. Toward large scale integration: Building a MetaQuerier over databases on the Web. In: Proc. of the
2nd Int’l Conf. on Innovative Data Systems Research. Asilomar, 2005. 44?55.
[10] Chaudhuri S, Das G, Srivastava U. Effective use of block-level sampling in statistics estimation. In: Proc. of the 24th ACM
SIGMOD Int’l Conf. on Management of Data. Paris: ACM Press, 2004. 287?298.
[11] Haas PJ, Koenig CA. Bi-Level bernoulli scheme for database sampling. In: Proc. of the 24th ACM SIGMOD Int’l Conf. on
Management of Data. Paris: ACM Press, 2004. 275?286.
[12] Olken F. Random sampling from databases [Ph.D. Thesis]. Berkeley: University of California, 1993.
[13] Piatetsky-Shapiro G, Connell C. Accurate estimation of the number of tuples satisfying a condition. In: Proc. of the 4th ACM
SIGMOD Int’l Conf. on Management of Data. Boston: ACM Press, 1984. 256?276.
[14] Dasgupta A, Das G, Mannila H. A random walk approach to sampling hidden databases. In: Proc. of the 27th ACM SIGMOD Int’l
Conf. on Management of Data. Beijing: ACM Press, 2007. 629?640.
[15] Wu P, Wen JR, Liu H, Ma WY. Query selection techniques for efficient crawling of structured Web sources. In: Proc. of the 22nd
Int’l Conf. on Data Engineering. Atlanta, 2006. 47?56.
[16] Ziv B, Gurevich M. Random sampling from a search engine’s index. In: Proc. of the 15th Int’l Conf. on World Wide Web. ACM
Press, 2006. 367?376.
[17] Bradlow E, Schmittlein D. The little engines that could: Modeling the performance of World Wide Web search engines. Marketing
Science, 2000,19(1):43?62.
[18] Lawrence S, Giles C. Searching the World Wide Web. Science, 1998,5360(280):98.
[19] Bhalotia G, Hulgeri A, Nakhe C, Chakrabarti S, Sudarshan S. Keyword searching and browsing in databases using BANKS. In:
Proc. of the 18th Int’l Conf. on Data Engineering. San Jose: IEEE Computer Society, 2002. 431?440.
刘伟(1976－),男,山东聊城人,博士生,主
要研究领域为Deep Web 数据集成,Web
数据抽取. 凌妍妍(1985－),女,硕士生,主要研究领域为Deep Web 数据集成.
孟小峰(1964－),男,博士,教授,博士生导
师,CCF 高级会员,主要研究领域为Web 数
据管理,XML 数据管理,移动数据管理.
