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

無效

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

技術(shù)領(lǐng)域

本發(fā)明屬于計算機信息分析與數(shù)據(jù)處理領(lǐng)域，具體涉及一種基于內(nèi)存映像的增量數(shù)據(jù)清洗方法。

背景技術(shù)

當(dāng)建立一個信息系統(tǒng)的時候，即使進行了良好的設(shè)計和規(guī)劃，也不能保證在所有情況下，所存放數(shù)據(jù)的質(zhì)量都能滿足用戶的要求。用戶錄入錯誤、企業(yè)合并以及企業(yè)環(huán)境隨時間的推移而改變，這些都會影響所存放數(shù)據(jù)的質(zhì)量。因此，有必要用元數(shù)據(jù)來表示數(shù)據(jù)質(zhì)量。數(shù)據(jù)的一致性(consistency)、正確性(correctness)、完整性(completeness)和最小性(minimality)四個指標用來說明數(shù)據(jù)的質(zhì)量程度。數(shù)據(jù)清洗過程就是解決對同一概念有不同的表示方法，在集成多個數(shù)據(jù)源時，消除模式?jīng)_突以及相似重復(fù)記錄等問題。

如今市場上有許多這種清洗工具和數(shù)據(jù)清洗技術(shù)，但是大多數(shù)是將數(shù)據(jù)放在外部磁盤上，并且一旦數(shù)據(jù)有所污染就得整個表甚至整個數(shù)據(jù)庫數(shù)據(jù)倉庫全盤清洗，這樣就導(dǎo)致清洗效率很低。為了克服傳統(tǒng)數(shù)據(jù)清洗的弊端，本發(fā)明設(shè)計了一種全新的數(shù)據(jù)清洗方法，充分利用內(nèi)存數(shù)據(jù)庫查詢、增加和刪除速度快的優(yōu)勢，將要操作的數(shù)據(jù)載入內(nèi)存建立MDB-樹索引，解決緩存敏感和TLB失效等問題，提高數(shù)據(jù)匹配率。同時本發(fā)明使用增量數(shù)據(jù)清洗方法，利用關(guān)系代數(shù)運算實現(xiàn)結(jié)點的增量維護，從而避免耗時的全量維護操作。本發(fā)明所涉及的現(xiàn)有技術(shù)包括：

1、內(nèi)存數(shù)據(jù)庫(MDB)索引技術(shù)

傳統(tǒng)基于磁盤的關(guān)系數(shù)據(jù)庫系統(tǒng)(DRDB)，由于主數(shù)據(jù)庫常駐磁盤，事務(wù)處理往往涉及磁盤IO操作，其體系結(jié)構(gòu)設(shè)計的優(yōu)化目標是如何減少讀寫磁盤的次數(shù)，很難滿足未來基于網(wǎng)絡(luò)的應(yīng)用系統(tǒng)對高性能數(shù)據(jù)訪問能力的需求。內(nèi)存數(shù)據(jù)庫(MDB)的數(shù)據(jù)永久駐留在內(nèi)存中。MDB在訪問數(shù)據(jù)時，擁有比DRDB更高的訪問效率。隨著內(nèi)存價格不斷降低，內(nèi)存容量擴大，在內(nèi)存中存儲越來越大的數(shù)據(jù)庫變得可行。

DRDB采用的索引結(jié)構(gòu)主要是B/B+樹，其設(shè)計目標就是減少訪問磁盤數(shù)據(jù)的IO次數(shù)。而在MDB中，采用了一種新的索引結(jié)構(gòu)T樹，其設(shè)計目標是減少內(nèi)存開銷和CPU指令數(shù)。T樹是由AVL樹和B樹發(fā)展而來，它是一種一個節(jié)點包含多個元素的二叉樹。由于是二叉樹，T樹保持了AVL樹二分查找的高效率，同時一個T節(jié)點包含多個元素，象B樹一樣，每個節(jié)點的充滿程度保持在半滿和全滿之間，在插入和刪除所引起的數(shù)據(jù)移動通常只需要在一個節(jié)點內(nèi)進行，減少了為保持樹的平衡所必須進行的旋轉(zhuǎn)操作。由于索引和數(shù)據(jù)全部在內(nèi)存中，在一個T樹節(jié)點中不需要像B樹那樣存放N個索引鍵值-指針對，只需要存放指向內(nèi)存中相應(yīng)記錄對應(yīng)字段的指針，這樣索引中變長字段的儲存不再是問題。但是隨著對處理器緩存作用的認識逐漸加深，MDB的數(shù)據(jù)訪問技術(shù)熱點研究方向在訪問過程中如何利用好處理器緩存，使得性能能得到最大優(yōu)化。而T樹的緩存利用率很差，反而制約了性能潛力的挖掘。因而人們相繼研制了CSS樹，CSB+樹等緩存敏感索引技術(shù)以及本發(fā)明中用到的MDB-樹。

2、數(shù)據(jù)增量維護技術(shù)

在對數(shù)據(jù)倉庫數(shù)據(jù)清洗過程中，需要兩種ETL過程：全量ETL過程和增量ETL過程，全量ETL過程用于數(shù)據(jù)倉庫的初始化，而增量ETL過程則用于不斷將新數(shù)據(jù)載入數(shù)據(jù)倉庫。而借用物化視圖增量維護的方法，可以利用全量ETL過程來自動產(chǎn)生增量ETL過程。但是物化視圖最初是為了提高數(shù)據(jù)倉庫查詢效率而提出的，增量維護是為了有效更新物化視圖，因而已有對物化視圖增量維護的研究集中于數(shù)據(jù)倉庫環(huán)境。數(shù)據(jù)倉庫中的數(shù)據(jù)都按主題組織，查詢中大量用到聚合、選擇、投影、聯(lián)接運算，而很少用到差運算，但是ETL過程中經(jīng)常會用差運算剔除不需要的數(shù)據(jù)，這是與數(shù)據(jù)倉庫環(huán)境下物化視圖維護不同的地方。

數(shù)據(jù)增量維護技術(shù)首先對ETL過程中的關(guān)系代數(shù)運算結(jié)點進行規(guī)范化，然后分別對規(guī)范化后的關(guān)系代數(shù)運算結(jié)點進行增量維護，在本發(fā)明中主要考慮6種關(guān)系代數(shù)運算(聚合α、選擇σ、投影π、聯(lián)接并U、差-)，規(guī)范為AUSPJ(聚合、并、選擇、投影與聯(lián)接)片段和D(差)片段的組合。同時給出這兩種片段的增量維護方法。

3、結(jié)果集歸并技術(shù)

關(guān)于結(jié)果集的歸并是該方法能夠正常使用的基礎(chǔ)之一。當(dāng)返回查詢結(jié)果時，實際上將所有多個線程查詢模塊的結(jié)果集進行歸并，在所有的查詢結(jié)果到達主調(diào)模塊前需要做初級的排序。到達主調(diào)模塊后通過歸并將各個模塊的結(jié)果集進行一遍歸并。

發(fā)明內(nèi)容

為了克服現(xiàn)有技術(shù)的上述缺點，本發(fā)明提供了一種基于內(nèi)存映像的增量數(shù)據(jù)清洗方法，充分利用了當(dāng)今計算機內(nèi)存大的優(yōu)勢，將待清洗數(shù)據(jù)載入到內(nèi)存，建立高效的MDB-樹索引結(jié)構(gòu)，大大提高數(shù)據(jù)訪問速率，利用增量清洗方式，提高數(shù)據(jù)清洗效率。