摘要: 联机分析处理中有很多的查询要从磁盘读取大量的数据，计算复杂的函数，而联机分析处理的交互特性要求能快速的响应用户提交的查询。为了解决这对矛盾，Jim Gray于1996年提出了数据立方体(Data Cube)操作符。数据立方体概括了用户可能提出的所有的查询类型，并且将查询结果预先计算出来保存到磁盘。回答用户查询时，通过查询重写把用户的查询转换为对某一个实例化视图的查询，极大的提高了查询响应速度。数据立方体存在一个严重的缺陷：大量的计算和维护工作，巨大的磁盘存储空间，不能很好的适用于高维的场合。为了解决这个问题，到目前为止，研究工作者提出了四种解决方法：部分数据立方体，在给定的存储空间约束下或维护时间约束下，从数据立方体中选择部分视图，实例化这些视图中的所有元组，从而减少了对磁盘空间的需求，但是，查询响应时间比数据立方体要长，在某些情况下，查询过程中要实时计算聚集函数；紧凑型数据立方体，如condensed cube和quotient cube，利用元组共享原理只实例化数据立方体视图中的某些元组，对稀疏数据（实际应用中，多数都是稀疏数据）形成的数据立方体有很高的压缩比，不需要实时计算，但查询响应时间比较长；近似数据立方体，利用柱状图(histogram)和小波变换技术压缩数据立方体，得到的查询结果是近似的；特殊存储结构的数据立方体，采用R-tree或prefix tree组织数据立方体中的元组，以获得较好的查询性能并可以压缩数据立方体，如cubetrees和Dwarf，缺点是这种结构与维数关系密切，维数越大，查询性能越不好。为了改善了quotient cube的查询性能，QC-tree采用了类prefix tree结构组织quotient cube中的元组，但没有从根本上分析它的查询性能。我们使用了Ullman等人提出的线性查询代价模型分析了quotient cube的查询性能，结果表明，由于quotient cube只实例化视图中的封闭元组，其它的元组分散在其它视图中（这些视图称为视图的搜索视图集），这样，在查询中必须要检查搜索视图集中的很多视图，其查询性能远不如data cube，是一种以时间换空间的解决方案，而这有背于联机分析处理需要快速的查询响应时间的要求。我们提出了semi-closed cube，可以表示为对quotient cube的优化问题。我们提出了一个贪心算法来解决该优化问题，基本思想是：如果quotient cubed的查询代价高于某个阈值，则选择一些视图，并为每个视图选择一个伙伴，伙伴是搜索视图集中的一个视图。我们实例化这些视图中的除了被其伙伴所封闭的所有元组，显然，在查询视图中的一个元组时，只需要搜索视图和它的伙伴，查询响应时间大大缩短。对于其它的视图，我们根据封闭元组的性质调整它的搜索视图集中以得到最短的响应时间。与quotient cube相比，semi-closed cube多实例化了一些元组，但取得了接近于data cube的查询响应时间，实验结果也证明了这一点。在condensed cube中，每个视图的伙伴是基本关系表，是semi-closed cube的一种特例。因此，semi-closed cube概括了condensed cube和quotient cube。我们今后的工作是将QC-tree的索引结构用于semi-closed cube，进一步提高其查询性能。