论文部分内容阅读
联机分析处理是数据仓库所能提供的一种基本的数据分析服务,而数据立方体是实现联机分析处理的主要手段。如何高效处理数据立方体中所包含的大规模数据是数据仓库研究和应用领域的一个关键问题。本文对于数据立方体的优化研究主要集中在如何减少其存储代价、查询时间和维护(更新)时间上,以及如何在这几者之间达到较佳的平衡。
QC-Tree是近两年提出的一种数据立方体的高效存储结构。它在极大限度地压缩了数据所占用的存储空间的同时,保持了良好的更新和查询性能。本文提出了一种在QC-Tree中实现cell级别的部分物化的结构:PMC。PMC的物化算法不同于已被广泛研究的视图物化算法。在传统的视图物化算法中,一个视图中的所有cell数据要么全部被物化,要么全部不被物化。而就我们所知,PMC是第一种在cell级别进行数据的选择和物化的结构。实验表明,PMC能够进一步减少QC-Tree所占用的存储空间并拥有更少的更新代价。此外,PMC还能保证数据立方体中所有数据在查询性能上的均衡性,这是传统的视图物化算法所无法做到的。
对于多维数据的范围查询处理而言,联机聚集是一种比较合算的查询策略。然而,以前在数据立方体上实现的联机聚集往往需要附加空间来存储联机聚集估算所需要的信息,这极大地影响了整个数据立方体的存储和维护性能。本文提出了基于QC-Tree的用于范围查询处理的联机聚集算法PE及其与简单聚集算法相结合的混合聚集算法HPE。此外,本文还提出了一种能够同时处理多个范围查询的联机聚集算法MPE。与以往联机聚集算法不同的是,本文提出的算法不需要任何附加空间,而是利用QC-Tree自身保存的聚集数据和语义关系来估算聚集结果。对算法的分析表明,本文提出的算法能够同时较好地满足多维数据的范围查询处理算法的三个要求,而这是过去的算法很难做到的。实验结果也证实了这一点。
在数据仓库领域的另一个关键性问题是如何在源数据发生变化时,对数据立方体中的数据进行有效的增量更新。文中提出的DSD算法是I.S.MumickT作的延伸。与Mumick的工作不同之处在于,本文使用两种增量表来将不同类型的更新数据分开存放,进而利用所保存的更新数据的操作类型的信息,对数据立方体的更新过程进行优化。此外,DSD算法维护过程中遵循了合理的刷新顺序,因此在出现重新计算的情况下,可以使用数据的最近的物化祖先进行临时导出计算,而不是使用基表。实验结果表明,DSD算法在性能上较Mumick的算法有较大幅度的改善。
文中认为,对于更大规模的数据流数据,传统的技术已经很难将数据完整的保存在数据立方体中,只能采用近似存储和近似查询的方法处理。略图是近两年提出的一种高效的数据流近似查询处理工具。在计数-最小略图中,点查询是其它所有较复杂查询的基础。本文着重研究计数-最小略图的新的点查询估算方法,分别提出了在收款机模型和十字转门模型下更有效的查询算法,并初步证明了本文提出的算法的优越性。实验结果也证实了本文的结论。