（计算机应用技术专业论文）etl执行过程的优化研究.pdf

摘要 摘要 e 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 ) 是构建和维护数据仓库的基本构件。由丁二它处理的 是海茸数据，如何加快响应时间成为值得研究的问题。大多数的e t l 商业一i ：具提供设计和管理e t l 工作流的f 具但不采用任何优化措施。设计好的e t l i 作流交给d b m s 执行，由d b m s 完成优化任 务。但e t l 过程不能仅作为一个大的查询交给数据库去处理，在e t l 过程中各个活动相互关联全局 优化是必须考虑的。 本文对e t l 过程的逻辑优化进行了研究。对e t l 工作流进行了形式化定义，介绍了状态等价变 换的转换规则，状态变换过程的模式产生，转换规则的适用性。工作流的等价性判定规则。e t l 工 作流的优化问题可建模成状态空间搜索问题：一个e t l 工作流可看作一个状态图对每个状态图采 用状态变换产生所有可能的等价状态图，从中找出代价最小的状态圈即为最优e t l 执行过程。并提 出了一个e r l 优化体系结构。 论文给出了获得最优化e t l 过程的算法，首先通过穷举法对状态空间进行完全搜索来获得代价 晟小的e t l1 = 作流。接卜来介绍了启发式算法和贪婪法米减少搜索的状态空问。并通过一系列实验 结果论证了算法的有效性。 本文最后设计了基f 统计的优化器代价模型。给出各种操作活动的代价估算方法和估算所需的 统计数据，并具体给出收集所需统计数据的脚本。最后结合操作活动的谓词属性的特征对复杂的统 计数据管理工作进行了简化，提出一种快捷的统计数据的管理方法。 关键字：e t l ，工作流，优化，代价模型。基f 统计的优化器 东南大学碗 学位论文 a b s t r a c t e t li sat o o lr e s p o n s i b l ef o rd a t al o n d i n ea n dm a i n t a i n i n go fd a mw a r e h o u s e h o w t oe 1 爵c i a n f l y s h o r t a nt h ee x e c u t i o nt i m ej sab i gc h a l l e n g e , b e c a u s et h ev o l u m eo f d a t at ob ep r o c e s s e di sv e r yl a r g e s o f a r , i e a d i n gc o m m e r c i a it o o l sa l l o wt h ed e s i g no fe t lw o k f l o w s b u td on o tu s ea n yo p t i m i z a t i o n t e c h n i q u e 1 1 ed e s i g n e dw o r k f l o w sa r ep r o p a g a t e dt ot h ed b m sf o re x e c u t i o n ；t h u st i l ed b m s u n d e r t a k e s t h et a s ko f o p t i m i z a t i o n a oe t lp r o c e s sc a nn o tb ec o n s i d e r e d 丛ab i gq u e r y i nt h ep r o c e s so fe t le a c h o f a c t i v i t yi sr e l a t e d s ot h ew h o l eo p t i m i z a t i o nm u s tb ec o n s i d e r e d 1 nt l l i sp a p e r , w ed e l v ei n t ot h ei o g i c a lo p t i m i z a t i o no fe t lp r o c e s 蠕f i r s tw eg i v eaf o r m a l d e f i n i t i o no f t h ec o n s t i t u e n t so f 卸e t lw o r k f l o w t h 朗w ed e f i n e das e to f t r a n s i t i o n st h a tc a nb ea p p l i e d t ot h es t a t e s w ea l s op r o v i d ed e t a i l so nh o ws t a t e sa r eg e n e r a t e d t h ec o n d i t i o n su n d e rw h i c ht r a n s i t i o n s a 陀a l l o w e da n dt h ed e t e r m i n a n tr o l e so f e q u i v a l e n tw o r k f l o w s s ow es e tu pt h et h e o r e t i c a l e 、v o r kf o r t h ep r o b l e m ，b ym o d e l i n gi ta sas t a t e - s p a c es e a r c hp r o b l e m ，w i t he a c hs t a t eg r a p hr e p r e s e n t i n gap a r t i c u l a r d e s i g no ft h ew o r k f l o wa sag r a p h ，e q u i v a l e n tw o r k f l o w sa r ep r o d u c e df r o ms t a t et r a n s i t i o n s 。t h es t a t e s p a c e j s f a b r i c a t e d t h r o u g h a s e t o f c o i t e c ts t a t e t r a n s i t i o n s a n d t l l e m i n i m i z a t i o n o f t h ee x e c u t i o n c o s t o f a n e t lw o r k f l o wi st h eb e s to g l e m o r e o v e r , w ep r o v i d ea l g o r i t h m st o w a r 出t h em i n i m i z a t i o no ft h ee x e c u t i o nc o s to fa ne t l w o r k f l o w f i r s tw eu s ea l le x h a u s t i v ea l g o r i t h mt oe x p l o r et h es e a r c hs p a c ei ni t se n t i r e t ya n dt of i n dt h e o p t i m a ie t lw o r k f l o w t h 朝w ei n t r o d u c eg r e e d ya n dh e u r i s t i cs e a r c ha l g o r i 椭m st or e d u c et h es e a r c h s p a c et h a tw ee x p l o r e , a n dd e m o n s t r a t et h ee 衔c i e n c yo f t h ea p p r o a c ht h r o u g has e to f e x p e r i m e n t a lr e s u l t s a ti e s t , t h er e a l i z a t i o nt e c h n o l o g yi sp r o v i d e da b o u tt h eo p t i m i z e rc o s tm o d e ib a s e do ns t a t i s t i c s w b p r o v i d et h ec o s te s t i m a t em e a s u r eo fd i 虢r e n ta c t i v i t i e s t h es t a t i s t i c st h a tt h ec o m p u t i n gn e e d s , t h es o d p t t h a lc o l l e e t ss t a t i s t i c sd a t an e e d e d , a n dp r e d i g e s tt h em a n a g e m e t a to ft h es t a t i s t i c sd a t ac o m b i n e dw i t ht h e c h a r a c t e d s t i co ft h ep r e d i c a t i o na t t r i b u t eo fa c t i v i t i e s f i n a l l y , w ep r o v i d ea ns h o r t c u tm a n a g e m e n tm e t h o d o f t h es t a t i s t i c sd a t a k e y w o r d ：e t l ，w o r k f l o w , o p t i m i z a t i o n , c o s tm o d e l ，s t a t i s t i c sb a s e do p t i m i z e r 东南大学学位论文 独创性声明及使用授权的说明 一、学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果尽我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意 签名：罢叁红，日期：! ：堡：! 二、关于学位论文使用授权的说明 东南大学、中国科学技术信息研究所、田家图书馆有权保留本人所送交学位论文的复印件和电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相 一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全都或部分 内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。； 签名：塞选红导师签名：主盔囊曲日期：，_ j 牛 第章引言 1 1 研究背景 第一章引言 数据仓库作为一种数据密集型应用，由两部分构成：静态部分和动态部分。静态部分是指数据 仓库的体系架构和实例数据；动态部分是构建和维护数据仓库的各种进程，负责加载、刷新等，这 主要由e m 工具完成的。e t l 负责将分布的，异构的数据源数据 增加了元数据版本控制功能，有效跟踪数据转换开发流程： 简化了软件部署和元数据发布t = 作，使e t l ，f 具更易于使用； 元数据存储管理的规范化方便了e t l 工具的设计、开发。 2 4e t l 过程图形化描述 在e 1 l 过程逻辑描述设计中，最好采用图形化的描述方式来描述e 1 r l 过程，s e ue 1 乙中提供 一套图形化描述机制来描述数据的转换过程，使用不同的图标表示e t l 过程逻辑描述中的数据转换、 记录集、关联等概念。 使用图形描述数据从数据源通过一系列的数据转换，最终加载到数据仓库中。e t l 过程图g 代e ) 中节点v 是：数据存储源s ，记录集对象r ，关联对象a ，数据转换对象t ；节点之间的关系包括： 数据集和转换对象之间的数据提供关系p r 、记录集和数据存储源之间的部分关系p o ，数据集和关联 对象之间的关联关系r e 。v - - s o d u a u t ，e = p r u p o u r e 。图形符号定义为( 图2 - 4 ) ： 提供关系 教据存绪薄 l s j 记录集 。 都分关系 关联 关联关系 数据转换 图2 - 4e t l 过程图形符号定义 下图( 图2 - 5 ) 是一个详细的e t l 过程图形化描述过程。数据源s 1 和s 2 中的数据通过数据传 输，即通过网络把远程的数据文件f 1 r p 到中问层数据库( 数据准备区d s a ) 中，在d s a 中进行转 换和清洗。数据源s l 的e t l 过程为：d 1 f f l 活动对s l 中抽取来的新老数据( s 1d sn e w 和s id so l d ) 进行差异视图操作获得增量抽取数据s 1 d f ，然后进行主键冲突检查( s p k i ) 主键代替( s k i ) ， 美元到欧元转换( $ 2 e ) ，日期美国格式到欧洲格式转换( a 2 e ) 数据源s 2 的e t l 过程为：d i f f 2 活 动对s 2 中抽取来的新老数据( s 2 _ d s _ n e w 和$ 2 一d so l d ) 进行差异视图操作获得增鬣抽取数据 s 2 d f ，然后进行主键冲突检查( s p k 2 ) ，主键代替( s k 2 ) ，s 2 中的非空检查( 卜i n ) ，聚合( t ) ，选 择( o ) ，然后和数据源s l 的e t l 过程进行了合并( u ) 操作，最后数据彼加载到目标数据仓库中。 7 东南大学硕士学位论文 2 5 本章小结 图2 - 5 一个详细的e t l 过程图形化描述 本章介绍了东南大学计算机系数据库实验室自行设计和实现的通用e t l 工具s e u _ e t l 的功能 框架和各个模块：统一数据模型、e t l 的逻辑描述与执行、元数据管理和e t l 过程图形化描述，为 以f 各章的描述打下了基础。 8 第三章e t l 优化问题建模 第三章e t l 优化问题建模 原有s e u e t l 系统e t l 的执行分为设计阶段和运行阶段，设计好的e t l 过程交给e t l 调度 器进行抽取、转换、重载。这个过程本身没有采 j 任何优化措施本章通过建模提出一种对设计好 的e t l 上作流进行优化的理论框架。 3 1 问题的提出 图3 - 1 描述了从数据源s 1 和s 2 中抽取数据到数据仓库肼中的e l l 过程数据源s l 中保存记 录集p a r t s l ( p k e y ，s o u r c e ，d a t e ，c o s t ) ，记录的是每个月的生产成本数据：数据源s 2 中保存记录集 p a r t s 2 ( p k e y ，s 0 1 j r c e ，d a t e ，d e p t ，c o s t ) 。记录的是每天的生产成本数据；数据仓库佣保存记录集 p a r t s ( p k e y ，s o u r c e ，d a t e ，c o s t ) 存储备供戍商每个月各部分产品的花费。假定数据源s 1 和数据仓 库是欧洲格式，数据源s 2 是美国格式，那么从数据源s 2 来的数据要转换成欧洲格式 图3 1 一个e t l 工作流的例子 在图3 一l 中标注了每个e t l 活动的执行优先级和功能描述。源数据的优先级最高目标数据仓 库的优先级最低。数据源s l 的e t l 过程是：( 3 ) 对属性c o s t 进行非空值检查，数据源s 2 的e t l 过程是；( 4 ) 美元花费( $ c o s t ) 转换成欧元花费( e c o s t ) ，( 5 ) 日期( d a t e ) 从美国格式转换成欧 洲格式，( 6 ) 对每个月的供给进行聚合，剔除掉不必要的属性d e p t 。( 7 ) 在载入数据仓库前，两个 流进行了合并，( 8 ) 对e c o s t 属性进行了最后检查，确定在某个范围内的值才能放进数据仓库。 对上i 型分析存在以下问题：1 ) 能否采用传统的查询优化措施。2 ) 能否把选择操作尽可能下压 到t 作流的前端。对于s l 而言属性花费没有改变，可以将选择f 压到工作流最前端：对s 2 而言属 性花费被改变了。选择操作只能卜压剑应j j $ 旋转换函数的操作之后。3 ) 能否在美元剑欧元转换之 前执行聚合操作。在上图中将聚合操作f 压剑$ 2 e 函数操作之前可减少转换操作的i ：作鼍。 圈3 - 2 显示了图3 - 1 中的l 作流被转换成完成相同任务的等价_ 亡作流。对欧元的选择操作被放在 工作流的两个分支的前面，这样选择范围外的值提前被剔除掉；但是由1 二是对属性欧元花费进行过 滤并且先聚合可减少过滤r = 作量，依然不能把选择操作卜压n $ 2 e 转换和聚合之前；同时对聚合操作 和日期转换操作c a 2 e ) 进行了交换，从而减少转换操作的， 作量。 问题集中在：对工作流可以进行何种变换、哪些转换是合法的；为了提高效率，怎样获得最优 e 1 | l 工作流。 9 东南大学硕士学位论文 图3 - 2 一个等价的e t l 工作流 下面对e t l 工作流进行形式化定义，并对优化问题进行建模。 3 2e t l 工作流的形式化定义 每个e t lt 作流可看作一个有向无环图( d a 6 图) 。图的节点可以是e t l 活动或记录集。记录 集是能够提供扁平记录模式的数据源，比如说最常用的关系表和记录文件。图的边代表数据供给关 系或输入输出关系。由结点n i 出发进入结点n 2 的边，表示n 2 从n l 接收数据作进一步处理，此时 称n l 为数据提供者，n 2 为数据消费者。图均等地模拟了以下两种情形：1 ) 边的两个结点都是活动。 2 ) 活动和记录集相结合，既可以作为提供者，也可以作为消费者。 每个结点有一个或多个模式( 属性的集合) 。一个模式随时是另外一个模式的数据提供者，假 定这两个模式的属性间是一对多的映射( 即一个提供者属性可以对应不止一个消费者。而一个消费 者属性只能对应一个提供者) 。记录集有一个模式，活动至少有两个模式( 输入、输出) 。直观地 讲，一个活动包括一组输入模式，负责把记录集带给活动作进一步处理；一个或多个输出模式负责 把数据交给f 一个数据消费者( 活动或记录集) 。具有一个输入模式的话动称为一元活动，具有两 个输入模式的活动称为二元活动。这里川输出模式术语来表示给随后的数据消费者提供干净的、一 致的数据；用术语过滤模式表示把脏数据输出剑日志文件或清洗活动作进一步处理。 对于每一个输出模式，用一个代数表达式来表示交给各自模式的数据的语义。考虑采用扩展的 关系代数表达式，包括f 列操作符：选择( 6 ) 投影( ) ，笛卡尔积，连接w ，聚集，差， 并u ，函数应用f 。上述操作符的语义很明显。对于采_ 函数的情况，假定存在一组函数类型( 比如 算数和字符串操纵函数) ，可以通过用输入模式的属性作为输入参数，产生一个新值作为函数的返 回值，来表示函数应用f 的语义。 活动是一个四元组a _ ( i d ，i 。0 ，s ) ：i d 是活动标识符：i 是一个或多个输入模式的有限集合，从 活动的数据提供者接收数据；0 是一个或多个输出模式的有限集合；s 是一个或多个扩展的关系代数 表达式表示每个输出模式数据流的语义。 假定有活动集a ，记录集i i s ，供给关系集p r 。e t l 工作流可以看作有向无环图( d a g 图) ：g ( v ，e ) 。 v a u r s ，e = p r 。g ( v ，e ) 可以拓扑排序，因此可以给每一个活动赋值唯一的执行优先权作为活动标示 符。j l 作流的所有活动有一个提供者和消费者( 既可以是另一个活动，也可以是一个记录集) ，每 个输入模式只有一个提供者( 多个提供者对应同一个消费者的情况可以通过合并u 活动获得) 。 3 3 通过变换产生新的等价状态交换过程 e t l 工作流的优化问题可建模成状态空间搜索问题。 1 0 第三章e t l 优化问题建模 3 3 1 状态与状态变换过程 状态图：每一个e t lt 作流是一个状态图对应一个状态变换过程。( 见3 2 节) 等价状态图：两个状态图在相同输入的情况f 产生相同输出。如果用一个状态图产生由此状态 图派生的新的状态图，就称已经访问了这个状态图。 状态变换：用来产生新的等价状态图。比如交换状态图中活动的执行顺序。 接f 来引入状态图的一系列逻辑转换。表达式s ：t ( s ) 表示从状态图s 到s 的转换，这些逻 辑转换包括； 1 s w 变换：局部交换一元活动a - ，a 2 在图中的顺序，记为s w a ( a - ，) 如图3 - 3 ( a ) 这样选择 操作频率高的活动可以推到i ：作流的前端( 类似于代数优化的操作卜- 压) 。 2 f c 与d i s 变换：两个具有相同功能的一元活动处于两个不同的数据流，汇聚到一个二元 活动，f c 变换用一个新的同类一元活动放在这个二元活动之后代替上述两个一元活动； d i s 把一个活动分配到两个汇聚的数据流。这两种变换分别记为f a c ( a b ，a t ，动和d i s ( a b ，a ) 如图3 - 3 ( b ) 。f a c 与d i s 本质上是对一元和二元活动进行交换。 3 m r r 与s p l 变换：用这两个变换来组合活动和取消组合而不改变它们的语义。这两种变换 分别记为脏r ( a m ，a - ，a 2 ) 和s p l ( a m ，a - ，a 2 ) 如图3 ，3 ( c ) 组合表明一些活动可以被组合到 一起，其他活动不能插入到这些活动中来，组中的活动不能交换顺序，当状态变换完成后 可以取消组合。这样搜索空间可以大大减少。 七 书 蛳b - w a 3 3 2 引入这些变换的原因 彻眺m i n d d i s( c ) m 田m d s p l 图3 - 3 状态的逻辑变换 1 交换变换允许选择频率高的活动推向t 作流的开端，类似于传统的代数优化。 2 分解变换在于：存在某种操作，在汇聚后只执行了一次，而在汇聚前在汇聚的两个分支里各 做了一次即两次。例如某个活动可以缓存数据( 代理键分配时查找表可以被缓存) 此时采用 分解变换可以提高效率( 这种操作汇聚后再作，而且只做一次) 。 3 分配变换在于：当活动的选择频率比较高并且要下压到i 作流的前端，此时把一个活动分配 到两个并行分支里可以提高效率。选择范围外的值可提前被剔除掉。 4 组合和取消组合变换：组合意味着一些活动可以被组合剑一起，其他活动不能插入到这些活 动中来，组中的活动不能交换顺序，当状态变换完成后我 f j 可以取消组合。这样搜索空闻可 以大大减少。 3 3 3 状态变换举例 在下面图3 4 中有三个工作流，( 2 ) 和( 3 ) 对( i ) 分别进行了d i s 变换和f a c 变换。若 仅考虑每个过程的处理行数，每个工作流输入8 行，主键代替s k 代价为1 1l o g an ，选择0 代价 为n ， 0 操作处理幅度涉及5 0 的记录，其它操作处理涉及1 0 0 的记录，简化起见忽略u 的 代价。则三个状态图的总的执行代价分别为： 忪舅 东南大学硕士学位论文 8 k 1 、u 叶d 0 1 8 k l 、u 0 1 、u _ 。k s k 2 0 2 _ s k 2 ， 0 2 图3 - 4 状态变换的好处 c 1 = 2 nl 0 9 2 n + n = 5 6 ，c 2 = 2 ( n + ( n 2 ) l o ( n 2 ) ) - - 3 2 ，c 3 = 2 n + ( n 2 ) 1 0 8 2 ( n 2 i = 2 4 因此d i s 变换( 2 ) 和f c 变换( 3 ) 可以减少一个状态i 封的执行代价。 3 3 4 变换的形式化定义 1 s w a ( a i ，8 0 ：即在图g = ( v 。e ) 上交换8 l 在图中的先后次序，产生一个新图g = 姆，e ) ， 这里v ：v 。对于每个边e = ( v a - ) ，e e e ；引入e 后，边e 气v a = ) ，同样对于每个边e e e ， e 气a - ，v ) ，引入e 后，边c ；( a 2 ，v ) 。用边( a 2 ，a 。) 去代替边( a - ，a 2 ) ，图中其它部分的边保持不 变。 2 f a c ( a b ，a 一，a z ) ：即在图g = ( v ，e ) 上应用分解变换，产生一个新图g = ( v ，e ) ，在新图里 去掉结点8 ，a 2 ，给v7 引入一个新的结点a ，v - v 一 a ，a 2 u a ) ，对于每个边e e e ，一v ，a 1 ) 或( v ，a 2 ) ，引入e 后，边e 叫v ，a b ) 。对f 每个边e e ，e 鼍籼，v ) 引入e 后，边e = ( a ，v ) ， 加入边( o , b 。a ) ，图里其它的边保持不变。 3 d i s 。8 ) ：即在图g ：( v ，e ) 上应用分配变换，产生一个新图g = “，e ) ，在新图里去 掉结点a 引入新的结点a l ，a 2 ，v - v ul a i ，赴卜 a l ，去掉边( a h a ) ，对于每个边e e ，e = ( v 曲， 引入e 后，边e 却, a 0 ，e ”= ( v 8 7 ) ，对于每个边e e e ，e - = ( a ，v ) ，引入e 后，边e = 如， v ) 边e l - ( a 1 酗，e z = ，扎) ，图里其它的边保持不变。 4 娅r ( a m ，a - ，a 2 ) ：即在图g = ( v ，e ) 上应用组合变换，产生一个新图g = ( v ，e ) ，在新图 里引入新的结点a l + 2 ，v - v 一 a - ，a 2 u a l + 2 。去掉边( 8 b 却) 对丁二每个边e e e ，e 气v ，a - ) ，引 入e 后，边e 气v a m ) ，对于每个边e e e ，e 气a 2 ，v ) ，引入e 后，边e = 俑m ，v ) 。图里 其它的边保持不变。 5 s p l ( 8 m 。a ，a 2 ) ：即在图g _ ( v ，e ) 上应用组合取消变换，产生一个新图g = ( v ，e ) ，在 新图里引入新的结点a t ，a 2 ，v - - v 一 a l + 2 u a l ，a 2 ，对丁二每个边e e e ，叫v a m ) ，引入e 后， 边e 气v a ，) ，对丁二每个边e e e ，e 鼍a m ，v ) ，引入e 后，边e = ( 弘v ) ，加了一个新边e = ( a t a 2 ) ， 图中其它部分的边保持不变。 在f 表里州出了上述一系列变换的符号和含义，上图3 - 3 列出了这些变换的例子。 变换类型表达式含义 交换变换s w ( a i a 2 )交换一元活动a - ，8 2 分解变换 f a c ( 8 ba l ，a 2 )从二元活动ab ，分解出一兀活动a l ，如 分配变换 d i s ( a h ，a )参照二元活动8b 对一元活动进行分配 组合变换 m e i ( a m ，a i ，a 2 ) 合并活动a l ，a 2 产生新的活动a l + 2 取消组合变换 s p l ( a 1 2 ，a l ，a 2 ) 把活动8 m 分解成两个新的活动a l , a 2 所有等价的e t l 工作流，为了选择最优e t l 工作流需要一个合适的代价模型。 代价模型：给定活动a c ( a ) 代表a 的代价。整个状态变换过程( 状态图s ) 的代价是它所有活 动的代价和。 c ( s ) = c ( a i ) l l 最优化e t l 工作流问题就是找到一个状态变换过程s 耵一，c ( s 一) 最小。这部分内容放在第五章阐 述 接下来讨论状态变换过程的模式产生和由状态圈应用变换规则所带来的问题。 1 2 第三章e 1 l 优化问题建模 3 4 状态变换过程的模式产生 不同的状态图是自动构建的，为了构建一个e t l 工作流，要设置好每个e t l 活动的相关参数 比如输入输出模式。由丁二状态变换过程是自动构建的，因此不同活动的输入输出模式的产生也一 定要是自动的接f 来我们要解释这个创建过程怎么执行 e t l 过程有下列典型活动如表3 2 ： 1 数据过滤：完成清洗功能，屏蔽不需要的记录，允许相关的记录交给工作流的其它部分进 行进一步处理，比如主键冲突、非空检查。数据清洗过滤活动是模式保持活动，也就是经 此类活动处理后数据的输入输出模式保持不变。 2 数据转换：比如聚集、交、并等。数据从输入模式接收，经过一些处理交给活动的输出模 式，一般情况f ，输入模式和输出模式是不同的。也就是说模式进行了转换。 表3 2 基本转换类型分类 数据清洗过滤选掸( 6 ) 非宅( 硼) 主键冲突( 腿) 外键冲突( f l ( ) 数据唯一性( 删) 值域捡壹( 叫) 一正转换 聚集( ，) 投影( ) 标量函数转换( f c ) 表达式转换( e c ) 主键代替( s k ) 元组分解i t d ) ，亡组合并( t a ) 二元转换并u 交n 差 连接w 出丁二状态转换的需要( 比如交换变换) ，除了输入输出模式，每个活动还需要以f 辅助模式： 1 功能模式( f u n c t i o n a r y ) ：这个模式是一系列属性的集合，是所有输入模式并集的子集，表 示参与活动执行计算的属性。例如：一个活动有一个输入模式s t - a 、b 、c 、d ，执行一个非空检查 州( b ) 操作，则此函数的功能模式为sf = b 。 2 产生模式( g e n e r a t e d ) ；这个模式包括由活动的处理过程产生的所有输出属性。例如一个基 于函数的活动$ 2 把一个属性d o l l a r _ c o s t 转换成欧元格式，即e u r o _ c o s t = $ 2 e ( d o l i a r _ c o s t ) ， 则产生模式为s 产 e u r o _ c o s t 。数据清洗过滤操作的产生模式为空。 3 过滤模式( p r o j e c t e do a t ) ：一系列属性，属于输入模式，由这些活动执行相应的操作后不 再进行进一步处理。例如采f j 代理键操作后，数据交给新的产生的代理键( 属于g e n e r a t e d 模式) 处理，不再采用数据原有的键( 属于p r o j e c t e d _ o u t 模式) 。 这些辅助模式一旦确定，可以如下自动创建活动的输入输出模式( s g e n 算法) ：对t 作流图拓 扑排序，拓扑排序后每个活动的输入模式等于它的提供者的输出模式，每个活动的输出模式等丁由 它的g e n e r a t e d 模式扩展后的输入模式的并减去p r o j e c t e d模式。每次状态转换后，由新的状_out 态圈确定活动的模式。模式的自动构建过程算法如下。 模式产生( s g e n ) 算法 1 输入：一个状态图s ，即图g = ( v ，e ) 包括n 个活动 2 输出：完整定义好活动输入输出模式的状态图s 3 b e g i n 4 对s 拓扑排殷 5 给每一个活动赋一个优先级p ( i ) ，a t 表示标注了优先级p ( i ) 的活动 6 f o r ( i = l ：i ( n ：i + + ) 即对每一个活动 1 3 东南大学硕：t 学位论文 7 f o re a c hi n p u ts c h e m as t jo fa f 8 s ：o u t p u t _ s c h e m a ( p r o v i d e r ( s - j ) ) ： 9 1 0 o u t p u t s c h e m a ( a i ) 2 u ，8 uug e n e r a t e d s c h e m a ( a ) 一p r o j e c t e d _ o u t ( a i ) 1 1 1 2 e n d 由于有一些结点有不止一个出度，指向不同的活动或记录集。因而状态变换后原则上要重新计 算整个图的活动模式。在此，进行裁剪，因为已对一| = 作流拓扑排序，在这个前提卜，执行一个转换， 只要检查i ：作流所改变部分后的活动。当所有活动只有一个出度时( 每个输出模式只有一个消费者) ， 逻辑变换只影响相关的活动，工作流的其他部分保持不变，因此不对整个图应用模式产生算法，只 重新计算包括受影响活动的子图的新的活动模式。 3 5 转换适用性 一个e 1 lt 作流并不是所有活动在任何情况下都可以进行上述逻辑变换。需要定义一些规则， 判定某个状态围何时允许和禁l p 转换规则的应用。 交换变换；活动的交换变换不完全等同丁二操作下压( 代数优化的执行计划所采用的方式) ，由丁： 函数的存在潜在改变了属性的语义，关系代数对函数不提供支持，因此在有些情况下允许操作下压， 而在一些特殊的情况下并不允许操作下压。 下面就可以做操作下压和不可以做操作下乐各举一个例子。例如：活动a ，执行把属性c o s t 从 美元格式转换剑欧元格式，活动a 2 在a 1 后做选择操作，只选择那些欧元总计超出1 0 0 的元组，很明 显不能交换这两个活动；另一方面如果只要函数出现就不允许交换任何交换变换，那么实际上会错 过很多有用的操作。f r l 工作流有关函数的操作很多( 多是算术和字符串处理) 。例如活动a l 执行 把属性日期从美国格式转换成欧洲格式，活动a 2 把星期信息从日期格式中抽出产生一个新的属性d a y , 在这种情况下允许交换变换。 如果满足下列条件喇允许活动卸。a 2 进行交换变换。 1 a l ，a 2 在图中是邻接点( 不失一般性，a l 是a 2 的前驱) 。 2 a - ，a 2 有一个简单的输入输出模式，并且它们的输出模式只有一个出度。 3 在转换前后，a l 。 a 2 的产生模式是输入输出模式的子集。 4 在转换前后，a 1 ，a 2 的输入模式是它们提供者的子集。 当f u n c t i o n a r y 模式是输入模式的子集，输入模式是提供者模式的子集时才可以交换两个活动。 分解变换；对a l ，a 2 进行分解变换用新的活动a 来代替，a 在汇聚流做和a l 、a 2 同样的功能，分 解变换适_ l j 于以卜- 情形： 1 a l 、a 2 在代数表达式有相同的操作。仅是输入和输出模式不同。 2 a 1 、a 2 有一个共同的消费者a b ，是个二元活动。 显然a 1 、a 2 从图中去掉，用一个新的活动a 来代替，紧随后。也就是说对于任何节点x ，相应 的边a 1 ) ，阮a 2 ) 变成a b ) ；边( a 1 ，a b ) ，( a 2 ，a b ) 和：符点8 i ，a 2 从圈中去掉，加入新的节点a 和边( a ba ) 对丁二任意节点y ，边( a b , y ) p h y ) 代替。 分配变换：活动a 可以被分配剑两条路径上如果： 1 二元活动a b 是a 的提供者，两个同类活动a l 、a 2 处于汇聚于a b 的两个分支。 2 a 1 、a 2 和a 在代数表达式上有相同的操作。 同样a 从图中移掉，节点和边的操作和分解变换刚好相反。 组合和取消组合变换：组合变换并没太大的问题。新活动的输出模式是第二个活动的输出，输 入模式是所有有关活动输入模式的组合减去与第一个活动的输出模式有关的第二个活动的输入模 式。取消组合变换需要原来的活动是一个组合活动比如升b + c 。在这种情况f 活动分解成两个活动a 承l b 卜c 1 4 第三章e t l 优化问题建模 3 6 关于转换产生等价e t l 工作流的讨论 在这部分，讨论上述介绍的各种转换的正确性( 我们定义这些转换产生等价e t lt 作流) 。换 句话说，要保证对某个e t le 作流应用这些定义的状态变换后生成的新的e t l 工作流和原工作流等 价，也就是就在执行完毕将产生和原有t 作流同样的数据。 有很多方法来判定上述变换的正确性。这里采用“黑盒法”来测试。下面引入活动谓词的概念。 活动谓词：每个活动和记录集以逻辑已访问状态为标志，这个标忐称为活动谓词或活动已访问 状态活动谓词以活动的功能模式属性和记录集模式的属性作为变鼍。 一个活动附带一个活动谓词，活动成功执行后( 成功执行意味着活动处理好输入数据并交给下 一个活动或记录集) 谓词设置成“t r u e ”，否则谓词设置成“f a l s e 。 谓词由确定语义的谓词名和一系列变量组成，比如给定一个谓词n n ( a g e ) 表示输出数据流进行 了属性a g e 非空检查。 一个e t l 丁作流正确执行完成，所有活动的谓词设置成。t r u e ”。在此很容易检查两个工作流是 否等价：在相同的模式f 产生数据：执行完产生相同的记录( 相同的谓词设置为“t r u e ) 。 对于工作流s = g ( v ，e ) 的每一个结点n ev ：有一个谓词只作为结点n 的已访问状态c o n d 。 pic o n d 。( # v r b l l ，# v r b l k ，f f v r b l k + t ，一，# v r b l n ) 由于n ev = a op , s ，定义二种结点n 的常用情形。 1 n 是一元活动，活动的功能模式属性作为谓词变量。 # v r b l l ，# v r b l k ，# v r b l k + t ，f f v r b l n - n f u n 2 n 是二元活动，两个活动的功能模式属性作为谓词变量 # v r b l l ，# v r b l k = mi n l ，f u n # v r b l k + l ，# v r b l n n i n 2 f u n 3 1 3 是记录集，记录集的属性作为谓词变最。 一日r 作流的所有活动计算完成，相戍逻辑已访问状态集置为 t r u e 也就是说，数据经过e t l 活动从源数据流向数据仓库，把对应的活动谓词设置为“n 1 i e ”。 冈此当j ：作流完成后，我们可以获得f 面的表达式来描述工作流处理数据的完成状态。 工作流逻辑己访问状态c o n d w f ：是一个布尔代数表达式，是工作流所有活动逻辑已访问状态的 并集( 以执行的拓扑顺序排列) 。 基于上述分析来讨论产生等价e t l 工作流的判定规则问题。 等价e t l 工作流：两个- 作流w l 和w 2 等价当 1 ) 交给每一个目标记录集的数据模式是等价的。 2 ) 两个t 作流的逻辑已访问状态等价，即c o n d 。l ic o f 儿2 。 下面分别对上述两个条件进行讨论： 条件1 状态变换过程s 是一个图g 爿、e ) 。所有活动只有一个输出，并且每个输出模式只有一 个消费者。转换t 产生一个新的状态变换过程s ，即一个新的图g 彳v ，e ) ，变换所影响的活 动集合为g a cv uv ，必须保证v - g a 活动的模式等价于v g a 活动的模式( 即参加变换的活 动作为一个整体考虑。交给目标记录集的数据模式等价) f 面讨论五种变换满足条件1 所需的判断规则； 1 s w a ( a , b ) 假设一元活动序列k , a , b ，l e a ，此时g 气a b ) ，如果活动a , b 满足交换变换适用条件，则有： 在s w a 伍b ) 之前活动i 的输入模式等于活动b 的输出模式。 1 i n nr - l _ b o u t 气b i n ub g e n - b p r o ) = ( & o u t ub g e n - b p r o ) = f & i n u & g e n - a p r o ub g e n b p r o ) 爿k o u t k 3a g e n - & p r o k jb g e n - b p r o ) 在s w a ( a , b ) 之后 1 r i ( 硼m = l o u t 鼍a i n ua g e n - & p r o ) 1 5 东南丈学颈t 学位论文 = c o o u i ua g e n - & p r o ) ；r b i n ub g e n - b p r o u a g e n - a p r o ) = ( k o u t ub g e n - b p r o ua , g e n - a p r o ) 显然1 i n i b e 61 ) - 1 砜娴：o 2 f a c ( d c l ，c 2 ) 假设两个一元活动c ，c 2 汇聚于二元活动d ，d 汇聚于f b 一元活动分别汇于c l 勘应用f a c 变换后曲汇聚于一元活动d ，d 汇聚于新的一元活动e l ；2 最后义汇于f o 在这种情况fg = d , c l ，c 2 ，o l 。) ! 竺l 8 4 一c 峪一f +j _ ，一 气丽一b 图3 - 5f a c 变换 在转换前，d i n l = c 1 o o t - - - - i l o u t uc l ,