关系数据库中近似查询的自动采样改进方法研究

李庆红

(株洲职业技术学院信息工程系，湖南株洲412001)

关系数据库中近似查询的自动采样改进方法研究

李庆红

(株洲职业技术学院信息工程系，湖南株洲412001)

海量数据的传统精确查询易导致负载过大，而通过改进数据库近似查询自动采样，预先运行样本查询，然后根据每一个元组在样本关系表中出现的次数，将每个元组需要的存储信息作为元组的属性添加进数据表中，并通过DBMS在整个自动抽样过程对它们进行管理，对所得的结果进行分类并统计，得出每次采样过程中某个元组出现的次数，实验表明方法是有效的。

关系数据库;自动采样;SQL

采用传统精确查询技术处理海量数据，查询任务将显得极其繁重，从而导致整个查询的响应时间超出用户可以接受的限度。因而往往采用近似匹配，通过对部分或采样数据的查询，而不是整个数据集本身进行的查询，此外，要完整地收集一个数据集往往不可能，现在的数据仓库多是“普遍”数据的一个样本，这在科学应用领域是极其普遍的。为了让用户了解查询结果的精度，确定正确的查询结果在某个概率区间中，需要结合查询结果的概率分布来给出置信区间，然后根据整体数据的分布情况计算出概率，对样本数据估计匹配置信区间。通过分析样本数据而推导出整个数据特征的概率分布，对数据集很可能不准确。

在实际运用中通过样本推断出整个分布非常困难，不可能预先知道数据集的标准偏差和参数分布函数，或必须处理数据的概率分布，当需要推导又推导不出产生置信区间的函数时，则需要考虑采用新的处理方法。基于仿真的置信区间不需要单独的分析推导［1－3］，使用简单的计算能力避免分析推导和参数分析，提供了一个通用技术为大多数统计方法计算置信区间。统计估计中使用较广泛的Bootstrap方法［4］能被大多数数据库使用，能够减小查询数据的范围，将查询简化到基础数据上。置信区间在一个大容量的数据集上重复运行，反复抽样基本数据库表产生仿真数据集，每一次先对基本数据表进行再抽样，再对每一个样本进行基本查询，最后再根据所有的查询结果推导出整个数据的结果。但Bootstrap方法在对大型数据进行操作时速度将随着数据量的增加而降低速度。

本文改进了数据库近似查询的自动采样，通过确定在非采样样本上的基本查询结果元组是第二次采样形成的关系集上相同查询结果的一个超元组集，预先运行样本查询，然后记住每一个元组在样本关系表中出现的次数，将每个元组需要的存储信息作为元组的属性添加进数据表中，然后通过DBMS在整个Bootstrap过程对它们进行管理，对所得的结果进行分类并统计，得出每次采样过程中某个元组出现的次数，提升了Bootstrap方法的采样效率，或者减少执行查询的次数，加快获取结果的时间，以最大限度地降低性能，使Bootstrap方法对海量数据数值类型的整个或者部分样本进行基础SQL查询即完成对关系数据库的近似查询，得到符合用户要求的近似结果信息。

1 元组信息存储

在应用Bootstrap方法进行数据的近似查询时，算法用到的大量再抽样和重复查询操作产生了大量的负载，为了降低查询负载，设法避免运行基本查询在一次以上。对于大多数关系数据库查询来说，实际上有很多种方法可以实现这个目标。考虑以下查询:

SELECT BOOTSTRAP f(R1.att1，R1.att2，...，R2.att1，R2.att2，...)

FROM Rx+1，Rx+2，...，Ry

INCOMPLETE R1，R2，...，Rx

WHERE expression(R1.att1，R1.att2，...，R2.att1，R2.att2，...)

RESAMPLE b TIMES

WHERE expression(R1.att1，R1.att2，...，R2.att1，R2.att2，...)

RESAMPLE b TIMES

