基于同源元组的分层自索引立方组织形式

摘要

为了加速响应联机分析处理系统中的复杂多维查询，通常需要预先计算并保存数据立方。然而数据立方的巨大尺寸却给数据立方的计算和存储带来诸多难题。为了保存数据立方不得不消耗大量的存储空间；同时在计算数据立方所耗费的时间代价中，占支配地位的就是用于存储数据立方的结果集所带来的大量I/O操作。为了从根本上解决这些问题，需要探索有效的数据立方计算和组织方法。 浓缩数据立方（Condensed Data Cube）是一种有效缩小数据立方尺寸的机制，其中基本单元组的浓缩（BST Condensing）是指把那些由同一条基表元组计算聚集得到的立方元组浓缩成一条，从而减小数据立方的体积。最小基本单元组浓缩数据立方（Min-Cube）在浓缩数据立方的基础上，通过完全纪录基本单元组所对应的单值维集（the single dimension set，SD或SDSET），进一步降低了数据立方的存储代价。 在Min-Cube中，存在着多条由相同的基表元组集合聚集而成的元组，这些元组称为同源元组（Homeotic Tuple，HT）。类似浓缩数据立方的思想，在这些由同源元组中有规则的选择一条作为代表，能更进一步的减小数据立方的尺寸，这样形成的新的数据立方的组织形式称为面向同源元组的浓缩数据立方（HTC-Cube）。同源元组浓缩数据立方中非基本数据立方内的各条元组相互之间没有任何直接联系，因此，同源元组浓缩数据立方是一种最简数据立方形式，其尺寸在已知的多种基于浓缩思想的数据立方组织形式中是最小的。 同时，根据面向同源元组的数据立方浓缩组织形式中非基本数据立方元组之间相互无关的特性，可以在分层索引的层次之间体现出查询相关性。因此，将同源元组浓缩数据立方组织成一种分层自索引的数据立方结构，根据非基表元组的索引信息，利用其层次间的查询相关性可以迅速定位其基本数据立方元组，从而取得较好的查询效率。