计算机应用 ›› 2009, Vol. 29 ›› Issue (12): 3296-3299.

• 数据库与数据挖掘 • 上一篇    下一篇

基于QC树的数据仓库增量维护和查询算法

陈振坤   

  1. 华南理工大学计算机科学与工程学院
  • 收稿日期:2009-06-24 修回日期:2009-08-11 发布日期:2009-12-10 出版日期:2009-12-01
  • 通讯作者: 陈振坤

Incremental maintenance and query algorithm of data warehouse based on QC-trees

CHEN Zhen-kun   

  • Received:2009-06-24 Revised:2009-08-11 Online:2009-12-10 Published:2009-12-01
  • Contact: CHEN Zhen-kun

摘要: 为使通过QC树对数据仓库进行常规的增删改操作和查询操作变得更加方便和高效,提出了QC树增量维护和有效查询的详细实现算法。该实现算法以QC树的结构为基础,结合深度优先算法和等价类的覆盖关系对QC树进行维护和查询。实现算法通过只观察等价类的上界值和考虑所有可能出现的类状态的变化情况,以确保算法的高效性和正确性。与传统的数据立方体维护和查询方法比较,新方法只需要观察等价类上界值的变化情况,较大地减少了需要考虑的数据量,有效地解决了数据量过大导致维护查询效率太低的问题。理论分析与实验结果证明了该实现算法的有效性。

关键词: 商立方体, QC树, 数据立方体, 增量维护, 点查询, 范围查询

Abstract: In order to make it more convenient and more effective to add, delete, update and query a data warehouse through QC-tree, this paper suggested how to incrementally maintain and query QC-tree. The implementation maintains and queries QC-tree based on the structure of QC-tree, combining the deep first algorithm and cover of equivalent classes. The implementation involves only the upper bound of equivalent classes and considers whatever may happen to the states of classes, so that it confirms the effectiveness and correctness. Compared with the traditional maintenance and query through data cube, the implementation dramatically cuts down the data amount to be considered, so that it improves the performance of maintenance and query.

Key words: Quotient Cube (QC), QC-tree, data cube, incremental maintenance, point query, range queries