假设基本查询是直接对R1和Ry关系上进行的查询，则S是f运行在这个查询上的元组的集合，换句话说，如果聚集函数f被SELECT* 语句代替以后，S将仅仅是这个查询结果的多集。假设基本查询不是直接运行于R1，R2，...，Rx，而是运用对 R1，R2，...，Rx再抽样后的集合，那么S*就被定义为f要运行元组的多集。由于R*中的元素R1*，R2*，...，Rx*分别是再抽样集合 R中样本R1，R2，...，Rx，因而 R* 必是 R 的一个元组集。因此，使 R*与任何其它的关系进行连接产生的元组集决定是R与相同关系连接产生元组集的子集。即结果集S*删除重复元组后必包含于删除重复元组后的S集。表示为S*(删除重复元组后)⊂S(删除重复元组后)。

这样可以保证在非采样样本上的基本查询结果元组是第二次采样形成的关系集上相同查询结果的一个超元组集。如果对每一个原始关系 R1，R2，...，Rx仅运行一次基本查询，那么将可以得到一个关系S，这个S包括所有在R1，R2，...，Rx的样本集上运用同样的查询得到的一系列查询结果。S的后处理将给予任何在样本中执行查询时得到的任何结果。

假定两个关系表:SUPERVISES(BOSS，EMP)和 AGE(EMP，YEARS)如下所示:

表1 关系表

使用下面的SQL查询语句估计Mr.Smith管理员工的平均年龄:

SELECT AVG(AGE)

FROM SUPERVISES，AGE

WHERE BOSS=“Mr.Smith”AND

SUPERVISES.EMP=AGE.EMP

使用这个查询，首先得到的用于计算平均年龄的S集是:

表2 基础数据查询结果

Mr.Smith管理员工的平均年龄估计结果为37.5。假设对两个关系进行重采样，如下表所示。对新生成的样本进行前面一样的查询。用于计算平均年龄的S*集元组为:

表3 再采样查询结果

平均年龄的估计值为40.2。删除了重复元组后，用于Bootstrap方法估算的元组集并未包含在取样前的任何元组中。在基础关系表上取样的过程并不能创造新的元组，而只能改变S中元组在S*中出现的次数。如果关系R的一个元组t在R*中出现了n次，那么S中的任何一个依赖于t的元组将跟一些附加因素在S* 中出现n次。(“Mr.Smith”，“Joe”)在SUPERVISES关系表的样本中出现了两次，(“Joe”，42)在AGE关系表的样本中出现2次。其结果是，元组(“Mr.Smith”，“Joe”，“Joe”，42)在 S* 中出现了4 次。

2 再抽样实现

根据上面所举的例子，就可以通过一个简单的方法来模拟重复对每一个样本表进行多次查询的过程。通过预先运行样本查询，然后记住每一个元组在样本关系表中出现的次数，这样就可以达到预期。对于任何规模的关系R即使它有可能远远大过主存容量，也可以用一个简单的算法来对其进行采样(参见算法1)。

算法1 对R进行再抽样

Vector temp=＜＞

For i=1 to|R|do产生一个1到|R|之间的随机数;将这个随机数添加到temp;

对temp进行分类排序，如果本身很大，需要用到极限分类算法;

从头到尾对temp进行浏览;对temp中的每一个i;

累计i在temp中出现的次数;

End for

然后可以使用算法1求得的次数计算S中的每个元组在每一次Bootstrap方法查询时重复出现的次数，如果运行完所有这些次数需要过多的主存空间作为缓存，而主存空间明显不够，那么就需要另外找一种比较好的的方法来处理这个问题了。目前处理该问题最简单且最高效的办法是运用一个I/O算法:将每个元组需要的存储信息作为元组的属性添加进数据表中，然后通过数据库管理系统在整个Bootstrap过程对它们进行管理。对查询结果的后期处理工作就是给出Bootstrap查询的最终结果。

上例用到的数据表，要求所有元组进行b=10次采样，且每个样本的容量即每次采样的次数n=10。运用算法1统计每一个元组在每一个样本中重复出现的次数，并按样本号进行GROUP BY分组。步骤如下:

创建 tuple_count(Tuple_id，Samp_id，Appear_count)和t_tuple(Tuple_id，Samp_id，num)，执行下列SQL存储过程:

CREATE PROCEDURE count_tuple_appear

AS

declare@i int

declare@j int

declare@samp int

set@i=1

while@i＜=10

begin

set@j=1;

while@j＜=8

begin

