用基于小波的压缩直方图实现二维谓词选择率估计的方法

摘要

本发明涉及用基于小波的压缩直方图实现二维谓词选择率估计的方法。方法分为对数据库中的数据进行统计和选择率估计两个阶段，其中：第一阶段包括以下步骤：1)数据采样，2)提取最频繁值，3)构造数据分布矩阵，4)小波分解，5)滤波存储，第二阶段包括以下步骤：6)重构数据分布矩阵，7)选择率估计。本发明使用小波技术对原始的数据分布矩阵进行有损压缩，从而使得二维数据的联合分布存储成为可能，在使用时，再将压缩过的数据分布矩阵恢复，从而进行二维选择率的估计。并且，本发明在小波分解前提取了最频繁值进行单独存储，因此使用小波技术压缩的数据损失被大大降低。本发明是一种时间换空间的方法，在不增加巨大时间开销的前提下，使用较少的存储空间保存了二维数据的联合分布，从而为二维查询提供准确的选择率估计。

主权项

1.一种用基于小波的压缩直方图实现二维谓词选择率估计的方法，其特征在于：它分为两个阶段，第一阶段是对数据库中的数据进行统计，第二阶段是用户查询时的选择率估计，其中：第一阶段包括以下步骤：1)数据采样对待创建二维统计信息的关系进行随机采样，并获取二维统计信息所涉及的属性的属性值，从而构成创建统计信息所基于的二维数据集合，2)提取最频繁值计算二维数据集中的所有不同数据的数目和每一个数据出现的次数，将出现次数超过平均次数的数据作为二维最频繁值单独存储在统计信息中，其余的数据作为下一步骤中的数据分布矩阵的输入，3)构造数据分布矩阵构造一个用来存储数据的分布特征的整型矩阵，矩阵的每一维代表数据库属性的一维，矩阵的大小视每一维的数据分布范围而定，对步骤2)输入的数据逐条按照各维的属性值所在的坐标区域进行分发，确定矩阵的每一个坐标区域的数据分布量，4)小波分解对步骤3)中构造的数据分布矩阵，按每一维顺序进行Haar小波分解，得到一个新的矩阵，5)滤波存储对小波分解后得到的矩阵进行过滤，按照数据库的存储能力选取若干个绝对值最大的小波系数，记录该小波系数的值和该小波系数在数据分布矩阵中的坐标位置，它们和步骤2)提取的最频繁值一起构成了基于小波的压缩直方图，将压缩直方图及其必要的标识信息一起作为统计信息存储，第二阶段包括以下步骤：6)重构数据分布矩阵当用户提交一条查询语句的时候，首先按照统计信息的标识信息查找与查询语句所涉及的属性相匹配的统计信息，然后按照Haar小波分解过程的逆过程对存储的统计信息进行逆分解，重构出数据分布矩阵，7)选择率估计当得到一个多维范围查询语句之后，首先从重构的数据分布矩阵中计算符合该查询条件的选择率，然后计算最频繁值中符合查询条件的选择率，查询语句的选择率就等于这两个选择率之和。