基于粗集约简的索引枚举选择方法

An enumerating method for index selection based on rough sets ruduct

依据可索引列构造原子配置及其候选空间,针对候选配置提出了一种基于粗集约简的分层估算方法.首先通过对关系型联机分析的查询执行语法分析,生成索引集的原子配置,使得其中的索引列均被高代价算子访问.然后利用约简迭代构造彼此不可替代的索引集,以有效缩减待考察空间.最后基于索引的数量约束,使用枚举代价估算消除了当前层中代价最大的索引.利用约简的特性,该方法在保证索引有效性的前提下,有效降低了代价估算的复杂度.实验验证在付出中等规模的估算代价后,约简分层的枚举方法显著提高了枚举估算的效率.

In terms of indexable columns, this paper generates the atomic configurations and its candidate space, and proposes a hierarchical filtering method for the candidate configurations based on rough sets reduct. Firstly, based on the queries parsing of the relational on-line analytical processing （ROLAP）, it generates the atomic configuration of the index set such that each index in this set can be utilized by the weighty operator. After this, the reduet based hierarchical candidate can produce the irreplaceable minimal index set. Due to the non-exchangeability of the candidate indexes produced by the reduct, the evaluated complexity decreases sharply. The experiment proves that this method exhibits a remarkable improvement of the index validity with a moderate executive cost, especially when I~ the query set is very large.