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