set@samp=1+abs(checksum(newid()))%(30)

insert into t_tuple select@samp，@i，1

set@j=@j+1

end

set@i=@i+1

end

3 再抽样分析与实验

通过上面的存储过程，就将每次采样的信息存入表t_tuple中。对t_tuple进行查询就可以得到每一次抽样过程的信息，结果如图1所示:

图1 随机抽样结果

对所得的结果进行分类并统计，即得出每次采样过程中某个元组出现的次数，这个过程可通过下面的查询过程得到，同时将结果存入到tuple_count表中，如图2所示。

Insert into tuple_count

select tuple_id，samp_id，sum(num)as appear_count from t_tuple

group by tuple_id，samp_id

图2 累计每次抽样相同元组数

接下来，需要进行基础查询，并用查询得到的结果产生一个S集，S中存储的元组将用于f聚集函数的调节。这个任务是通过DBMS查询引擎对存储在数据库中的所有数据执行查询来完成的，惟一的异常是因为numAppear数组的缘故，会增大所有不完整关系表的每个元组尺寸。这个数组被当作是元组的附加属性而贯穿于整个查询的过程中。

最后，对S进行后处理以产生Si*(1≤i≤b)。当所有的Si* 被计算出来后，就可以在所有的Si*上应用f聚集函数，然后生成Bootstrap查询的最终结果。注意到很多情况下，并不一定要将每一个Si*具体化。如果f可以计算(在许多使用普通聚集函数的情况下如AVG和SUM)，那么在计算Si*中的元组时，f的值将变化。

实验使用传统的DBMS进行查询，采用TPC－H基准［5］进行测试，DBGEN程序将比例因子(SF)作为基准参数生成TPC－H数据。使用比例因子SF=1来创建1GB数据集。选择TPC－H基准五个查询Q1、Q2、Q6、Q12进行测试。采用C++和SQLSERVER2005实现，测试环境为XP 系统、Intel Xeon 2.4 GHz、4GB 内存。

表4 查询时间比较(单位:秒)

实验得到的表4显示改进方法最终产生的负载远远小于初始查询所需抽样次数，表明提升了Bootstrap方法的采样效率，减少执行查询的次数，加快获取结果的时间。

4 结论

本文改进了数据库近似查询的自动采样，提升了Bootstrap方法的采样效率，对海量数据数值类型的整个或者部分样本进行基础SQL查询即完成对关系数据库的近似查询。虽然仅需要执行一次基础查询就能利用Bootstrap方法，但对于整个查询执行过程，海量不完整数据样本的所有元组仿真将造成巨大的性能负载。下一步的工作将进一步降低性能负载。

［1］HAAS P J，NAUGHTON J F，SESHADRI S，et al.Sampling-based estimation of the number of distinct values of an attribute［C］.Proceedings of the International Conference on Very Large Databases，1995:311－322.

［2］HASS P J，NAUGHTON J F，SESHADRI S，et al.Selectivity and cost estimation for joins based on random sampling［J］.Journal Compute System Science，1996，52(3):550 －569.

［3］ACHARTA S，GIBBONS P B，Poosala V，et al.The aqua approximate query answering system［C］.Proceedings of the ACM International Conference on Management of Data，2009:574 －576.

［4］HALL P.The bootstrap and edge worth expansion［M］.Berlin:Springer-Verlag，1995:56.

Research on Improved Method of Automatic Sampling of Approximate Question in Relational Databases

LI Qing-Hong
(Department of Information Engineering，Zhuzhou Professional and Technical College，Zhuzhou 41200，China)

Traditional accurate query of mass data is easy to lead to overload.This paper improves the bootstrap method for approximate queries.The sample query is executed in advance，according to the number of every tuple which appears in the sample relation，store information that these tuples need be added into a data table as store information，they are managed by DBMS in the whole bootstrap processing to classify and count obtained results to get the number of certain tuple which appears in every bootstrap processing.The experiment shows that the method is effective.

relational database;automatic sampling;SQL

(责任编校:光明)

TP392

A

1673－0712(2011)02－0087－04

2010－11－02.

李庆红(1967—)，女，湖南株洲人，株洲职业技术学院信息工程系讲师，硕士，研究方向:数据库。