（计算机应用技术专业论文）etl工作流优化及其性能分析.pdf

摘要 近年来，数据仓库已经发展到能支持企业决策，甚至支持企业合作伙伴和客 户的新高度。新一代的数据仓库应用不仅改善了企业战略的形成，更重要地是发 展了战略的执行决策能力。e t l ( 抽取、转换、装载) 是数据仓库系统开发中的 重要组成部分之一，e t l 过程的正确与否关系到数据仓库的可用性。本文主要对 e t l 工作流进行了优化研究，并采用紧同步随机p e t r i 网对优化前后的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 过程实施的控制提供了很好的参考数据。 最后用紧同步随机p e t r i 网对e t l 工作流模型进行描述，在前面实验的基础 上对e t l 工作流进行了性能分析，也从这一方面再次证明了e t l 工作流优化的有 效性。 关键词：数据仓库；启发式算法；贪婪算法；紧同步随机p e t r i 网；同步变迁分 解等价法 论文类型：应用研究 a b s t r a c t i nr e c e n ty e a r s ，t h ed a t aw a r e h o u s eh a sb e e nd e v e l o p e dt os u p p o r tb u s i n e s s d e c i s i o n s ，o re v e nan e wh e i g h tt os u p p o r tt h eb u s i n e s sp a r t n e r sa n dc u s t o m e r s t h e a p p l i c a t i o no fan e wg e n e r a t i o nd a t aw a r e h o u s e c a nn o to n l yi m p r o v et h ef o r m a t i o no f e n t e r p r i s es t r a t e g y ，b u ta l s om u c hm o r ei m p o r t a n td e v e l o pt h ed e c i s i o n - m a k i n ga n d e x e c u t i o na b i l i t yo ft h es t r a t e g i c e t l ( e x t r a c t ，t r a n s f o r m ，a n dl o a d ) i st h em o s t i m p o r t a n tp a r to f t h ed a t aw a r e h o u s es y s t e md e v e l o p m e n t t h ea v a i l a b i l i t yo ft h ed a t a w a r e h o u s ei sd e p e n d e do nt h ec o r r e c t n e s so ft h ee t lp r o c e s s t h i sp a p e rs t u d i e st h e o p t i m i z a t i o n so fe t lp r o c e s s e sa n da n a l y s e st h ep e r f o r m a n c eo f t h eo p t i m i z a t i o n st o a d o p ts t r i c t l ys y n c h r o n i z e ds t o c h a s t i cp e t r in e t s f i r s to fa l l ，t h i sp a p e ri n t r o d u c e sa ne t la c t i v i t ym o d e l ，a n a l y s e st h ef a c t o r s w h i c ha f f e c tt h er u n t i m eo ft h ee t la c t i v i t i e s t h ep a p e rs e t su pat h e o r e t i c a l f r a m e w o r kf o rt h ep r o b l e mb ym o d e l i n gi ta sas t a t es p a c es e a r c hp r o b l e mw i t hw h i c h e a c hs t a t eg r a p hr e p r e s e n t sap a r t i c u l a rd 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 t s w o r k f l o w sw h i c ha 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 ，a n dt h es t a t es p a c ei sf a b r i c a t e d t 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 ，t h e nc h o o s et h em i n i m i z a t i o no ft h e e x e c u t i o nc o s to ft h ee t lw o r k f l o wa st h eb e s to n e t h e nt h ep a p e ri m p o r t st h es t a t es p a c es e a r c ha l g o r i t h m ，r e a l i z e st h eo p t i m i z a t i o n o ne t lw o r k f l o wb yt h eo p t i m i z a t i o no nt h 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 t h m s ， a n dd e m o n s t r a t e st h ee f f i c i e n c yo ft h ea p p r o a c ht h r o u g has e to fe x p e r i m e n t a lr e s u l t s ， w h i c hp r o v i d e st h ev e r yg o o dr e f e r e n c ed a t af o rt h ec o n t r o l o ft h ee t l i m p l e m e n t a t i o n f i n a l l y ，t h ep a p e ru s e ss t r i c t l ys y n c h r o n i z e ds t o c h a s t i cp e t r in e t st od e s c r i b et h e e t lw o r k f l o wm o d e l ，a n dc o n d u c t sp e r f o r m a n c ee s t i m a t i o no ne t lw o r k f l o wb a s e d o nt h ep r e v i o u se x p e r i m e n t s ，w h i c hi m p r o v e st h ev a l i d i t yo ft h ee t lw o r k f l o w o p t i m i z a t i o na g a i n k e y w o r d s ：d a t aw a r e h o u s e ；h e u r i s t i cs e a r c ha l g o r i t h m s ；g r e e d ya l g o r i t h m s ； s t r i c t l ys y n c h r o n i z e ds t o c h a s t i c p e t r in e t s ；s y n c h r o n o u st r a n s i t i o ne q u i v a l e n t d e c o m p o s i t i o n p a p e rt y p e ：a p p l i e d r e s e a r c h l i 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究 成果。论文中除了特别加以标注和致谢的地方外，不包含其他人 或机构已经发表或撰写过的研究成果。其他同志对本研究的启发 和所做的贡献均已在论文中做了明确的声明并表示了谢意。 名疹妒： 论文使用授权声明 厂、弓7 f 本人完全了解上海师范大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅； 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其 它手段保存论文。保密的论文在解密后遵守此规定。 名獬新澎泐： 厂，弓7 | 上海师范人学硕士学文论文绪论 1 1 研究背景 第一章绪论 目前，信息化建设呈现出“数据集中化、业务综合化、管理扁平化、决策科 学化”的发展趋势，而大多数过去遗留下来的异构的系统、应用、商务流程以及 数据源构成的应用环境己不能满足这样的需求。面对纷繁复杂的市场竞争，众 多企业立足于多年积累的数据和自身的核心业务，提出了建立数据仓库的规划和 实施方案，为企业的进一步发展奠定了基础。 数据仓库更多的不仅仅是一种产品，它是一种解决方案。数据仓库是从更为 典型的面向事务型的操作环境中分离出来的一种信息环境。数据仓库，就本身而 言，作为一种信息环境，逐渐成为了现代企业的一种关键资源。 数据仓库是一种能够提供重要战略信息的新范例。2 0 世纪9 0 年代，一些组 织开始从建立数据仓库系统中得到竞争的优势。表卜l 给出了一个战略领域的例 子，我们可以看到数据仓库正在不同的行业发挥着作用。 表卜l 使用数据仓库的行业 获得竞争优势的行业 夺零售业 制造业 呤客户忠诚度成本削减 市场策划。后勤管理 夺金融行业公益事业 风险管理夺资产管理 欺诈检测冷资源管理 令航空业政府机关 夺航线收益率令人力计划 区域管理夺成本控制 然而，战略信息并不是企业日常运作的信息，比如关于订单、发货、处理投 诉等。战略信息比这些信息重要得多，对于企业的生存和持续健康发展有非常重 要的意义。企业决定性的商业决策有赖于正确的战略信息。表1 - 2 列出了战略信 绪论 上海师范大学硕士学位论文 息的特征。 表1 - 2 战略信息的特征 综合性 必须有一个独立的、从企业整体来看的视角 数据完整性信息必须是准确的，必须符合商业规则 可用性必须是通过直观方法容易获得的，对于分析i ：作是有用的 可靠性每个商业因素都必须有且只有一个值 及时性信息必须是在规定时间内准备好的，待用 在大多数情况下，前面所述的数据仓库中的战略信息是从操作型系统中得到 的，但是这些操作型的信息不能直接用来提供战略信息，而且两者之间的信息在 一般情况下是不同的，这就需要对源系统中的数据进行处理。我们把这样的一个 处理过程叫做e t l ，即：抽取( e x t r a c t ) 、转换( t r a n s f o r m ) 和装载( l o a d ) 。 抽取：将数据从不同的数据源抽取到临时中间层，便于进一步处理。 转换：将操作数据转换成另一种格式以更加适用于数据仓库设计。在大多数 情况下，转换是将数据汇总。 装载：将业务数据从一个或多个数据源中取出，并逐字逐段地将数据映射到 数据仓库的新的数据结构上。 e t l 是建立数据仓库的必要步骤，根据调查统计，整个数据仓库系统开发中 7 0 左右的时间和工作量都花费在e t l 过程的设计和实施上乜嬲h 1 。 目前e t l 技术在国内外的发展虽然有了很大程度上的进步，但也存在着一些 不足。比如：在数据量过大的时候就会影响至m j e t l 工作流的执行效率，有时候还 可能导致无法在规定时间内完成数据的集成，并造成大量文件的堆积。再比如： e t l 工作流的执行性能无法在执行前进行分析等。 基于上述几个问题，本文将会着重研究以下几个问题： 1 影响e t l 工作流执行的因素有哪些，它们是如何影响其执行效率的； 2 引入状态空间搜索算法，如何更好地优化e t l 工作流的执行效率； 3 引入紧同步随机p e t r i 网，分析优化前后e t l 工作流执行前的性能。 1 2 国内外研究现状 2 上海师范大学硕十学文论文绪论 2 0 世纪9 0 年代初，在国外兴起了数据仓库( d a t aw a r e h o u s e ，d w ) 技术，促 进了联机分析处理( o nl i n ea n a l y t i c a lp r o c e s s i n g ，o l a p ) 技术和基于海量数 据仓库的数据挖掘( d a t am i n i n g ，d m ) 技术的发展。今天，在国内外软件市场， 数以百计的数据仓库、联机分析处理和数据挖掘软件产品走向市场、走向应用， 支撑起了商业智能( b u s i n e s si n t e l l i g e n c e ，b i ) 这一新兴领域。 在早期的数据仓库中，数据的抽取一般是数据操作的快照或者子集。基于一 系列规则下，这些快照被加载到一个终端用户数据系统中，大概一个星期或者一 个月一次。这些决策支持系统的数据模型和操作系统的数据模型是相匹配的，因 为，毕竟不管怎么样，它们是抽取快照的。 目前，对于e t l i 作流的研究主要集中在数据转换、数据清洗以及e t l 工作流 建模。文献 5 6 7 8 研究了在数据转换中的模式映射描述、数据清理和数据 转换的融合，以及如何使用e t l 过程来描述追踪数据仓库中的数据来源；文献 9 研究了清洗技术的优化，提出了一种自动清洗和人为清洗相混合的数据清洗策 略：文献 1 0 1 1 介绍了一种基于图形的e t l 活动的通用模型；文献 1 2 介绍了 基于e t l 活动的通用模型，设计了一种描述e t l 场景的基本框架；文献 5 1 3 1 4 1 5 介绍了两种e t l 工作流的概念建模的方法；文献 1 6 1 7 1 8 1 9 2 0 讨论了e t l 工作流优化的一些概念和方法。 最近几年，工作流技术的研究和应用已经引起了研究人员、开发人员和用户 的普遍关注乜小2 2 | 。诸如计算机支持的协同工作、无纸办公、表单传递、协作系统 和办公自动化等。业务流程建模是工作流描述的重要内容，模型的性能评价是工 作流系统研究和应用的主要理论基础和支撑技术，因此对模型的性能分析是工作 流的一个重要研究内容。有很多文献讨论了工作流系统模型的性能，但都是针对 工作流的某一方面特性来分析或改进工作流的性能。如文献 2 3 是根据客户服务 器这种工作流模型来对工作流的性能进行分析的，文献 2 4 是根据具有时间限制 的这种工作流模型来对工作流的性能进行分析的。 上面的文献中都没有提到对e t l 工作流的性能分析，这是本文所要关注的一 个方面，另s b e t l i 作流执行过程的优化也是本文的一个重点。 1 3 论文的主要工作 3 绪论 上海师范大学硕十学位论文 本文主要研究了以下几方面的内容： 1 在已有e t l 活动模型的基础上，对影响e t l 活动执行时间的因素做了分析。 2 对e t l 工作流以及工作流优化问题进行建模。 要对e t l i 作流进行优化首先需要建立适合优化的模型，本文用图、状态和 状态空间来对e t l i 作流和工作流优化问题进行建模，并介绍了几种可以用于优 化e t l i 作流的变换。 3 实现了e t l 工作流的优化。 本文借鉴了状态搜索空间算法，通过改进启发式算法和贪婪算法实现对e t l 工作流的优化，减少e t l 工作流的执行时间，提高e t l 工作流的执行效率。 4 通过实验分析了e t l 工作流优化方案的有效性。 为了分析e t l i 作流优化方案的执行效率和有效性，本文进行了有针对性的 实验，通过记录和分析实验数据，分析了我们提出的e t l i 作流优化方案的执行 效率和有效性。 5 用紧同步随机p e t r i 网对已有的e t l i 作流模型进行了描述，并对执行前 的e t l 工作流进行了性能分析。 1 4 论文的创新点 1 对影响e t l 活动时间执行的因素进行了分析。 2 对启发式算法和贪婪算法进行了改进。并实现了对e t l i 作流的优化。 3 采用紧同步随机p e t r i 网对e t l i 作流模型进行描述，在此基础上，用同 步变迁分解等价法对e t l 工作流进行了性能分析，分析表明优化算法能提高e t l 工作流的执行效率。 1 5 论文的组织结构 第1 章是绪论。 第2 章是数据仓库理论介绍。 第3 章是e t l 优化问题建模。 第4 章是基于算法的状态空间搜索； 4 上海师范大学硕十学文论文绪论 第5 章是e t l 工作流模型描述及其性能分析。 第6 章是总结。总结本文的工作、创新点及进一步的工作； 最后是致谢和参考文献以及读研期间发表的论文和参加的科研项目。 5 数据仓库理论 上海师范大学硕士学位论文 第二章数据仓库理论 2 1 数据仓库简介 随着数据库技术的应用与发展以及企业管理的需要，人们尝试着对数据库中 的数据进行再加工，从而形成一个集成的、面向分析处理的环境，以便能够从这 些海量的信息中挖掘规律，提取知识，最终创造出收益。随之，数据仓库应运而 生了。 数据仓库通常是一个专用的数据库系统，它独立于这个组织中的联机事务处 理系统。在以下方面数据仓库不同于操作型系统： 它比事务系统跨越更长的时间。 它包括多个被处理过的数据库( 对数据库进行处理是为了使数据仓库中 的数据具有统一的定义) 。 它被优化以便回答来自直接用户和应用软件的查询。 数据仓库至少有三种类型： 提供数据并支持整个企业的传统数据仓库。 数据市场，它是微型的数据仓库，用来支持特殊的商业单位或部门。 操作型数据仓库，它把数据仓库技术应用到事务系统中。 数据仓库之父b i l l 1 n m o n 给数据仓库下了一个定义，“数据仓库是面向主题 的、集成的、稳定的、随时间变化的数据集合，用以支持经营管理中的决策制订 过程2 引。 2 2 数据仓库的特点 数据仓库是一个信息传递系统，它具有如下几个特点： 面向主题 在一个数据仓库中，数据是围绕着企业主要对象( 如销售) 组织的。这种组 织是通过企业涉及的主题领域，而不是以软件应用为基础的。另一方面，数据仓 库包含面向决策支持的数据，这些数据跨越一段时间，并允许更复杂的关系存在。 6 上海师范人学硕士学位论文 数据仓库理论 数据集成 在数据仓库中，信息应该是：干净的、确定的、适当聚集的。数据仓库中的 数据是在对原有分散的数据库数据抽取、清理的基础上经过系统加工、汇总和整 理得到的，已经消除了原数据中的不致，从而保证了数据仓库内的信息是关于 整个企业的一致的全局信息。 非易失性环境 操作型数据库中的数据进行更新( 插入、删除、改变) 等操作时，是以记录 为基础有规律地执行。而数据仓库中的数据主要供决策分析之用，所涉及的数据 操作主要是数据查询，一舅某个数据进入数据仓库之后，一般情况下会长时间的 保盛。数据仓库中执行操作最多的是查询，修改和删除的操作很少，通常只需要 定期的加载和刷新。 时间级数 通常，数据仓库中的数据有5 年到1 0 年甚至更长时削内的，而操作型数据维 持大概只有6 0 天n 9 0 天。 在数据仓库中，组织起来的数据要一直包含相关的时间单位，因此，正确记 录的数据仓库数据是不能被用户更新的。 2 3 数据仓库体系结构 荫苘国 一忑三二1 萤咳荔二一 图2 1 数据仓库的系统结构创。 数据仓库理论上海师范大学硕士学位论文 数据仓库不仅仅是充当决策支持系统数据模型的物理实现，存放企业战略决 策所需信息，同时更多被看作一种体系结构，将异种数据源中的业务数据集成在 一起而构造，支持决策的专门查询和分析报告以及决策的制定。 从数据仓库系统结构图( 图2 - 1 ) 来看，它主要分四大部分：数据源、数据的 提取和存储管理、o l a p f j 艮务器和前端工具。 数据源：是数据仓库系统的基础，是整个系统的数据源泉。它通常包括企业 内部信息和外部信息。内部信息包括存放于r d b m s 中的各种业务处理数据和各类 文档数据。外部信息包括各类法律法规、市场信息和竞争对手的信息等。 数据的提取与存储管理：是整个数据仓库系统的核心。数据仓库的真正关键 是数据的提取与存储管理。数据仓库的组织管理方式决定了它有别于传统数据 库，同时也决定了其对外部数据的表现形式。要决定采用什么产品和技术来建立 数据仓库的核心，则需要从数据仓库的技术特点着手分析。针对现有各业务系统 的数据，进行抽取、清理并有效集成，按照主题进行组织。数据仓库按照数据的 覆盖范围可以分为企业级数据仓库和部门级数据仓库( 通常称为数据集市) 。 o l a p 服务器：对分析需要的数据进行有效集成，按多维模型予以组织，以 便进行多角度、多层次的分析，并发现趋势。其具体实现可以分为：r o l a p 、 m o l a p 和h o l a p 。r o l a p 基本数据和聚合数据均存放在r d b m s 之中；m o l a p 基本 数据和聚合数据均存放于多维数据库中；h o l a p 基本数据存放于r d b m s 之中， 聚合数据存放于多维数据库中。 前端工具：主要包括各种报表工具、查询工具、数据分析工具、数据挖 掘工具以及各种基于数据仓库或数据集市的应用开发工具。其中数据分析工 具主要针对o l a p f 艮务器，报表工具、数据挖掘工具主要针对数据仓库。 数据仓库也有其他的体系结构，例如：在两层环境中，数据源和客户在 同一台计算机上，而数据仓库和数据获取软件在另一台计算机上。单层体系 结构中，三个功能都在同一台物理机器上，有时在数据量有限且用户的数量 很小时会使用这种结构。 2 4e t l 简述 8 上海师范大学硕士学位论文数据仓库理论 e t l 目标 日 h p抽取转换装载 、 据仓i ， r r 国 图2 2e t l 处理过程 如图2 2 所示：e t l 处理过程分为数据抽取( e x t r a c t ) 、数据转换( t r a n s f o r m ) 以及数据加载( l o a d ) 三个阶段。在数据仓库的构建中，问题最多、数据量最大 的就是e t l 的操作乜7 儿1 8 1 。数据仓库的数据往往来自不同时期、不同硬件平台和不 同操作系统等，数据源的多样性造成了“脏数据 的大量存在，这些“脏数据” 产生的原因主要有： 数据库之间缺乏统一的标志，即表示同一对象的数据库记录的i d 不唯 一； 不同组织采用不同的格式表示数据，这对数据的整合也造成一定的困难， 典型的例子就是日期型的数据； 输入大量的数据时，总会或多或少出现一些错误； 存在不一致的数据。数据仓库要不断地装载这些存在“脏数据”的数据， 如果不能保证装载数据的质量，那么势必会降低数据仓库中数据的质量，对数据 仓库的后续操作造成影响，降低了数据挖掘的质量。为了提高数据质量，需要在 数据源与数据仓库之间架一座桥梁，同时还要在桥梁上设立“检查站 ，对经过 的数据进行检查，去除不符合要求的数据，这就是e t l 功能的工具。 e t l 是数据仓库获得高质量数据的重要环节，它是数据仓库中数据的入口， 一个设计良好、功能强大的e t l 工具对于构建一个数据清洁、结构良好的数据仓 库有着重要的意义。 市场上流通的e t l 工具主要分为下面3 种： 1 数据转换引擎。其中包括动态而复杂的操作算法。这些工具根据用户定 义的时间间隔，从一组指定的源系统中抽取数据，执行复杂的数据转换，将结果 导入一个目标环境中，并将数据应用到目标文件中。这些工具提供了最大可能的 灵活性，使用户能选择最合适的数据转换方法，实施完全更新和增量装载。这些 9 数据仓库理论上海师范人学硕士学位论文 工具的功能涵盖了整个e t l 过程。 2 通过复制捕获数据。这些工具中的大部分使用由数据库管理系统维护的 交易日记。在交易日记中捕获的源系统的变化可以近乎实时地在数据准备区域被 复制，等待进一步的处理。有些工具可以通过数据库触发器的使用来复制数据。 数据库中促出的专门规程用信号通知复制代理，捕获并传送这些变化。 3 代码生成器。这些工具直接处理数据的抽取、转换和装载。通过创建执 行这些功能的程序代码，完成这些过程。代码生成器会创建3 g l 4 g l 的数据抽取 和转换程序。用户提供数据源的参数和目标输出及其商业规则。这些工具可以生 成大部分常见编程语言的程序代码。 2 5e t l 策略和过程 e t l 策略是关于工作的总计划啪1 ，处理诸如如何提取数据以及如何处理数据 中的错误之类的问题。主要考虑的问题包括不同的数据格式、坏数据、不兼容的 源系统、源系统的改变和提取与加载的窗口等。e t l 策略需要定义这类问题的标 准来为e t l 过程提供依据。e t l 过程是用来执行e t l 策略的，它规定提取哪些数据 以及如何将其转换成一致的格式。在数据仓库的设计中，7 0 的努力都用于e t l 过程。一旦数据加载到数据仓库中，最主要的工作就是向业务决策者提供数据。 然而，数据的抽取、转换和装载是很漫长的过程，其中转换过程是最重要和最为 复杂的。数据转换过程不仅仅是数据格式的改变，它还意味着要准备运行数据、 转换其结构和内容，以及净化数据和将记录准备好以便集成到数据仓库中去 啪m 1 。其中转换主要包括类型转换、串操作、数学函数、参照完整性、关键字翻 译和聚集六种类型。 e t l 策略和过程将数据转换成与数据仓库一致的格式，再加载到中心数据存 储库中，它将直接影响数据仓库的最终数据存储格式。 综上所述，e t l 包含以下的工作和任务类型： 将几个源数据结构组合成数据仓库目标数据库中的行。 将一个源数据结构分成若干个结构后放入目标数据库中的若干行。 从源系统数据字典和目录中读取数据。 从多种文件结构中读取数据，包括平面文件、索引文件( v s a m ) 、旧系统 1 0 上海师范大学硕士学位论文数据仓库理论 数据库( 分等级的网络化的) 。 装载大量原子事实表的细节。 为大量聚集表或事实表做聚集。 将数据从源系统平台上的一种格式转换成目标平台上的另一种格式。 得到输入字段的目标值( 例如：从出生日期得到年龄) 。 将晦涩的数值改变成对用户有意义的值( 例如：将1 和2 转变成男性和 女性) 。 2 6e t l 过程的主要工作流 e t l 过程主要分为以下几个步骤聆引： 1 确定数据仓库中需要的所有目标数据； 这个需要考察目标系统关键计算指标的计算过程，需要考察度量数据、维度， 根据度量和维度的考察，我们就可以设计数据仓库系统的关系数据库的二维表结 构了。 2 确定所有的数据源： 数据仓库的数据源一般有很多种，包括有：e x c e l 文档、各种数据库等。 3 确定从源到目标数据元素的数据映射关系； 在分析源和目标系统数据结构的差异的基础上，筛选源系统中与目标o l a p 系统无关的数据列，并将这些列排除在抽取过程外。然后确定了源和目标系统的 二维表之间的映射关系，为后续的数据抽取和转换提供明确的参考。 4 设计完善的数据抽取规则； 源数据库系统的数据具有如下特点：结构化的异构数据库环境，即每个系统 的信息和组织都不一样，但总体属于结构化的数据；半结构化的数据结构，即存 在于w e b 上的一些数据非常复杂，没有特定的模型描述，是一种非完全结构化的 数据。 根据这两类数据的具体情况，确立了如下数据抽取规n - 抽取方式：采用自动方式和人工方式相结合，对于国内海关和国际世贸 系统这样的结构化数据，采用d t s 自动抽取方式；对于g d p 数据及人口等这样的 半结构化数据，采用人工抽取方式，然后再采用d t s 方式进行二次抽取。 数据仓库理论上海师范大学硕七学位论文 抽取频率：世贸系统这样的外部数据是每季度购入，因此我们对所有数 据都按照每季度抽取频率。 抽取顺序：根据实际情况，我们确立先抽取维度表数据，然后抽取事实 表的数据。 异常处理：针对无法抽取的数据，确立对应的处理规则。 数据存储区域：建立准备区域关系数据库，暂时存储中间抽取数据。 5 设计数据转换和清洗的规则； 为解决各源系统数据的多样性与复杂性，并处理为本系统可用的单一格式。 为此确立的转换规则有： 度量单位的转换：将各类度量单位转换为标准单位以符合数据仓库的统 一标准( 例如，将货币单位表示转换为美元等情况) 。 字段的解码：对源系统各种不同的编码进行解码，变成用户可以理解的 值( 例如，在各个源系统中，国家和交易商品的编码的不一致性问题) 。 类型转换：获取源列中的值，然后转化为解决方案中的数据类型表示。 域查找：使用源系统中的值查找数据存储中的替换值，转换为可以理解 的数值。 6 数据整合和装载。 大部分指标计算处理时，需要同时用到国内和国外的数据。但来自两个不同 源系统的数据，对应的交易产品和国家的编码不同，产品h s 编码划分粒度大小也 不一致。充分考虑客户意见，采用h s 编码的前4 位作为公共处理粒度，并按此新 维度对度量数据进行汇总。 2 7 本章小结 本章主要介绍了数据仓库以及e t l i 具的一些理论知识。 首先介绍了数据仓库产生的背景及其特点以及数据仓库的体系结构；然后是 e t l 的介绍，其中包含了e t l i 具的分类、e t l 策略以及e t l 过程的主要工作流。 1 2 上海师范人学硕士学位论文e t l 优化问题建模 第三章e t l 优化问题建模 本章将会介绍已有的一个e t l 活动模型以及e t l i 作流优化过程中涉及到的 五个交换操作，这将作为以后几个章节的基础。 3 1e t l 活动模型的建立 文献 2 介绍了如图3 - i 所示的一个e t l 活动模型，它将e t l 活动抽象为一个 类。这样的一个抽象模型既使得我们可以很直观地理解e t l 活动的构成，也为实 验数据的准备做了一个很好的铺垫。 图3 1e t l 活动模型 首先，我们介绍一下图3 - 1 中e t l 活动模型蕴含的一些基本要素： d a t at y p e s ：即数据类型。每种数据类型t 以名称、域和一组可列值集 等作为其标识。域的取值可以参考其实际数据类型的取值范围。 a t t r i b u t e s ：即属性。属性是以它的名称和数据类型作为标识的。属性 和取值范围构成了一个项。 s c h e m a ：是属性的有限集合。 r e c o r d s e t s ：即记录集。记录集以它的名称、逻辑s c h e m a 和物理外延( 也 就是属于记录集s c h e m a 的有限集合) 为其标识。通常我们会处理两种类型的记 录集：关系表和记录文件。 其次，图3 一l 中e t l 活动模型包含的几个属性说明参考文献 1 3 。 1 3 e t l 优化问题建模上海师范大学硕+ 学位论文 图3 2s s i s 开发的e t l 工作流 如图3 2 所示，它是一个用s s i s 开发的e t l 工作流。按照图3 - 1 中e t l 活 动的模型，该活动对象的各个属性值如表3 - 1 所示。 表3 1e t l 活动模型示例 n a m e 格式转换e x p r e s s i o nt o n u m ( ) i n s c h e m a n o ，n a m e ，a g e ，s c o r e ti m e c o s t o u t s c h e m a n o ，n a m e ，a g e ，s c o r e ) c o s t e x p 0 4 3 5 x 一9 7 5 7 0 f u n s c h e m a s c o r e l i s t _ s t a r t ) r o w c o u n t g e n s c h e m a )s e l e c t i v i t y 2 p r o s c h e m a 可以看出该模型简洁易懂，在本文中，我们将以此作为e t l 活动的模型。 3 2 影响e t l 活动b i 口j 的因素 文献 2 中已经介绍了一种e t l 活动时间估算模型砭；o 4 3 5 x 一9 7 5 7 0 ，这 个时间估算公式是用回归分析方法得到的，其中为e t l 工作流( 即该e t l 活动) 的执行时间，x 为源数据源的数据量。但这个估算公式中只考虑到了数据源只有 一种的情况，而现实中往往更为复杂，除了受硬件方面的因素等影响外，还包括 如下几点： 1 4 上海师范大学硕+ 学位论文e t l 优化问题建模 多个数据源。 s s i s 提供的数据源一般有如下几种： 1 ) d a t a r e a d e r 源：使用来自n e tf r a m e w o r k 数据访问接口的数据。 2 ) e x c e l 源：提取e x c e l 文件中的数据。 3 ) 平面文件源：提取平面文件中的数据。 4 ) o l ed b 源：使用来自o l ed b 访问接口的数据。 5 ) 原始文件源：提取文件中的原始数据。 6 ) 脚本组件：使用脚本来提取、转换或加载数据。 7 ) x m l 源：提取x m l 文件中的数据。 对于一个数据仓库而言，数据源越多，e t l 执行时间越难以估算，而且e t l 的执行效率也会在不同程度上降低。 网络速度。 数据仓库网络速度越快，e t l 活动执行越快。 数据量。 数据量越大，e t l 执行时间越多。 3 3e t l 工作流优化问题建模 本文将会用状态空间搜索方法来描述e t l 活动的优化问题：我们将会通过文 中即将介绍的交换、因式分解、分布执行、合并和分解五种变换操作来对e t l 活 动进行优化，从所有采用状态变换产生的等价状态图中找出最小代价的状态图即 为最优e t l 执行过程。本节中将会介绍五种变换操作以及状态生成算法；状态空 间搜索算法放在第四章讨论。 3 3 1 状态变换过程 本文涉及到的逻辑变换操作主要有交换、因式分解、分布执行、合并和分解 等，简单描述如下： s w a 交换：用于交换一元活动a ，和a ，的顺序，比如我们交换如图3 3 ( a ) 中两个活动的位置。交换只考虑一元活动，如：选择、检查空值、主键约束、排 e t l 优化问题建模上海师范大学硕十学位论文 除、功能函数等。我们把这种变换记为s w a ( a 。，a ：) 。 f a c 与d i s 交换：这两个变换共同作用于一元活动的交换中，比如：合 并、连接等，并且至少有两个一元活动具有相同的功能，但是它们是作用于不同 的工作流，如图3 - 3 ( b ) 所示。f a c 和d i s 是两种互逆的转换。如果我们有两个 活动，它们对不同的数据流进行了相同的操作，并且最后要进行合并，我们可以 采用f a c 操作。同样地，如果我们有一个活动，它作用于一个单独的数据流，我 们可以将它分到不同的数据流。这两种交换分别记为f a c ( a 。，a 。，a 2 ) $ 1 1 d i s ( a 。，a ) m e r 和s p l 交换：我们用这两种变换来进行“打包或者“解包，而不 改变活动的语义。这两种变换分别记为m e r ( a 1 + 口2 ，a l ，a 2 ) 和s p l ( a 1 + 口2 ，a l ，a 2 ) ( 如图3 3 ( c ) 所示) 。 一， ( 卜。划一。 图3 3 ( a )图3 3 ( b )图3 - 3 ( c ) 图3 - 3 ：交换、因式分解、分布执行、合并和分解的图示 3 3 2 状态生成算法 文献 3 3 为工作流的设计提出了一组活动模版，如图3 - 4 所示。 图3 f 一4 中的最底层叫做s c h e m al a y e r ，所有s c h e m al a y e r 的活动是类数据类 型、函数类型、基本活动、记录集和关系的实例。而位于最上层的叫做m e t a m o d e l l a y e r ，它包含了前面所提到的类。m e t a m o d e ll a y e r 和s c h e m al a y e r 的关系就是 通过实例化来建立的。m e t a m o d e ll a y e r 实现了前面所提到的泛型需求：通过适 当的例子，包含于m e t a m o d e ll a y e r 的类对于任何e t l 建模都非常通用。而中间的 t e m p l a t el a y e r 是为了使m e t a m o d e l 在实际的e t l 活动更为实用而引入的。 1 6 上海师范大学硕七学位论文e t l 优化问题建模 图3 4 ：e t l 逻辑活动的模板n 2 1 图3 - 4 中，数据仓库d w p s 中的数据是从一个确定的数据源s 1 p s 中得到的。 在这个过程中的一些操作必须经过人工干预后才能被用于实际应用中：比如，在 实例化一个n o tn u l l 的模版时，必须指定将要检查的属性列。可以观察到的是， 这时的记录集是类集( 属于m e t a m o d e l 层) 以及源表事实表的实例。实例和自包 含类通过实例层的连接来关联的。场景的所有活动的相同机制应用是基本活动以 及它的其中一个子类的实例，如图3 - 4 所示。关系也必须遵循相应的规则：注意 到提供者如何联系概念s 1 p s 以及d w p s ，它和通过合适实例连接的类提供者关系 是相关联的。 至于类集合集是相关的，在模板层我们可以将它特例化为几个子类，基于正 交特点，比如它是一个文件还是一个r d b m s 表，或者说是一个源还是一个目标数 据存储集( 如图3 4 所示) 。为了构建一个e t l 工作流，我们还必须指定每个活动 的输入输出s c h e m a 以及相关的参数，这是一个手工的过程。 沿着相同的框架，类基本活动更多的是特例化为一个e t l 活动的重复模式的 扩展集，如图3 - 5 所示。 1 7 l l i t e r s - s e l e c t l o n ( t 一n o tn u l lf n n - 9 r l 眦r yk e y v l o l a t l o ni p k - f o r e l g nk e y v l o l a t l o nc f k 一u n l q i i ev a l u e 埘) 一d o m a l n m l s m i t c h d m ) u n a r yo p e r a t i o n s p u s h a g g r c g a t l o n ( ，) p r o j e c t l o n ( ) f u n c t l o na p p l l c a t i o nf f j - s u r r c g a t ek e ya s s l g n n 昭n t ( s k j t u p l en o r m a l l z a t1 0 nc n ) - t u p l ed e n o r m a l l z a t i o n d n ) f i l eo p e r a t i o n s - e b c d i ct oa s c i ic o n v 台r 8 l o n c e b 2 a s ) s o r tf 1 1 e ( s o r t b i n a r yo p t r a t i o n s - u n l o nt u ) - j o i n ( 一：1 ) - d l f f ) 一u p d a t ed e t e c t1 0 n u p d l t r a n s f f ro p e r a t i o n s f o p f t p j - c o m p r e s s d e c o m p r e s s z d z ) 一b n c r y p t d e c r y p tf c r d c r ) 图3 - 5 模板活动以及它们按类别分的图形符号n 2 1 在本文中，我们将会介绍一个自动生成输入输出s c h e m a 的算法，如下所示： 这个算法最主要的特点是采用了剪枝方法，算法只对那些有变化的e t l 工作 流进行检查，相应地也只会计算那些受到影响的e t l 工作流的子图，而不会对整 个状态图进行遍历，这样生成s c h e m a 的效率就大大提高了。 3 4 本章小结 本章首先介绍3 e t l 活动模型的内涵，然后论述了影响e t l 活动时间的因素， 最后介绍了一个状态生成算法。 1 8 上海师范大学硕+ 学位论文 基丁算法的状态空间搜索 第四章基于算法的状态空间搜索 4 1 状态签名定义 在引入启发式算法和贪婪算法之前，首先介绍一下什么是状态图签名： 状态图签名就是将