数据仓库建设--OLAP和数据立方体技术

    OLAP工具通常使用数据立方体和多维数据模型，对汇总数据提供灵活的访问。例如：数据立方体能够存放多个数据维上的预计算的度量。用户可以提出数据上的OLAP查询，也可以以多维方式，通过诸如下钻或上卷这样的OLAP操作类探查数据。

一、数据立方体计算：基本概念

    为了提升OLAP查询效率，我们采用了完全立方体物化（预计算）与部分立方体物化。下面比较了这些策略。

1、立方体物化：完全立方体、冰山立方体、闭立方体和立方体外壳

    例如：维A、B、C和聚集度量M的3-D数据立方体。通常使用的度量包括count(),sum(),min(),max()。数据立方体是方体的格，每个方体代表一个group-by。基本方体是数据立方体中泛化程度最低的方体。泛化程度最高的方体是顶点方体。为了在数据立方体中下钻，我们从顶点方体的格向下移动；对于上卷，我们从基本方体向上移动。

    基本方体的单元是基本单元。非基本方体的单元是聚集单元。

    为了确保快速查询OLAP，有时预计算完全立方体。然而，完全立方体的计算复杂度是维数的指数，即2的n次方。如果考虑到每个维的概念分层，那么方体的个数更多。这样预计算完全立方体可能需要海量空间。尽管如此，完全立方体计算的算法仍然是重要的。单个立方体可以存放在辅助存储上，在需要时访问。或者，可以使用这样的算法计算较小的立方体，包含给定维集合的一个子集，或者某些维的可能值的一个较小的领域。在这种情况下，较小的立方体是给定维子集或维值的完全立方体。探索计算数据立方体的所有方体的可伸缩方法。这些方法必须考虑可用于计算方体的内存容量的限制、计算的数据立方体的总体大小，以及计算所需要的时间。

    部分物化提供了存储空间和OLAP响应时间之间的折中。不是计算完全立方体，而是计算数据立方体的方体的一个子集，或者计算由各种方体的单元子集组成的子立方体。

    在许多情况下，相当多的立方体空间可能被大量具有很低度量的单元所占据。这是因为立方体单元在多维空间中的分布常常是相当稀疏的。例如：一个顾客一次在一个商店可能只买少量商品。这样的事件将产生少量非空单元，而剩下其他大部分立方体单元为空。在这种情况下，仅物化其度量值大于某个最小阀值的立方体单元是有用的。例如：仅仅希望物化其sales>$100。这样能够节省时间和磁盘空间，而且还能够导致更聚焦的分析。这种部分物化的立方体称为冰山立方体。这种最小阀值称为最小支持度阀值，或简称为最小支持度。

    为了系统的压缩数据立方体，需要引入闭覆盖的概念。一个单元c是闭单元，如果不存在单元d，使得d与c的特殊化（即d通过将c中的*值用非*值替换得到），并且d与c具有相同的度量值。闭立方体是一个仅由闭单元组成的数据立方体。

    部分物化的另一种策略是只要预计算涉及少数维的方体。这些方体形成对应大的数据立方体的立方体外壳。在附加的维组合上的查询必须临时计算。例如，可以预计算n维数据立方体中具有3个或更少维的所有方体，产生大小为3的立方体外壳。然而，这仍然会计算大量的方体，特别是当n很大时。或者，可以基于方体的兴趣度，选择只预计算立方体外壳的部分或片段，这种就外壳片段方法。

二、数据立方体计算的一般策略

   一般而言，有两种基本数据结构用于存储方体。关系OLAP（ROLAP）的实现使用关系表，而多维数据组用于多维OLAP（MOLAP）。尽管ROLAP和MOLAP可能使用不同的立方体计算技术，但是某些优化“技巧”可以在不同的数据表示之间共享。

1. 排序、散列和分组。应当对维属性使用排序、散列和分组操作，以便对相关元组重新定序和聚类。在立方体计算中，对共享一组相同维值的元组进行聚集。因此，重要的是利用排序、散列和分组操作对这样的数据进行访问和分组，以便有利于聚集的计算。
2. 同时聚集和缓存中间结果。在立方体计算中，从先前计算的较低层聚集而不是从基本事实表计算较高聚集是有效的。此外，从缓存的中间计算结果同时聚集可能导致减少开销很大的磁盘I/O操作。
3. 当存在多个子女方体时，由最小的子女聚集。当存在多个子女方体时，由先前计算的最小子女方体计算父母方体通常更有效。
4. 可以使用先验剪枝方法有效地计算冰山立方体。对于数据立方体，先验性质表述如下：如果给定的单元不满足最小支持度，则该单元的后代也都不满足最小支持度。使用这种性质可以显著的降低冰山立方体的计算量。冰山立方体的说明包含一个冰山条件，它是在物化单元上的约束。通常的冰山条件是单元必须满足最小支持度阀值，如果小计数或总和。在这种情况下，可以使用先验证性质对该单元后代的探查进行剪枝。例如：如果方体单元C的计数小于最小支持度阀值v，则较低层方体中c的任何后代单元的计数都不可能高于v，因此可以被剪枝。换言之，如果某个单元c违反某条件，则c的每个后代也将违反该条件。遵守这一性质的度量称为反单调的。这种形式的剪枝在频繁模式挖掘中很流行，它也有助于数据立方体的计算，减少处理时间和磁盘空间需求。这可能导致更聚焦的分析，因为不能通过阀值的单元可能不是有趣的。

