基于内存映像的增量数据清洗方法

1.一种基于内存映像的增量数据清洗方法，其特征在于：包括如下步骤：
第一步、首先数据载入到内存，构建内存数据库MDB-树索引结构，在建立好MDB-树索引结构后利用二级cache的失效率和TLB的失效率建立代价模型对该树结构进行评估。
第二步、利用MDB-树进行数据的查询、插入和删除操作；
第三步、将内存数据库物化视图规范化为AUSPJ(聚合、并、选择、投影与联接)片段和D(差)片段，采用关系代数运算实现结点的增量维护；
第四步、采用结果集归并算法实现数据清洗操作。
2.根据权利要求1所述的基于内存映像的增量数据清洗方法，其特征在于：在所述评估过程中：
1)按如下公式计算MDB-树的叶结点的cache失效的数量：
其中：n为可用的节点数，q为待匹配数据项的个数，h为树的高度，nc为一个结点跨越的Cache Line的数量，u为结点或者桶链的平均利用率；
2)按如下公式计算TLB失效的数目：
3.根据权利要求1所述的基于内存映像的增量数据清洗方法，其特征在于：在所述数据的查询操作过程中，结点内查询算法按如下步骤进行：
1)根据输入的结点指针和输入键值，将该结点指针指向的结点中的p.key与输入键值key比较，得到key在该结点区间的范围，然后判断该区间指向子结点的指针是否为空，如果不为空则在该结点的子结点中继续查找；如果为空则表示该结点为叶结点；
2)使用hash函数对key做hash运算得到hash地址，根据hash地址在叶结点中的HASH表中查找，如果没有找到则查找失败，如果有多个索引，则以该HASH地址为头指针的桶链中依次查找key值，如果有则将该key值对应的索引地址返回，如果不存在则查找失败。
4.根据权利要求1所述的基于内存映像的增量数据清洗方法，其特征在于：在所述数据的插入、删除操作过程中，先查询要插入或删除的KEY所对应的叶结点，当叶结点被定位后，对于插入操作，判断该结点是否有足够的空间来容纳新的索引项，如果空间不足，则分裂叶结点；对于删除操作，如果删除该索引项以后，该叶结点不存在其他索引项，则重新调整MDB-树。
5.根据权利要求1所述的基于内存映像的增量数据清洗方法，其特征在于：所述采用关系代数运算实现结点的增量维护包括如下步骤：
1)将一个包含有五种基本关系运算和聚合运算的ETL过程规范化为AUSPJ片段和D片段的组合，ETL过程的规范化结果为：一个D片段只包含单个差运算，一个AUSPJ片段包括五种基本关系运算，并且必须满足下面四种情况之一：a)如果有聚合运算，则聚合运算必须在AUSPJ片段的最上面；b)AUSPJ片段跟在D片段后面；c)AUSPJ片段跟在联接运算后面，而并运算则在AUSPJ片段的最上面；d)AUSPJ片段是ETL过程中最上面的片段；
2)对两种片段实现增量维护：
对AUSPJ片段的增量维护：必须维护以下三种物化视图：a)联接运算的所有输入关系；
b)投影运算和并运算的输出关系，并且此关系要增加计数属性或允许保存重复数据；c)聚合运算的输出关系；
对D片段的增量维护：其输入关系必须是物化视图，采用SRA方法或BRA方法实现。
6.根据权利要求5所述的基于内存映像的增量数据清洗方法，其特征在于：所述BRA方法是指对于物化视图C＝A-B，如果满足以下三种情况之一，则C是自维护的：
a)A只有删除增量且B只有插入增量；
b)A只有删除增量且B没有增量；
c)A没有增量且B只有插入增量。
7.根据权利要求1所述的基于内存映像的增量数据清洗方法，其特征在于：所述结果集归并算法是指根据每个线程查询的结果，将子结果集进行合并，最终成为完整的查询结果。

暂无