一种基于自适应遗传算法的物化视图选择方法

摘要

本发明公开了一种基于自适应遗传算法的物化视图选择方法，本发明输入带视图大小及访问频率属性的基于同一个事实表及其维表的候选物化视图集，按照映射规则将其映射到多维数据格中的节点，构建多维数据格模型并定义其下的物化视图的开销模型，然后利用二进制编码将基于多维数据格模型的候选物化视图集转换成遗传算法可以处理的0-1整型数组，最后引入自适应调整交叉概率和变异概率的机制来改进遗传算法，并利用改进的遗传算法求解物化视图选择问题，在求解大规模物化视图选择问题时，与没有采用自适应机制的遗传算法及采用贪心策略的传统算法相比，采用本发明所述的方法所得的结果较优，可以选择合适的视图进行物化，最小化物化视图的总开销。

主权项

1.一种基于自适应遗传算法的物化视图选择方法，其特征在于，该方法具体包括以下步骤：步骤(1)：输入带视图大小及访问频率属性的基于同一个事实表及其维表的候选物化视图集，根据候选物化视图SQL定义语句中group-by子句所包含的分组属性，按照映射规则将其映射到多维数据格中的节点；映射规则定义如下：SQL定义语句中包含分组属性最多的视图对应于多维数据格中的根节点，对于候选物化视图集中的任意两个视图，两个视图分别设为a和b，如果a视图SQL定义语句中包含的分组属性是b视图SQL定义语句中包含的分组属性的真子集，那么a视图所对应的节点是b视图所对应节点的子节点，多维数据格模型中，除根节点没有父节点外，其它的节点有且仅有一个直接父节点；步骤(2)：计算多维数据格模型下的物化视图的总开销；设Q为多维数据格模型中所有待物化的候选视图集，q为Q中的一个视图，f_q(q)表示q所对应的查询频率，M为物化视图集，QueryCost(Q,M)为物化视图的查询开销，MaintenanceCost(M)为物化视图的维护开销，Storage(M)为物化视图的存储开销，TotalCost(Q,M)为物化视图的总开销，avg_q∈Q{f_q(q)}为视图查询频率的均值，α为比例系数，TotalCost(Q,M)=QueryCost(Q,M)+α×(MaintenanceCost(M)+Storage(M))，其中α=0.5×avg_q∈Q{f_q(q)}；步骤(3)：利用二进制编码将基于多维数据格模型的候选物化视图集转换成遗传算法可以处理的0-1整型数组，并将步骤(2)所得的物化视图总开销的倒数作为遗传算法中个体适应度的大小；多维数据格模型中节点的编号对应于数组的索引，数组元素的值决定是否对视图进行物化，数组元素为1表示该元素索引所对应节点的视图需要物化，数组元素为0表示该元素索引所对应节点的视图不需要物化；步骤(4)：设定初始种群规模n、最大迭代次数max_number，根据步骤(3)所得的0-1整型数组，利用随机算法产生n个个体作为初始种群；步骤(5)：进行选择操作，通过筛选保留种群中适应度高的个体，淘汰种群中适应度低的个体；设Population为种群，k为种群中的个体，Fit(x)为个体x所对应的适应度，则个体x被选择进入下一代的概率p_s的计算函数如下所示：$p_s=\frac{\mathrm{Fit}\left(x\right)}{\underset{k\in \mathrm{Population}}{\Sigma }\mathrm{Fit}\left(k\right)}$步骤(6)：计算交叉概率p_c，为种群中的每个个体随机生成一个0到1之间的判定值flag_c,如果flag_c的值小于等于p_c，则该个体要进行两点交叉操作，否则该个体不用进行两点交叉操作，p_c的计算公式如下所示：$p_c=\left\{\begin{array}{cc}1-1.2\times {\mathrm{Fit}}_{\mathrm{avg}}/({\mathrm{Fit}}_{\max }+{\mathrm{Fit}}_{\min })& 0<{\mathrm{Fit}}_{\mathrm{avg}}/({\mathrm{Fit}}_{\max }+{\mathrm{Fit}}_{\min })<0.5\\ 0.4& \mathrm{else}\end{array}\right.$Fit_max为种群中个体的最大适应度，Fit_min为种群中个体的最小适应度，Fit_avg为种群中个体的平均适应度；两点交叉操作的过程如下：为两个要进行交叉操作的个体随机设置两个不同的交叉点，两个交叉点分别设为point1和point2，将两个个体point1和point2之间的基因码进行交换产生新的个体；步骤(7)：计算交叉概率p_m，为种群中的每个个体随机生成一个0到1之间的判定值flag_m,如果flag_m的值小于等于p_m，则该个体要进行变异操作，否则该个体不用进行变异操作，p_m的计算公式如下所示：$p_m=\left\{\begin{array}{cc}0.1& {\mathrm{Fit}}_{\mathrm{avg}}/({\mathrm{Fit}}_{\max }+{\mathrm{Fit}}_{\min })>0.5\\ 0.2\times {\mathrm{Fit}}_{\mathrm{avg}}/({\mathrm{Fit}}_{\max }+{\mathrm{Fit}}_{\min })& \mathrm{else}\end{array}\right.$变异操作的过程如下：为要进行变异操作的个体随机确定一个基因位，如果基因位上元素的值为0则将其变为1，如果基因位上元素的值为1则将其变为0；步骤(8)：重复步骤(5)、(6)、(7)，至迭代次数达到步骤(4)所设定的最大迭代次数max_number，最终代种群中适应度最大的个体就是要求的最优解，将其解码后输出就是要选择进行物化的视图集。