計算機(jī)科學(xué)2007Vol. 34No. 1ETL執(zhí)行過程的優(yōu)化研究*)吳遠(yuǎn)紅(浙江海洋學(xué)院信息學(xué)院舟山 316004)摘要提出了一個ETL(Exrction: Transformation-Loading)優(yōu)化框架并對ETL過程的邏輯優(yōu)化進(jìn)行了研究,把優(yōu)化問題建模成狀態(tài)空間搜索問題。每個ETL工作流看作-種狀態(tài),通過一系列正確的狀態(tài)變換來構(gòu)造狀態(tài)空間,并且提出算法來獲得最小執(zhí)行時間的ETL工作流。理論分析和實踐表明其具有良好效果。關(guān)鍵詞ETL,工作流,優(yōu)化The Research of Optimizing ETL Execution ProcessWU YuanrHong(Information College of Zhejiang Ocean University, Zhoushan 316004)Abstract An optimization framework is provided in the paper ,and the logical optimization of ETL processes is researched. The optimization problem is modeled as a state space search problem. Each ETL workflow is considered as astate and the state space is fabricated through a set of correct state transitions. Moreover，algorithms are provided to-wards the minimization of the execution cost of an ETL workflow . The theory and experiment result prove it to be effi-cient.Keywords ETL, Workflow ,Optimization算法,理論和實踐表明這種方法對于海量數(shù)據(jù)的處理很有效。1前言ETL過程不能單純地作為一個大的查詢交給數(shù)據(jù)庫去數(shù)據(jù)倉庫作為一-種數(shù)據(jù) 密集型應(yīng)用，由兩部分構(gòu)成:靜態(tài)處理.去優(yōu)化。為此提出如圖1所示的ETL執(zhí)行優(yōu)化框架,部分和動態(tài)部分,靜態(tài)部分是指數(shù)據(jù)倉庫的體系架構(gòu)和實例它由ETL過程設(shè)計器、優(yōu)化器、調(diào)度抽取.轉(zhuǎn)換、加載等幾種數(shù)據(jù),動態(tài)部分是構(gòu)建和維護(hù)數(shù)據(jù)倉庫的各種進(jìn)程，負(fù)責(zé)加類型的活動組成,其中ETL執(zhí)行優(yōu)化主要是尋求一個和原載、刷新等,這主要由ETL工具完成。ETL 負(fù)責(zé)將分布的、ETL過程等價的、最小執(zhí)行代價的ETL過程。其處理過程異構(gòu)的數(shù)據(jù)源數(shù)據(jù)(如關(guān)系數(shù)據(jù)文本數(shù)據(jù).XML.HTML等)如下:由ETL過程設(shè)計器設(shè)計好ETL過程,提交給優(yōu)化器，抽取到臨時中間層(Data Staging Area), 在中間層進(jìn)行清洗、通過轉(zhuǎn)換規(guī)則進(jìn)行等價狀態(tài)變換生成狀態(tài)空間，再由算法根轉(zhuǎn)換集成,然后加載到數(shù)據(jù)倉庫，成為決策支持(如OLAP,據(jù)代價模型進(jìn)行狀態(tài)空間搜索獲得最小執(zhí)行代價ETL工作數(shù)據(jù)挖掘)的基礎(chǔ)。ETL 作為一種數(shù)據(jù)轉(zhuǎn)換和集成的工具，流。是構(gòu)建數(shù)據(jù)倉庫的基本工具。2問題建模。 用戶界面.I EnL執(zhí)行優(yōu)化器I ETL過程執(zhí)行交互等價狀態(tài)的狀態(tài)空間生戚.轉(zhuǎn)換規(guī)附ETL工作流的優(yōu)化問題可建模成狀態(tài)空間搜索問題:每|元數(shù)據(jù)管理工具一個狀態(tài)是- -個ETL工作流圖,對每個狀態(tài)采用狀態(tài)變換產(chǎn)狀態(tài)空間搜索量小代價狀態(tài).手代價模型Emu過程設(shè)計舞生所有可能的等價狀態(tài)，從中找出代價最小的狀態(tài)即為最優(yōu)ETL執(zhí)行過程。轉(zhuǎn)換活動調(diào)度懸2.1 EIL 工作流的形式化定義廣抽取器活動是一-個四元組A=(ID,I,O,S), ID是活動標(biāo)識符,元數(shù)拋庫I是輸入模式的集合,0是輸出模式的集合,S是-個或多個擴(kuò)展的關(guān)系代數(shù)表達(dá)式,表示每個輸出模式的語義。轉(zhuǎn)換源中間層轉(zhuǎn)換目標(biāo)每個ETL工作流看作-一個狀態(tài)也就是- - 個有向無環(huán)圖(DAG圖),圖的節(jié)點可以是ETL活動和記錄集,邊代表數(shù)據(jù)圖1 ETL執(zhí)行優(yōu)化框架圖供給關(guān)系。目前對它的研究主要在ETL過程的建模1.43 ,但對ETL假定有活動集A.記錄集RS,供給關(guān)系集Pr ,ETL工作過程優(yōu)化的研究卻不多,它不同于多查詢優(yōu)化們,因為多查詢流可中國煤化Iv,E),V=AURS,E=優(yōu)化主要著眼于將各個不同的查詢語句局部最優(yōu)化,而在Pr.HCN M H G給每一個活動賦值唯ETL過程中,各個活動相互關(guān)聯(lián),全局優(yōu)化是必須考慮的。一的執(zhí)行優(yōu)無權(quán)作為結(jié) 切杯不付。本文提出一種ETL優(yōu)化執(zhí)行框架,并給出具體的優(yōu)化過程和2.2轉(zhuǎn)換規(guī)則* )基金項目:浙江省教育廳項目(0050113);浙江海洋學(xué)院項目(X05LQ07)。昊遠(yuǎn)紅講師,碩士,研究方向;數(shù)據(jù)抽取、數(shù)據(jù)挖掘?！?1●接下來引人狀態(tài)的一系列邏輯轉(zhuǎn)換。表達(dá)式S'= T(S)活動分配到兩個并行分支里來提高效率。這兩種變換分別記表示從狀態(tài)s到s'的變換,這些邏輯轉(zhuǎn)換包括:為FAC(as ,a1 ,az)和DIS( ar, a)如圖2(b)。FAC與DIS本.1)SWA變換:交換一元活動an ,az在圖中的順序,記為質(zhì)上是對-元和二元活動進(jìn)行交換。SWA(al,ar)如圖2(a),這樣可以把選擇頻率高的活動推向3)MER與SPL變換:用這兩個變換來組合活動和取消工作流的開端,類似于傳統(tǒng)的代數(shù)優(yōu)化。組合而不改變它們的語義。這兩種變換分別記為MER2)FAC與DIS變換: FAC把匯聚前在匯聚的兩個分支(a1+z ,an ,az)和SPL(a1+2 ,a1 ,a2)如圖2(C)。這樣搜索空間里各做了一次即兩次操作,放在匯聚后做一次。DIS把一個可以大大減少。8SWA(a,2) |SWA(2曲)MER(arzhag)↓↑SPL(國z劇雨)FACaa2) |↑ DIS(B,回)| a142 .a>- >(細(xì)) SWA .(b) FAC and DIS(C) MER and SPL圖2狀態(tài)的邏輯變換2.3 代價模型s'=SGen(s);,unvisited- -s'給定活動a, C(a)代表a的代價(不僅和代價模型有關(guān)而且和活動在工作流中所處的位置有關(guān)) ,C(a)代價評估可visited←-S以采用查詢優(yōu)化的各種代價模型。整個狀態(tài)的代價是它所有5. return SMN活動的代價和。6. End.C(S)= gc(a;)3.2 啟發(fā)式算法首先對搜索空間的每-一個狀態(tài)利用元數(shù)據(jù)庫的統(tǒng)計信息為了避免搜索整個狀態(tài)空間,采用啟發(fā)式算法進(jìn)行改進(jìn)，進(jìn)行代價評估。最優(yōu)化ETL工作流問題就是找到一個狀態(tài)轉(zhuǎn)換前對工作流可以約束的活動進(jìn)行MER變換;接著HS找SMEN ,C(Smav )最小。到初始狀態(tài)中所有的同類活動(H)和可分解活動(D) ,然后把2.4 元數(shù)據(jù)庫初始狀態(tài)S0分組(L);僅在線性路徑中應(yīng)用SWAP變換;對主要保存ETL過程的元數(shù)據(jù)和臨時中間層中數(shù)據(jù)庫概處于兩個匯聚流的同類活動應(yīng)用FAC變換;在轉(zhuǎn)換適用性允貌的統(tǒng)計描述,包括模型信息、表定義、視圖、用戶自定義類型許的情況下應(yīng)用DIS變換;僅在前面用FAC變換和DIS變換和函數(shù)約束等等。ETL 執(zhí)行優(yōu)化器在生成執(zhí)行計劃時將其產(chǎn)生的新狀態(tài)的線性路徑中再次應(yīng)用SWAP變換;最后返回作為定量分析的參考,通常包括元組的數(shù)目,屬性的大小,和最小代價狀態(tài)SMav。對于不同屬性的不同值的數(shù)目。為了保證基本統(tǒng)計信息的正下面是其實現(xiàn)算法。確性,需要不斷地修改元數(shù)據(jù)庫中的相關(guān)內(nèi)容。算法Heuristic Search (HS)3基于算法的狀態(tài)空間搜索輸入:初始狀態(tài)S,即圖G= {V,E)和在預(yù)處理中用到的-系列合并3.1 窮舉法輸出:最小代價狀態(tài)SMaN在窮舉搜索法中,對每個狀態(tài)采用狀態(tài)變換產(chǎn)生所有可首先對工作流可以約束的活動進(jìn)行合并MER變換Unvisited-. s能的狀態(tài),并把狀態(tài)空間抽象成圖，節(jié)點代表狀態(tài),邊代表狀visited- 0態(tài)間的轉(zhuǎn)換。窮舉搜索算法設(shè)置已訪問節(jié)點集合保存已經(jīng)訪SMNSO問節(jié)點和未訪問節(jié)點集合保存未訪問節(jié)點,算法從未訪問節(jié)D-Find Distributable- Activivities(So);L+ -Find_ Local Groups(So);點集合中取出一個未訪問狀態(tài),產(chǎn)生它的經(jīng)過狀態(tài)變化后的.“ For each gi in L{狀態(tài)進(jìn)行進(jìn)- -步處理。算法產(chǎn)生所有可能的狀態(tài),然后從所For each pair(ai,aj)in gi{有已訪問狀態(tài)中找出代價最小的狀態(tài),即為問題的解。算法TH(c(Smw)