[發(fā)明專利]基于內(nèi)存映像的增量數(shù)據(jù)清洗方法

無效

• 申請?zhí)枺?/td>: 201110316914.5
• 申請日: 2011-10-18
• 公開（公告）號: CN102495834A
• 公開（公告）日: 2012-06-13
• 發(fā)明（設(shè)計(jì)）人: 唐雪飛;陳科;汪海良;李應(yīng)洪
• 申請（專利權(quán)）人: 成都康賽電子科大信息技術(shù)有限責(zé)任公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 電子科技大學(xué)專利中心 51203
• 代理人: 周永宏

1.一種基于內(nèi)存映像的增量數(shù)據(jù)清洗方法，其特征在于：包括如下步驟：

第一步、首先數(shù)據(jù)載入到內(nèi)存，構(gòu)建內(nèi)存數(shù)據(jù)庫MDB-樹索引結(jié)構(gòu)，在建立好MDB-樹索引結(jié)構(gòu)后利用二級cache的失效率和TLB的失效率建立代價(jià)模型對該樹結(jié)構(gòu)進(jìn)行評估。

第二步、利用MDB-樹進(jìn)行數(shù)據(jù)的查詢、插入和刪除操作；

第三步、將內(nèi)存數(shù)據(jù)庫物化視圖規(guī)范化為AUSPJ(聚合、并、選擇、投影與聯(lián)接)片段和D(差)片段，采用關(guān)系代數(shù)運(yùn)算實(shí)現(xiàn)結(jié)點(diǎn)的增量維護(hù)；

第四步、采用結(jié)果集歸并算法實(shí)現(xiàn)數(shù)據(jù)清洗操作。

2.根據(jù)權(quán)利要求1所述的基于內(nèi)存映像的增量數(shù)據(jù)清洗方法，其特征在于：在所述評估過程中：

1)按如下公式計(jì)算MDB-樹的葉結(jié)點(diǎn)的cache失效的數(shù)量：

其中：n為可用的節(jié)點(diǎn)數(shù)，q為待匹配數(shù)據(jù)項(xiàng)的個(gè)數(shù)，h為樹的高度，n_c為一個(gè)結(jié)點(diǎn)跨越的Cache?Line的數(shù)量，u為結(jié)點(diǎn)或者桶鏈的平均利用率；

2)按如下公式計(jì)算TLB失效的數(shù)目：

TLBm=Cm-1log2(u*nc)+0.5+1.]]>

3.根據(jù)權(quán)利要求1所述的基于內(nèi)存映像的增量數(shù)據(jù)清洗方法，其特征在于：在所述數(shù)據(jù)的查詢操作過程中，結(jié)點(diǎn)內(nèi)查詢算法按如下步驟進(jìn)行：

1)根據(jù)輸入的結(jié)點(diǎn)指針和輸入鍵值，將該結(jié)點(diǎn)指針指向的結(jié)點(diǎn)中的p.key與輸入鍵值key比較，得到key在該結(jié)點(diǎn)區(qū)間的范圍，然后判斷該區(qū)間指向子結(jié)點(diǎn)的指針是否為空，如果不為空則在該結(jié)點(diǎn)的子結(jié)點(diǎn)中繼續(xù)查找；如果為空則表示該結(jié)點(diǎn)為葉結(jié)點(diǎn)；

2)使用hash函數(shù)對key做hash運(yùn)算得到hash地址，根據(jù)hash地址在葉結(jié)點(diǎn)中的HASH表中查找，如果沒有找到則查找失敗，如果有多個(gè)索引，則以該HASH地址為頭指針的桶鏈中依次查找key值，如果有則將該key值對應(yīng)的索引地址返回，如果不存在則查找失敗。

4.根據(jù)權(quán)利要求1所述的基于內(nèi)存映像的增量數(shù)據(jù)清洗方法，其特征在于：在所述數(shù)據(jù)的插入、刪除操作過程中，先查詢要插入或刪除的KEY所對應(yīng)的葉結(jié)點(diǎn)，當(dāng)葉結(jié)點(diǎn)被定位后，對于插入操作，判斷該結(jié)點(diǎn)是否有足夠的空間來容納新的索引項(xiàng)，如果空間不足，則分裂葉結(jié)點(diǎn)；對于刪除操作，如果刪除該索引項(xiàng)以后，該葉結(jié)點(diǎn)不存在其他索引項(xiàng)，則重新調(diào)整MDB-樹。

5.根據(jù)權(quán)利要求1所述的基于內(nèi)存映像的增量數(shù)據(jù)清洗方法，其特征在于：所述采用關(guān)系代數(shù)運(yùn)算實(shí)現(xiàn)結(jié)點(diǎn)的增量維護(hù)包括如下步驟：

1)將一個(gè)包含有五種基本關(guān)系運(yùn)算和聚合運(yùn)算的ETL過程規(guī)范化為AUSPJ片段和D片段的組合，ETL過程的規(guī)范化結(jié)果為：一個(gè)D片段只包含單個(gè)差運(yùn)算，一個(gè)AUSPJ片段包括五種基本關(guān)系運(yùn)算，并且必須滿足下面四種情況之一：a)如果有聚合運(yùn)算，則聚合運(yùn)算必須在AUSPJ片段的最上面；b)AUSPJ片段跟在D片段后面；c)AUSPJ片段跟在聯(lián)接運(yùn)算后面，而并運(yùn)算則在AUSPJ片段的最上面；d)AUSPJ片段是ETL過程中最上面的片段；

2)對兩種片段實(shí)現(xiàn)增量維護(hù)：

對AUSPJ片段的增量維護(hù)：必須維護(hù)以下三種物化視圖：a)聯(lián)接運(yùn)算的所有輸入關(guān)系；b)投影運(yùn)算和并運(yùn)算的輸出關(guān)系，并且此關(guān)系要增加計(jì)數(shù)屬性或允許保存重復(fù)數(shù)據(jù)；c)聚合運(yùn)算的輸出關(guān)系；

對D片段的增量維護(hù)：其輸入關(guān)系必須是物化視圖，采用SRA方法或BRA方法實(shí)現(xiàn)。