WSL操作指南

扩展行的概念

为了对常见的多维数据的扩展操作进行支持，本文提出了一种 n 维可扩展数组 ，该数组可以在任何维度仅使用三种辅助表为代价对某个维度中进行维度上的拓展；对于维度 ,这三个辅助数组分别为：历史表 ,地址表 ,和系数表 ,其结构如下图所示：

如上图所示，历史表 和地址表 都是一维数组，其中历史表用来记录行发生扩展的历史，一个维的扩展行 由拥有个维度的子数组构成 。

例如对于一个n维数组A，其维度信息分别为：，如果需要在维度上进行拓展,需要动态分配一片连续的地址空间给由n-1维构成的子数组S来保存新增维度的信息，子数组S的各个维度大小分别为，然后将这个新的子数组S添加到A中的维度i。

然后，历史数值计数器h加一，并将这个值h储存到历史表中，S中的第一个地址被保存到地址表中，注意，新增加的这个数组S通常是一个固定长度的数组，而真实的数据存储在S的子数组中。

例如，一个元组在一个n维固定大小的数组中的位置可以由下面的公式定位：

+d_3d_4…d_ni_2+….+d_ni_{n-1}+i_n$

为了便于这个计算，我们将数组保存下来，及作为系数向量，将其保存在前文提到的系数表中。

举一个实例，假设A是一个四维的可扩展数组，各个维度的信息分别为,如果在维度上进行扩展的话，就需要分配一个三维固定长度的数组S，各维度大小分别为，S中的元组可以按照行或者列的顺序进行安排，其地址计算函数为：。

因此我们可以记多维系数向量，对于A的每个维度上的每一次扩展，都需要计算相对应的子数组的系数向量并将其保存对应维度的系数表。大体上说，如果A是n维可扩展表的话（n>2），对于每一个维度，都需要建立一个拥有n-2维度的系数表。

通过以上的三种系数表，便可以通过以下的形式计算每一个数组元素的地址。

如上图中的元素，比较。因为有：,可以说明元素在对应的最近的历史值为8，同时我们可以根据该值得出对应的子数组的起始地址为36（保存在中），通过系数向量我们可知，元素相对于S中第一个地址的偏移量为,因此可以得出该元素对应的地址为。

从上面的元素访问的过程我们可以得知，为了从多个历史表中获得历史变量的最大值，需要对n条记录进行比较；获取了最大值之后，需要对拥有n-1个维度的固定长度子数组通过之前提到的特定地址函数来对其偏移量进行计算。但是，乘法操作和加法操作的实际执行次数要远少于n维固定长度的数据的规模。

基于扩展行的压缩行储存算法

给定一个拥有三个维度的压缩行，EaCRS将每一个子数组进行独立压缩，这种储存格式使用三个一维数组：VL（浮点），RO，CO（整数）对于每一个可扩展数组的子数组（对于n维的可扩展数组，子数组拥有n-1个维度 ）,可以将子数组中的全部非零值进行压缩。

数组RO存储了每行中的非零元素。拥有最短长度的维度通常被选作为行维度。如果一行的长度为k的话，RO就包含k+1个元素，RO[0]=1.RO[1]则包含子数组和RO[0]的第0行的非零元素。总的来说，RO[i]即为第i-1行中的非零元素的个数累加上之前RO[i-1]的值。

数组CO则保存每一个行元素的列索引值。

VL储存每行元素的非零值。

对于每一个子数组，他们的RO,CO和VL的初始值都为0。

在EaCRS格式中，对于一个n维的可扩展数组，在其三个辅助表中，只有历史表在每个维度上都需要保存，其是用来计算子数组的扩展维度与其他维度的长度和子数组的大小。

下图展示了上图中所示模式的一个EaCRS扩展数组的例子：

为了方便起见我们给定每一个子数组一个名字SA_i_j，其中i表示其所属的被扩展的维度，而j表示该维度的长度。举个例子SA_1_0,SA_1_1,…SA_1_是维度1的子数组，而SA_2_1,SA_2_2,…SA_2_则是维度2的子数。

考虑到图片1中的子数组SA_1_3，这个子数组沿着维度1进行扩展，如下面图片3中(a)：36,37,38…,47表示了给定三维可扩展数组的子数组元素的逻辑存储位置。为了扩展这里的稀疏度，我们给每一个子数组元素分配一些零和非零值，（例如逻辑位置中的36被分配给0，37被分配给13，38被分配给了0）。
考虑到SA_1_3沿着维度1进行扩展，剩下的两个维度则被考虑为行维度和列维度。对于SA_1_3，维度3的长度要比维度2短，所以在其对应的EaCRS格式中，维度3为行维度，维度2是列维度。

在子数组SA_1_3中有三行数据，其中第0行的数据包含一个非零值12（如上图b所示），这是因为RO[1]=2（0-1行有两个元素）,RO[2]=6（0-3行有六个元素）,RO[3]=7，VL行保存了子数组中所有的非零行元素（12，13，14，15，16），而CO行存储了这些非零元素在该列中对应的列数组索引。

EaCRS格式的前向映射和反向映射

前向映射：从逻辑数据库位置计算出物理数据库位置。
反向映射：从物理数据库位置计算出逻辑数据库位置

其中逻辑数据库和物理数据库可以理解为数据经过压缩的前与后的两个状态。

前向映射

这里通过一个案例来说明前向映射，以元素<3,3,1>为例，考虑到，因为，可以看出扩展的维度的是1号维度，该元素被包含在子数组SA_1_3之中，而在诸多维度之中，用于成员最少的维度通常被考虑为SA_1_3的行维度，又因为且，可知子数组SA_1_3的大小为,维度3作为行维度，该维度拥有的成员数量为3。又因为子数组是二维的，在这个前提下，维度2是SA_1_3唯一的列维度。上上图（a）中，第一行所有的非零元素的格式为RO[2] –
RO[1] = 6 – 2 = 4，该行所对应的非零元素的列索引保存在CO[RO[1]-1]，CO[RO[1]]，CO[RO[1]+1]和CO[RO[1]+2]中，即为CO[1], CO[2], CO[3]和 CO[4]，因为该行有四个非零元素，该行中非零元素所对应的数值即为VL[1], VL[2], VL[3] 和 VL[4].

后向映射

---

转载无需注明来源，放弃所有权利