（计算机应用技术专业论文）etl工作流的建模及优化.pdf

上海师范大学硕士研究生学位论文 e t l 工作流的建模及优化 摘要 e t l ( 抽取、转换、装载) 过程的开发是数据仓库开发的重要组成部分。 目前大型企业数据仓库( e d w ) 的实施中，需要处理的数据量非常庞大，逻辑 关系复杂，所以e t l 工作流的执行需要消耗大量的时间，经常无法在规定的时 间内完成数据的集成，造成大量的文件堆积。为了减少这样的问题出现，本文 提出一个e t l 工作流建模及优化的方案。 本文首先对e t l 活动的通用模型进行了改进，然后利用建立的e t l 活动模 型对工作流进行建模，将每个e t l 工作流看成一个状态，利用交换、因式分解 等转换来构建状态空间，最后采用状态空间搜索的方法实现对e t l 工作流的优 化，从而减少e t l 工作流的执行时间。 e t l 工作流的执行时间无法预计，会影响e t l 开发部门与客户之间服务协 议( s l a ) 的制定与实施，这是目前e t l 开发工作中存在的又一问题。针对这 个问题，本文提出一个时间成本模型。首先，在对e 儿活动进行建模的过程 中，引入一元线性回归方法，用来分析e t l 活动的执行时间与数据量之间的关 系。然后在此基础上，采用关键路径的思想，估算出整个e t l 工作流的执行时 间，为e l l 过程的实施和控制提供参考数据。 为了检验e t l 工作流优化方案的有效性，本文实现了e t l 工作流优化方案 中的主要算法，并对算法进行了测试。实验证明，当工作流中包含的活动数目 在一定范围内时，e t l 工作流的优化方案执行效率较高，并能够有效地优化 e 1 几工作流，减少其执行时间。 关键词：e t lt 作流建模，e t l 工作流优化，时间成本模型，状态空间，数据集 成，数据仓库 上海师范大学硕士研究生学位论文e r l 工作流的建模及优化 a b s t r a c t 1 1 舱i m p l e m e n t a t i o n o fe t l ( e x t r a c t i o n - t r a n s f o r m a t i o n - l o a d i n g ) i s v e r y i m p o r t a n ti nt h ed e v e l o p m e n to fd a t aw a r e h o u s e ( d v o c u r r e n t l y , t h el a r g e s c a l e e n t e r p r i s ed a t aw a r e h o u s e ( e d w ) s h o u l dd “) c c s sv a s td a t aw i t h i nal i m i t e dt i m e a n d t h ed a t am a yh a v ec o m p l e xl o # c a lr e l a t i o n s h i p s t h e r e f o r e ，t h ee x e c u t i o no fe t l r e q u i r e sal o n gt i m ea n ds o m c t h n e si tc o u l dn o tb ef i n i s h e d 鹊s c h e d u l e d i nt h a tc a s e t h es t a c ko fd a t af i l e sw o u l da r i s ea n dc a u s eal o to fp r o b l e m s t od e a lw i t hs u c ha p r o b l e m w ep r o p o s eam e t h o dt om o d e la n do p t i m i z ee t lw o r k f l o w s i nt h i sp a d e r , w ef i r s ti n t r o d u c ea ni m p r o v e dm o d e lo fe t la c t i v i t i e s o nt h eb a s i s o f m o d e lw ed e l v ei n t ot h em o d e l i n ga n do p t i m i z a t i o no f e t lw o r k f l o w w jc o n s i d e r e a c he t lw o r k f l o wa sas t a t ea n df a b r i c a t et h es t a t es p a c et h r o u g has e to fc o r r e c t s t a t et r a n s i t i o n s 1 r i 坨t i m eo fe t le x e c u t i o nw o u l db ed e c r e a s e dt h r o u g ht h e o p t i m i z a t i o n a n o t h e rp r o b l e mi nt h ed e v e l o p m e n to fe t li st h a ti t sah a r dw o r kt oe s t i m a t e t h et i m eo f e x e c u t i n ge t lw o r k _ f l o w s a sac o n s e q u e n c e i tw o u l dh a v eng r e a ti m p a c t o nt h ee s t a b l i s h m e n ta n di m p l e m e n t a t i o no fs e r v i c el e v e la g r e e m e n t ( s l a ) b e t w e e n t h ed e v e l o p e r sa n dc u s t o m e r s f o rt h i sr e a s o n , w ep r o p o s eat i m ec o s tm o d e li i lt h i s p a p e r f i r s t , d u r i n gt h ep r o c e s so fm o d e l i n ge t la c t i v i t y , w ec i t et h es t a t i s t i c a l r e g r e s s i o na n a l y s i sm e t h o dt oa n a l y z et h ea s s o c i a t i o nb e “啪t i m eo fe x e c u t i o na n d t h ev o l u m eo fd a t ap r o c e s s e d t h e l lw eu s et h ec r i t i c a lp a t ha l g o r i t h mt oc a l c u l a t et h e t i m es p e n ti nt h ee x e c u t i o no ft h ee t lw o r k f l o ws c e n a r i o i tc o u l db et h er e f e r e n c e d a t af o rt h ec o n t r o lo f e t lw o r k f l o wr e a l i z a t i o n f i n a l l y , i i lo r d e rt ov a l i d a t et h em e t h o d w ei m p l e m e n tt h ep r o p o s e da l g o r i t h m s a n de x p e r i m e n to nt h ev a r i a t i o no f m e a s u r e sl i k et i m ea n dv o l u m e o f p r o c e s s e ds t a t e s a se x p e c t e d ，t h eo p t i m i z a t i o nm e t h o dc o u l di m p r o v et h ee t lw o r k f l o w 们t l lah j 曲 p e r f o r m a n c ew h e nt h en u m b e ro f a c t i v i t i e si si nac e r t a i ns c a l e k e y w o r d s ：e t lw o r k f l o wm o d e l i n g ，e t lw o r k f l o wo p t i m i z a t i o n , t i m ec o s tm o d e l ， s t a t es p a c e ，d a t ai n t e g r a t i o n , d a t aw a r e h o u s e 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的研究 成果。其他同志对本研究的启发和所做的贡献均已在论文中做了明确的声明并表 示了谢意。 作者签名：了夕啊日期：即“口 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此 规定。 作者签名： 导师签名：日期：力阳7 j ；口 丁硎兰泐陟 上海师范大学硕士研究生学位论文e 化工作流的建模及优化 第一章绪论 1 1 项目背景 近年来随着市场竞争的进一步激烈化，企业对决策支持系统的依赖性越来 越大，纷纷要求建立数据仓库来存储决策所需的数据。数据仓库的建立过程一 般如下：首先进行数据仓库的设计，然后进行数据的采集、转换和清洗，并将 有效的数据保存在设计好的数据仓库当中，最后是进行深入的数据挖掘和决策 分析。数据仓库中的数据来自于各种不同的业务系统，需要从各个业务系统数 据源中抽取原始数据，然后经过清理、转换、集成、聚集等一系列的处理，最 后将产生的决策数据加载到数据仓库中口2 l 。这个数据的选择、抽取、加载和刷 新过程被称为e t l ( e x t r a c t , t r a n s f o 衄a n di o a d ) 过程。 f r l 过程的实施是整个数据仓库系统开发实施中最重要的部分。据统计， 整个数据仓库系统开发中7 0 左右的时间和工作量都花费在e t l 过程的设计和 实施上l 。e t l 过程是整个数据仓库系统实施的关键，因为数据仓库中数据的 正确性和有效性需要e t l 过程来保证。e t l 过程的正确与否关系到数据仓库的 可用性。 通过在上海惠普有限公司、e b a y 软件工程( 上海) 有限公司和闵行统计局 的调查研究，作者认识到了数据仓库技术的发展，了解到数据抽取、转换和装 载的重要性，并认识到目前数据仓库技术实施所存在的问题。 首先，目前在企业或者统计部门都存在大量的历史数据，这些数据对企业 或地区的发展决策是非常有帮助的，正确、合理地使用和分析这些数据将会带 给我们很大的利益。但是，这些数据的来源不一样，数据格式和存储方式等等 也有很大的差异，数据质量不能得到保证。针对这种情况，企业和统计部门都 在进行数据集成等工作。 其次，要将这些数据正确地集成起来，存放在统一的数据库中，为我们的 分析作贡献，就必须采用e t l 技术。通过参与大型企业数据仓库的实施工作、 阅读文献资料和相关的信息，作者了解到e t l 技术在国内外的发展水平，并认 识到现在e t l 技术存在一些问题。比如，一些e t l 工作流逻辑太复杂，数据量 太大，在实际执行的过程中会消耗大量的时间，导致无法在规定的时间内完成 数据的集成，并造成大量的文件堆积。再比如，e t l 的执行时间无法估算，常 常会影响e t l 开发部门与客户之间的服务协议( s l a ) 的制定与实施。 所以，在数据仓库技术越来越成熟的今天，如何提高e t l 工作流的工作效 率，如何有效地估算e t l 工作流的执行时间，使得我们设计出的e t l 工作流具 有更高的可控性将越来越重要。 上海师范大学硕士研究生学位论文e t l 工作流的建模及优化 1 2 国内外研究现状 国内数据仓库的应用起步较晚，其应用范围主要集中在金融、证券、电信 等少数行业中，且大多数由国外数据仓库产品所垄断。国内一些大学对数据仓 库有些研究，如哈尔滨工业大学开发的并行数据仓库管理系统p d w m s 、南京 大学开发的数据仓库原型系s o f t b a s e w a r e 、华中科技大学数据库与多媒体技术 研究所开发的原型系统d md w 。 国外数据仓库已经得到大规模的应用，几乎每个数据仓库厂商都有自己的 e t l 系统，市场上己经存在许多比较成熟的商用e t l 系统。典型的商用系统有 m m 的v i s u a lw a r e h o u s e ，o r a c l e 9 i 的o r a c l ew a r e h o u s eb u i l d e r , m i c r o s o f t 的 d t s ，i n f o r m a t i c ap o w e r c c n t e r 等。 概括和归纳这些工具所提供的功能包括：1 ) 识别多种数据源；2 ) 抽取数 据；3 ) 定义数据流动和转换的实施方式：4 ) 定义工作流，控制逻辑流程；5 ) 任务调度，监控和报告异常；6 ) 在d w 和数据集中衍生数据；部分工具还有数 据质量和清洗的功能，提供基于业务规则和数据库规则清洗数据集结果。使用 这些e t l 工具能够快速地构建一个j o b 来处理某个数据，这些工具给数据仓库 工程实施带来了很大的便利性。 针对e t l 工作流的建立，国内外都有一些关于e t l 活动和工作流建模方面 的研究：文献 1 6 】讨论了一种用图来表示e t l 活动的方法；文献【1 7 】基于e t l 活动的通用模型，设计了一种描述e t l 场景的基本框架；文献【4 】 5 】 6 】介绍了 几种e t l 工作流的概念建模的方法；文献【3 】讨论了如何将e t l 工作流的概念 模型映射到逻辑模型；文献【2 3 】介绍了一种e t l 过程建模的方法；还有很多的 文献介绍了e t l 实现的多种框架和方法。 这些研究主要针对的是e t l 工作流的建立和实施，对于开发出的e t l 工作 流的执行时间和效率并没有很深入的研究和阐述a l k i ss i m i t s i s ，p a n o s v a s s i l i a d i s 等在2 0 0 5 年第2 1 届i c d e 会议上首次提出e t l 优化问题，揭开了 e t l 技术研究的一个新的篇章，文献 1 1 1 2 1 1 4 讨论了e t l 工作流优化的一些概 念和方法。 1 3 论文的主要工作 本文主要研究了以下几方面的内容： 1 对已有的e t l 活动的通用模型进行改进 在对e t l 活动的通用模型研究的基础上，本文提出了对该通用模型的一些 改进，以使之能够适用于工作流的优化方案；在对e t l 活动建模的过程中，还 引入一元线性回归分析的方法，来分析预测i t l 活动的执行时间，为优化方案 中的时间成本模型提供数据基础。 2 上海师范大学硕士研究生学位论文 e 亿i 作流的建模及优化 2 对e t l 工作流以及工作流优化问题进行建模 要对e t l 工作流进行优化首先需要建立适合优化的模型，本文用图、状态 和状态空间来对e t li 作流和工作流优化问题进行建模，将每个工作流看成一 个状态，采用交换、因式分解等转换方法来构建状态空间，深入研究了几种可 以用于状态转换的方法，并详细介绍了其实现的条件和算法。 3 实现对e t l 工作流的优化 本文用状态空间搜索问题来描述e t l 工作流的优化问题，并提出时间成本 模型，以e t l 工作流的执行时间为优化的标准，采用状态空间搜索算法实现对 e t l 工作流的优化。通过优化，减少e t li 作流的执行时间，并估算出工作流 的执行时间。 4 实验分析e t l 工作流优化方案的有效性 为了分析e t l 工作流优化方案的执行效率和有效性，本文进行了有针对性 的实验，通过记录和分析实验数据，分析了e t li 作流优化方案的执行效率和 有效性。 1 4 论文的创新点 论文的创新点如下： ( 1 ) 运用统计分析方法对e t l 活动模型中的时间参数进行预测； ( 2 ) 把每个e t l 工作流看作一个状态，引用交换和分解因式等方法对状 态进行转换，将e t l 工作流的优化问题转换成为状态空间搜索问题； ( 3 ) 提出时间成本模型，作为优化的标准，借鉴关键路径的思想计算e t l 工作流的执行时间； ( 4 ) 将状态空间搜索的方法应用于e t l 工作流的优化。 1 5 论文的内容安排 第1 章为绪论。讨论了项目背景意义、国内外研究现状和本文的主要研究 目标。 第2 章为数据仓库与e t l 知识的介绍。主要介绍了数据仓库的环境和体系 架构，论述了e t l 在数据仓库中的重要地位，并详细介绍了e t l 的一些相关知 识； 第3 章为e t l 活动模型的建立。主要介绍了现在比较成熟的e t l 活动的通 用模型，以及在此基础上对该通用模型进行的改进使得它能够应用与本文中 的算法，并且，引入了一元线性回归分析方法，介绍了该统计分析方法在e t l 活动的执行时间估算中的应用； 3 上海师范大学硕士研究生学位论文 e t l 工作流的建模及优化 第4 章为e t l 工作流及优化问题的建模。介绍了本文的算法中e t l 工作流 的模型，并对e t l 工作流优化问题进行建模，为使用状态空间搜索算法对工作 流进行优化作准备； 第5 章为e t l 工作流的优化。主要介绍了e t l 工作流优化中所使用的时间 成本模型，状态签名的定义，以及状态空间搜索算法的实现； 第6 章为系统测试。设计了一个测试方案对e t l 工作流优化方案进行测 试，并通过测试结果分析说明该优化方案的有效性； 第7 章为总结。总结本文的工作总结及进一步的工作： 最后是参考文献和致谢。 4 上海师范大学硕士研究生学位论文 e t l 工作流的建模及优化 第二章背景知识 2 1 数据仓库 数据仓库是联机操作处理( 0 l t p ) 数据库随着决策支持系统( d s s ) 的发展 而产生的一种全新技术。数据仓库之父b i l l i n m o n 给数据仓库下了一个定义， “是面向主题的、集成的、稳定的、随时间变化的数据集合，用以支持经营管 理中的决策制订过程”。它要从大量的事务型数据库中抽出数据，通过清理、 转换，形成统一的存储格式，给最终用户特别是决策支持者提供对数据的访问 支持。决策支持需要将来自异种源的数据统一( 聚集和汇总) ，产生高质量的、 纯净的和集成的数据；决策支持还需要历史数据。数据仓库的最终目的是通过 把原始的业务数据转换为策略性的业务信息来支持对业务的决策分析。数据仓 库的组织管理方式决定了它有别于传统数据库，是面向主题的数据集合，根据 需求将数据组织成一个完备的分析领域，用来支持决策分析的功能。 2 1 1 数据仓库体系结构 数据仓库不仅仅是充当决策支持系统数据模型的物理实现，存放企业战略 决策所需信息，同时更多的被看作一种体系结构，将异种数据源中的业务数据 集成在一起，支持决策的专门查询和分析报告以及决策的制定。 一信息源o+ 一信息提取、存储 k 一信息应用 f 习 i 业务系统i l 、 数 0 7 6 5 ，故活动的执行时间与输入的数据量有高度的线性关系。 2 1 兰兰! 苎燮圭! 窒竺兰竺兰苎 ! 兰三堡堕竺竺堡墨垡些 ( 神 ( e j x x x ( d ) 图3 6 相关系数 3 4 小结 x 本章主要介绍了本文中的e t l 活动模型。首先介绍了e t l 活动的通用模 型，然后对该通用模型进行了改进。另外，为给本文中的时间成本模型提供基 础数据，在e t l 活动的模型中加入了时间成本属性，还引入了统计回归分析的 方法，分析活动的执行时间与输入的数据量之间的关系。 上海师范大学硕士研究生学位论文e t l 工作流的建模及优化 第四章e t l 过程及优化问题建模 介绍了e t l 活动的模型，本章将继续介绍e 几工作流优化方案中建模的其 他工作，包括e r 几工作流的建模以及f 几工作流优化问题的建模。 4 1e t l 工作流建模 关于工作流的建模已经有了很多相关的研究，比如用图形的方法1 7 】【8 】、用 u m l 9 i 1 0 1 ( 统一建模语言) 对工作流进行建模。本节我们将研究e t l t 作流的 建模。一个e t l 工作流可以用一个有向的无环图来描述，如图4 一l ，就是一个图 形化的e ，r l 工作流。图的节点由活动和记录集组成。记录集可以是任意的数据 存储。目前有两种比较流行的记录集，即关系型表以及记录文件。图的边表示 数据输入输出关系：一条边从节点n l 指向n 2 表示1 1 2 接受从n 1 来的数据并做相应 的处理。在这样的情况下，我们把n l 叫做数据提供者，n 2 就是数据消费者。 这样的图有下面的两种情况： 1 ) 两个提供者都是活动( 以一个管道的方式联合起来) ； 2 ) 活动和记录集相互交互，记录集可以是数据提供者也可以是消费者。 图4 1 一个e t l 二e 作流不例 假设，有一个活动的有限集合a ，一个有限的数据集的集合r s ，以及一个供 给关系的有限集合p r 。那么，个e t l 工作流就是一个有向无环图( d a g ) ， g ( v ，e ) ，其中矿= a u r s ，e = p r 。g ( v ，e ) 可以进行拓扑排序，所以，其唯 一的执行顺序可以作为其唯一的标志。工作流的所有活动都必须有一个提供者 和一个消费者( 可以是另一个活动或者一个数据集) 。每个输入s c h e m a 都只有 一个提供者( 对于同一个消费者的多个提供者都由u n l 0 n 活动获得) 。 上海师范大学硕士研究生学位论文 e t l 工作流的建模及优化 图4 - 2e t l i 作流模型 幽4 - 3e t l 工作流示例模型 根据以上的描述以及在3 2 节中介绍的活动的模型，我们可以设计出e t l 工 作流的类图，如图4 2 所示。每个状态( s t a t e ) 由多个节点( n o d e ) 组成，其 中属性n u m 表示节点的个数，属性s i g n a t u r e 表示该状态的签名( 详细描述见 4 3 2 ) ；一个节点可能是一个数据集( r e c o r d s e t ) ，或者是一个活动 ( a c t i v i t y ) ，可以通过节点的属性n o d e t y p e 来区分，i d 用来唯一标志一个节 上海师范大学硕士研究生学位论文 e t l 工作流的建模及优化 点，p r e n o d e s 和n e x t n o d e s 属性分别记录节点的前驱节点和后续节点，可以表示 出节点之间的关系，即一组有向边的；每个数据集都有一个名称，数据集的属 性o u t s c h e m a 表示该数据集包含的数据的s c h e m a ，r o w c o u n t 表示数据集的数据 量，通常表示数据的行数；活动的描述详见3 2 节。根据图3 3 中的工作流，可 以得到如图4 - 3 中的工作流模型。 4 2e t l 工作流优化问题建模 4 2 1e t l 工作流优化问题描述 我们用状态空间搜索问题来描述e t l 优化问题。 状态：每个状态s 就是一个在4 1 部分描述的图，即状态就是e t l 工作流，所 以，在本文中我们可以认为“状态”和“e t l i 作流”是相同的意思。 转换：转换t 是用来产生新的等价状态。在这里，等价状态的意思是指那些 有相同输入就会有相同输出的状态。实际操作过程可以通过下面几个方式实 现： 1 通过交换状态中的活动的顺序，即按照执行顺序交换工作流中的两个活 动 2 用一个等价的任务来代替原来并行操作的相同的任务 3 把工作流中的某个任务克隆后，分配到并行的工作流中执行，然后再与 连接工作流组合起来 我们用符号s l - 丁( s ) 来表示从状态s 到s 的转换。如果一个状态已经被用 来生成了其他的一些等价状态的话，我们就说该状态已经被访问了。 状态空间：一个状态s 的有限集合，该集合的元素包括状态s ，以及由状态s 经过转换生成的等价状态。用符号q 表示状态空间，那么q = s ，r ( s ) ) ，其中t 表示所有可能的转换。 本文主要涉及的对状态的转换主要有交换、因式分解、分布执行、合并和 分解等，简单描述如下： 交换：交换可以用于交换一对一元的活动a l 和而的执行顺序，即 可以交换这两个活动在图中的位置( 如图4 4 a ) 。交换只考虑一元的活 动，如，选择，检查空值，主键约束，排除，函数应用等活动。可以用 符号s w a ( a 1 ，) 来表示交换活动q 和啦的执行顺序。 因式分解：因式分解主要针对一个二元的活动，如，u n i o n ， j o i n ，d i f f e r e n c e 等，在该二元活动之前至少要有两个操作相同的一元 活动( 它们分别作用于不同的数据流，但最后会合并到前面提到的二元 活动中) 。如图4 4 b 所示，在图的上面一部分中，活动口l 和口2 的操作 上海师范大学硕士研究生学位论文 e t l 工作流的建模及优化 是相同的，它们作用于不同的数据流，但是它们最后将会聚到活动以。 因式分解方法就是用一个新的活动a 来代替活动a i 和岛，放在活动巩的 右边。用f a c ( a b ，a ，a ：) 来表示因式分解法。 分布和因式分解是互逆的两种转换。如果有两个活动对不同的数据 流进行同样的操作，最后合并到一起的话，我们就可以运用因式分解的 方法，这样只要对合并以后的数据流进行操作。由此我们可以知道，如 果一个活动对某一个单一的数据流进行操作，我们可以将数据流分解成 为多条不同的数据流。大家可能注意到从本质上来说因式分解和分布的 方法其实就是一元活动和二元活动之间的转化。我们用d i s ( a 。，口) 来表示 分布转换。 合并和分解：这两种转换就是在不改变活动语义的基础上将两个 活动进行“打包”或者“解包”。合并表示根据e t l i - 作流的限制，有些 活动必须要组合在一起。比如，在某两个活动中间不能存在第三个活 动，或者这两个活动不能被交换，那么我们认为这两个活动必须要组合 在一起操作。分解表示将一对组合在一起的活动取消组合。如，在所有 可能的转换结束后，我们可以将所有组合的活动取消组合。这样做的好 处就是在不会牺牲任何设计需求的基础上降低了搜索空间。分别用 m e r ( a 1 + 2 a i ，a 1 2 ) 和s p l ( a 1 + 2 ，q ，a 2 ) 来表示合并和分解。 交换c a 1 i 啕变换t 辞川， + 。 d ： f o cii nr a n g ec 0 ，1 1 ： c s p l i s t l a p p e n d ( s e l f n o d e s a 1 p t e n o d e a i i a c t i v i t y o u t s c b e ) 协p l i 5 t 2 = c o m b i n e ( m p l i s t 2 ，t m p l i s t l 【i ” s e l f n o d e s 【aj e c 七i v l t y s e t i e g c h e s m a ( p l i s t l ) d t p l i s t 3 = ，l i b o 啊山i n e i u p n a t z ，s e l f n o d e s l a a c t i v i t y g e n s c h a n e ) ，s e l f r 协d a n a 1 峨i v i t y p r o c m e h e t e ) s e l f n o d e s e 1 a c t i v i t y s e t ( t s c h e m a ( 乜p l i 5 t 3 l 诅p l i 3 t 1 = 【】 恤p l i s t z = 【】 乜p l i s t 3 = 【】 图4 5 生成s c h e m a 算法 原则上来说，整个状态的活动都需要重新计算s c h e m a ，因为可能有的输出 s c h e m a 会作为多个消费者的提供者( 也就是说，在模型中表示活动的节点可能 有多条输出的边，分别指向其他活动或者记录集) 。但在该工作流的拓扑排序 过程中包含了一个很明显的剪枝：在该方法中，每次转换后我们都只要检查修 改活动之后的部分( 按拓扑顺序) 。另外，在下面这种情况下，我们也不需要 做那么复杂的计算，即当所有的活动都只有一个输出，每一个输出s c h e m a 都只 有一个消费者，那么受到转换影响的将只有转换涉及到的活动，其他的部分都 不受影响。在这种情况下，我们就不需要对整个状态应用该算法，我们只要对 状态中受到影响的子图进行重新计算。 上海师范大学硕士研究生学位论文e t l 工作流的建模及优化 4 3 3 线性组和相似活动 在这里我们还要介绍一下线性组和相似活动的概念，本文用线性组的概念 来划分活动主要是为了形成一个线性的执行路径，用相似活动将处于不同的线 性组但是做相同工作的活动组织在一起。 线性组：一个线性组就是一个图( 状态) 的子集，它的元素将一元 活动组成一个线性的路径。如图4 - 1 ，状态的线性组就是： 3 ，4 ，5 ，6 ，7 ) ， 8 ，9 ，1 0 ，1 1 ，1 2 以及 1 4 ) 。 相似活动：如果两个活动满足下面的条件，这两个活动就称为相似 活动： 1 ) 它们处于收敛的线性组； 2 ) 它们有相同的语义( 即同一个语义表达式) ； 3 ) 它们拥有相同的操作，生成和排除s c h e m a 。 比如，我们来看图4 6 中的e t l 工作流，其中包含的一个活动就是将数据从 两个数据源 e s l ( 旦堡匕丛丝墼q 仃r ，c o s t ) 和 r s 2 笆丝巨! 二，竖堕堡丝，q t y ，c o s t ) 填充到目标数据集 r s 3 ( 婴，s o u r c e ，q r r ，c o s t ) 中。在该状态中，两个代理主键活动( 3 和 4 ) 就是相似活动，因为它们都是在收敛的线性路径上，有着同样的代数表达 式，有同样的操作s c h e m a e k e y ，s o u r c e ，生成s c h e m a s t a i r 以及排除 s c h e m a p k e y 13 图4 6e t l 工作沉不例 4 3 4 转换的条件与实现 根据前面的介绍，可以知道对某个状态实施一定的交换后，会提高e t l i 作 流的工作效率，但到现在为止还没有提到实施这些交换的条件，即需要定义 定的规则来确定是否允许对某个状态进行某个转换。我们之所以在介绍了 s c h e m a 生成算法之后再介绍限制条件是因为转换的正确性与s c h e m a 生成的正确 性息息相关。 3 0 上海师范大学硕士研究生学位论文 e t l 工作流的建模及优化 4 3 4 1 交换的条件与实现 我们先举正反两个例子。首先，假设出现如图4 7 中的情况，活动喁将c o s t 属性从美元转换为欧元，而它的消费者，活动岛则只选择其中超过1 0 0 欧元的 数据。很明显的，我们不能盲目的将这两个活动交换。但是，如果有函数存在 就不允许交换的话，实际上就可能会阻止了许多的有用的转换操作，因为e t l 3 1 作流有很多都是与函数相关的( 大部分都是算术和字符串的处理) 。例如，考 虑图4 8 的情况，活动口l ( a 2 e ) 将日期属性从美国的日期格式转换成为欧洲的日 期格式，活动a 2 ( g d a y ) 将某一个日期( 如t h u r s d a y ，n o v1 3 ，2 0 0 3 ) 中的一 部分( 如t h u r s d a y ) 解析出来，并生成一个新的属性d a y 。在这种情况下交换就 是允许的。 a 1a 2 a 2 a l 图4 - 7 交换的条件 因此，活动q 和啦只有在满足了下面的条件时，才允许交换： 1 q 和色在图中相邻( 不失一般性，我们可以假设q 是啦的提供者) 2 q 和q 都只有单一的输入输出s c h e m a ，并且它们的输出s c h e m a 都只有一个 消费者 3 a 。和呸的操作s c h e m a 都只是它们的输入s c h e m a 的子集( 在交换前后都满 足) 4 q 和，的输入s c h e m a 都是它们的提供者的子集( 交换前后都必须满足) 条件1 和2 是简单的估算空间搜索和命名生成复杂度的方法。另外两个条件 覆盖了两种可能的问题。条件3 覆盖的问题如下，如图4 7 ，活动皿将美元转化 成为欧元，其输入属性为d o l l a r _ c o s t ，所以操作s c h e m a 中包含d o l l a r _ c o s t ， 其输出属性为e u r o _ c o s t 活动吒同时需要在其操作s c h e m a 中包含e u r o _ c o s t ( 如，它找出所有c o s t 大于i 0 0 欧元的) 。如果某个交换将活动口：放到了口1 之 前，那么该交换将会被拒绝。s c h e m a 生成算法将按从源到目标的顺序分配属性 3 l 上海师范大学硕士研究生学位论文 e t l 工作流的建模及优化 名称，然后，巩的属性将会变成d o l l a rc o s t ，所以操作属性e u r o c o s t 将不会 出现在活动的输入s c h e m a 中。 如果设计人员给活动q 和4 2 的操作s c h e m a 中的属性名字相同，那么条件3 的防护就很容易被破坏了。如，假设设计人员用c o s t 代替d o l l a r _ c o s t 和 e u r oc o s t 的话，那么条件3 就不会被触发。为了解决这个问题，我们采用了在 4 3 1 中描述的命名规则。 而图4 8 的例子，活动q 和啦在本文中就是是可以交换的，因为在它们的 输入输出s c h e m a 中有相同的属性d a t e 。 a 1a 2 图4 - 8 交换的条件 第二个问题，就是条件4 覆盖的问题就比较简单了。假设活动啦是一个刀。 ( 排除) 活动，在它的输出s c h e m a 中丢弃了一个属性( 如图4 9 ) 。这样，交换 就会出错，因为如果交换了，那么在活动口l ( 现在成为了活动呸的消费者) 的 输入s c h e m a 中的被丢弃的属性在活动风的输出s c h e m a 中就没有提供属性。显 然，我们就在执行分配s c h e m a 的算法时就会遇到问题。 a 1a 2 a 2 a 1 图4 9 交换的条件4 3 2 上海师范大学硕士研究生学位论文e t l 工作流的建模及优化 根据本节中的限制条件以及4 2 2 中对转换的形式化描述，我们可以设计出 转换操作的流程图，如图4 1 0 。 图4 - 1 0 交换的流程图 4 3 4 2 因式分解和分布的条件与实现 如果有一个活动a 以及两个操作语义完全相同的活动q 和口，并r a ，和4 ， 完成后其数据流将会聚于a ，我们就可以将它们进行因式分解。因式分解必须 满足下面的条件： 1 活动q 和4 2 从代数表达式的语义上来说是同样的操作，唯一不一样的就 是它们的输入( 输出) s c h e m a 2 活动q 和啦有共同的消费者，假设为，它必须为一个二元的操作 ( 如，合并或者差分) 显然，活动q 和口2 将从图中删除，并用一个新的活动口来代替，后面还要 接上活动。换句话说就是，对于任意节点x 相关的边( x ，a 。) 和( 工，啦) 都会变成 ( x ，嘞) ，边( 口。，) ，( 4 ：，) 将被删除，节点口1 和口2 被删除，加入新的节点口和 新的边( a s ，a ) ，对于任意节点y 相关的边( a s ，y ) 都变成( 口，y ) 。 分布的条件是类似的，一个活动a 只有在满足下面的条件才可以被克隆出 两个活动a i 和巩，然后分布到两条路径中执行： 1 有一个二元的活动作为活动口的提供者，而两个复制生成的活动q 和 口2 将指向活动吼 2 口和口：从代数表达式上来说与活动口的操作是相同的 3 3 上海师范大学硕士研究生学位论文e t l 工作流的建模及优化 很自然的，活动a 将从图中删除。节点和边的处理其实就是提取的逆操 作。 根据这些限制条件以及4 2 2 中对转换的形式化描述，我们可以设计出因式 分解和分布操作的流程图，如图4 1 1 以及4 1 2 。 合并和分解：合并不会造成很大的问题。新的活动的输出s c h e m a 是第二个 活动的输出s c h e n l a ，它的输入s c h e m a 就是相关活动的输入s c h e m a 的并集减去与 第一个活动相连接的活动二的输入s c h e m a 。分解要求起始活动为一个组合活 动，如a + b + c ，这样，它就可以被分解成为两个活动如口和5 + c 。 ( 开始 ) 二工二 获得初始状态s o 及活动a 1 。a 2 a b 王 1 用相似活动a 代替活ll 动a l ，a 2 得状态s 1生 1 一 l 不能因式分解， 为状态s 1 生成i 输出错误信息 i 所有s c h e m al 输出状态s 1 l 堡j 图4 1l 因式分解转换的流程图 4 4 小结 i 获得初始状态s o l l 及活动a b a 幺孓一 弋驴 y l 克隆a ，生成活l 动a 1 a 2 1 l 用相似活动a 1 a 2 代 不能分布，输出 i 替活动a 得状态s 1 错误信息 l 为月| 状；f i 态s c s h l e 生m 成a t l 输出状态s ， r 结束、 图4 - | 2 分布转换的流程图 本章主要讨论了e t l 工作流以及工作流优化问题的建模。首先，我们提出了 e t l - 1 - 作流的模型，并举例说明；然后对优化问题进行了深入的研究，我们将每 个e t l 工作流看成一个状态，并通过交换、因式分解和分布等操作实现状态的转 换，所以我们详细地介绍了这些转换以及实现转换的必要条件。 在状态转换的过程中，需要修改活动的s c h e l 诅，所以本章还介绍了为状态 自动生成完整的s c h e m a 的算法。另外，为了解决状态转换和生成中的一些问 题，我们还提出了属性的命名规则以及线性组和相似活动的概念。 上海师范大学硕士研究生学位论文 e t l 工作流的建模及优化 第五章e t l 工作流的优化 在前面两章中，我们主要介绍t e t l _ t _ 建模问题，包括活动和工作流 的建模。本章我们将着重介绍e t l 工作流的优化问题，如图5 1 中的虚线部分， 它是建立在前面工作的基础之上的。 网愿e t l t f 丽丽一丽 e 1 1 - 活 动炎幽 断燮壹适j 图5 - 1 主要工作结构图 5 1 状态签名定义 在交换的过程中，我们必须注意状态之间彼此的差异以避免同一个状态的 重复产生。正如前面提到的，一个状态就是一个有向图，但是，它还有一些其 他的限制：1 ) 它有一些源节点( 源数据集) 2 ) 一些目标节点( 目标数据集) 3 ) 它可以在提供者一消费者关系的基础上进行拓扑排序从而可以给每个活动分 配一个唯一的执行优先级。 基于上面所说的，我们可以很容易地为每个活动分配一个辨识结构，即： 1 ) 每条线性的路径都由一个用点作为分隔符的字符串 2 ) 并行的路径用双斜线分隔 我们把这样的描述每个状态的字符串叫做状态的签名。1 。并行的路径之间 的顺序要注意，必须将起始标志最小的路径放在前面。 如图4 - 1 中，我们给工作流的每个元素都分配了一个唯一的标志，其签名就 是( ( 1 3 4 5 6 7 ) 1 1 ( 2 8 9 1 0 1 1 1 2 ) ) 1 3 1 4 1 5 。圆括号里面