三、    数据立方体计算方法

    完全或部分数据立方体的预计算可以大幅度降低响应时间，提高联机分析处理的性能。但是，这种计算是一个挑战，因为它可能需要大量时间和存储空间。数据立方体有效计算方法有：多路数据聚焦方法、BUC方法从顶点方体向下计算冰山立方体、Star-Cubing方法，从顶向下和从底向上的计算、壳片段立方体方法，它为有效的高维OLAP计算壳片段。

1、多路数组聚集方法使用多维数组作为基本的数据结构，计算完全数据立方体。他是一种使用数组直接寻址的典型MOLAP方法，其中维值通过位置或对应数组位置的下标访问。

• 把数组划分成块。块是一个子立方体，它足够小，可以放入立方体计算时可用的内存。分块是一种把n维数组划分成小的n维快的方法，其中每个快作为一个对象存放在磁盘上。块被压缩，以避免空数组单元所导致的空间浪费。
• 通过访问立方体单元来计算聚集。可以优化访问单元的次序，使得每个单元必须重复访问的次数最小化，从而减少内存访问开销和存储开销。技巧是使用这样一种次序，使得多个方体的聚集单元可以同时计算，避免不必要的单元再次访问。
• 由于分块技术涉及重叠某些聚集计算，因此称该技术为多路数据聚集。它执行同时聚集，即同时在多个维组合上计算聚集。

2、BUC从顶点方体向下计算冰山立方体

    BUC是一种计算稀疏冰山立方体的算法。从顶点方体向下到基本方体构造冰山立方体。这使得BUC可以分担数据划分开销，这种处理次序也使得BUC在构造立方体的使用先验性质进行剪枝。 

    BUC聚集整个输入并输出结果总数。对于每个维d，输入在d上划分。由Partition()返回，dataCount包含维d的每个不同值的元组总数。d的每个不同值形成自己的分区。行8对每个分区迭代。行10检查分区的最小支持度。也就是说，如果该分区中的元组数满足最小支持度，则该分区称为递归调用BUC的输入关系，在维d+1到numDims上的划分计算冰山立方体。采用sql实现：compute cube iceberg_cube as select A,B,C,D,Count(*) from R cube by A,B,C,D having count(*) >=3。BUC是如何构造维ABC和D的冰山立方体，其中最小支持度计算为3.假设维A有4个不同值a1,a2,a3,a4；B有4个不同值b1,b2,b3,b4；C有2个不同值c1,c2；而D有2个不同值d1,d2。如果将每个分组看成一个划分，则必须计算满足最小支持度（即具有3个元素）的分组属性的每个组合。

    在搜索满足冰山条件的元组时，BUC使用先验证性质节省搜索时间。从维A的值a1开始，聚集a1分区，为a的分组创建一个元组，对应于单元（a1,*,*,*）。假设（a1,*,*,*）满足最小支持度，此时在a1的分区上进行递归调用。BUC在维B上划分a1的分区。它检查（a1,b1,*,*）的计数，看他是否满足最小支持度，并在（a1,b1，*，*）上递归，从c1开始对c上划分。建设（a1,b1,c1,*）的单元计数是2，不满足最小支持度，则它的任何后代也不能满足。因此，BUC减掉对（a1,b1,c1,*）的进一步探查。节省大量处理时间。

3、为快速高速OLAP预计算壳片段

    数据立方体有利于多维空间的快速OLAP。然而，高维完全数据立方体需要海量存储空间和不切实际的计算时间。冰山立方体提供了一个更可行的替代方案，正如我们已经看到的，冰山条件用来指定计算完全立方体单元的一个子集。然而，尽管冰山立方体比对应的完全立方体小，并且需要较少的计算时间，但是它还不是最终的解。

    第一，冰山立方体本身的计算和存储开销可能仍然很高。第二，很难确定合适的冰山阀值，该阀值设的太低将导致巨大的立方体，设置太高可能无法用于更多有意义的应用。第三、冰山立方体不能增量的更新，一旦一个聚集单元低于冰山阀值，他就被剪枝，他的度量值就丢失。任何增量更新都需从头重新计算。

     外壳片段方法遵循版联机计算策略。它涉及两个算法：一个计算外壳片段立方体，而另一个用立方体片段处理查询。外壳片段方法能够处理维度非常高的数据库，并且可以快速联机计算小的局部立方体。他利用信息检索和基于web的信息系统中很流行的倒排索引结构。其基本思想如下：给定一个高维数据集，把维划分成互不相交的维片段，把每个片段转换成排序索引表示，然后构造立方体外壳片段，并保持与立方体单元相关联的倒排索引。使用预计算的立方体外壳片段，可以联机动态的组装和计算所需要的数据立方体的方体单元。这可以通过倒排索引上的集合交操作有效的完成。