论文部分内容阅读
随着数字时代的到来，企业积累的数据量呈爆炸性的增长。为了分析海量的历史数据，以辅助企业今后的决策，联机分析技术应运而生，一个完整的联机分析系统包括了数据仓库环境和联机分析工具。数据立方作为数据仓库中数据的组织和存储方式，以及联机分析工具的操作对象，在联机分析技术中扮演着基础和核心的角色，成为一个备受关注的研究内容。 数据立方提供了数据的一种多维视图，便于用户从多种角度考察他们感兴趣的数据。为了加快数据立方的查询响应，以提高分析效率，数据立方的实化是一种行之有效的解决方法。在数据立方领域中，实化主要研究数据立方的快速计算和计算结果的高效存储。经过计算之后，数据立方的尺寸呈指数级的增长，使得计算本身及其结果存储是非常困难的事情。围绕着数据立方的计算和存储，开展了三方面的研究工作:自底向上计算、紧凑存储以及基于语义的存储。 数据立方计算不仅用于预先计算数据立方，还可以用在联机响应聚集查询之中。在现有的各种计算方法中，最有效的是BUC算法，自底向上计算各个小方，特别适合于计算稀疏数据立方，此外，BUC算法的思想促进了数据立方领域内其它问题的研究。通过分析BUC算法，提出了“后单值”划分，单元组划分只是“后单值”划分的一种特例。在研究“后单值”划分的性质之后，设计了基于“后单值”划分的优化处理，并将其嵌入到BUC算法之中。实验结果表明，基于“后单值”划分的优化处理在多数情况下提高了BUC算法的性能，其原因是数据项之间往往存在相关性，使得BUC算法在计算过程中会产生大量的“后单值”划分。在实际数据立方中，由于维之间有比较大的相关性，大部分划分是“后单值”划分，优化处理的效果非常明显。 紧随计算而来的问题是计算结果的高效存储，在这个问题上面，紧凑立方思想是当前最为有效的解决方法，Dwarf和QC-tree是其中有较高浓缩效果的两种存储结构。在分析Dwarf的原始构造算法之后，得出其有可能构造出含后缀冗余的Dwarf。通过研究Dwarf结构，提出了关于Dwarf结构和事实表划分的三个定理，以此为基础提出了DBC算法。DBC算法通过计算数据立方来构造Dwarf，不仅可以构造真正的Dwarf，而且具有比原始算法更高的构造性能。为了进一步缩减Dwarf的存储尺寸，分别提出了融合Condensed Cube思想的浓缩Dwarf和融合冰山立方思想的冰山Dwarf，前者从Dwarf中删除了不必要的“*”项，而后者从Dwarf中删除了琐碎的路径。在分析QC-tree的原始构造算法之后，得出其构造性能很低，并且需要很大的工作主存。通过研究QC-tree结构，提出了快速构造QC-tree的OPA算法，这是一种单阶段的算法，不需要生成和处理临时类。此外，OPA算法以后序的顺序输出节点，只需配置较小的工作主存即可运行。实验结果表明，OPA算法远远优于原始构造算法。 为了捕获和表达立方元组之间的下钻语义，提出了类格，这是由类及其直接下钻关系形成的一种逻辑结构。Quotient Cube和QC-tree是类格的两种物理实现，但是它们没有从下钻语义的角度考虑存储，致使所表达的语义是隐含的和晦涩的，难以为用户理解和使用，为此，提出了下钻立方，以一种直观自然的方式实现了类格。下钻立方也是一种紧凑立方技术，但是不同于Dwarf和QC-tree:下钻立方所存储的不是原数据立方的内容，而是原数据立方蕴涵的下钻语义。在下钻立方结构中，每一个节点表示一个类，节点中的每一条边表示一个直接下钻关系。在提出下钻立方之后，设计了下钻立方的查询响应算法和构造算法:当面对一条查询时，查询响应算法从下钻立方的根节点开始，依据查询说明的元素下钻到包含查询点的所有目标节点;构造算法通过计算和处理划分，直接从事实表构造出下钻立方，从而避免了类的计算和处理。定性分析和实验结果表明Dwarf、QC-tree和下钻立方的存储尺寸和构造时间同维数目是多项式的关系，而同元组数目是几乎线性的关系。比较而言，下钻立方最有最快的查询响应速度，并且在多数情况下具有最小的存储尺寸，而Dwarf在多数情况下具有最快的构造速度。