（计算机应用技术专业论文）数据仓库增量维护技术的研究.pdf

摘要 数据仓库中包含着从各种独立自治的数据源中抽取出来的信息，当数据源发生变化时，数据仓 库中的数据也必须被更新以反映这种变化，面对如此大量的数据，采用完全重载的方法显然是不可 行的，因而有必要提出一种高效的增量式维护的方法，也就是只将数据源中发生变化的数据捕获并 刷新到数据仓库中。建立在数据仓库上的一些应用，如o l a p 分析和数据挖掘等，通常会涉及到大 批量数据的检索，为了能够提高查询的效率，在数据仓库中会建立一定数量的实视图。目前关于数 据仓库的增量式刷新的讨论，大部分都集中在实视图的维护上。本文提出了一个实现数据仓库增量 刷新的体系框架，它将不再局限于实视图的维护，而涉及到了一个数据仓库系统运行的整个过程， 包括对数据源变化的监控，将捕获到的变化数据传送和集成到数据仓库、对数据仓库的刷新和历史 数据的保存等主要部分。当采用传统的方法对数据仓库进行维护对，所捕获到的变化信息将被直接 应用到仓库中相应的表或实视图上。文中提出了一种d e l t a 表的方法，变化的数据先被抽取到d e l t a 表中，然后再利用d e l t a 表对数据仓库进行增量维护，该方法能够将复杂的维护过程进行分解，使可 控制性和正确性得到进一步的保证。由于数据源的更新和数据仓库的维护是两个分离的过程，这有 可能导致异常数据的出现。本文提出了一种补偿算法，它能够有效的消除异常数据，该算法借用了 e c a 算法的核心思想，但是针对我们所提出的框架，该算法在实现上做了很大改进。在刷新过程中， 数据仓库通常是不可访问的，为了减少数据仓库不可见的时间，我们将实视图的维护过程分成了数 据传送和刷新两个阶段。在数据传送阶段，数仓库对用户仍然是可访问的，因而这个阶段会做尽可 能多的工作以减少刷新阶段所需的时间。 关键词：数据仓库，增量昴q 新，实视图，聚集函数，数据异常 a b s t r a c t d a t aw a r e h o u s e sc o n t a i nl a r g ea m o u n t so fi n f o r m a t i o n ，o f t e nc o l l e t e df r o mav e r i t yo fi n d e p e n d e n t s o u r c e s a sc h a n g e sa r ec o l l e c t e df r o md a t as o u r c e s ，a l ld a t aa tt h ed a t aw a r e h o u s et h a td e p e n du p o n t h i s m u s tb eu p d a t e dt or e f l e c tt h e s ec h a n g e s s i n c et h e r ea l es om a n ya m o u n t so fd a t ai nt h ew a r e h o u s e ，i ti s n o tf e a s i b l et or e l o a dt h ew h o l ed a t aw a r e h o u s ee a c ht i m e s oi t i s n e c e s s a r yt of i n dam e t h o dt h a tc a l l e f f i c i e n t l yr e f r e s ht h ed a t aw a r e h o u s e t h a ti st os a y ，t h ed a t aw a r e h o u s e i so n l yu p d a t e dw i t ht h ec h a n g e d i n f o r m a t i o nc a p t u r e df r o md a t as o u i _ c , o s d e c i s i o ns u p p o r tf u n o t i o n s ，s u c ha so n - l i n ea r i a t y t i c a fp r o c e s s i n g ( o l a p ) a n dd a t am i n i n g ，i n v o l v ec o m p l e xa g g r e g a t eq u e r i e so v e rl a r g ev o l u m e so fd a t a w a r e h o u s e a p p l i c a t i o n st h e r e f o r eb u i l dac e r t a i nn u m b e ro fm a t e r i a l i z e dv i e w st oi n c r e a s et h es y s t e mp e r f o r m a n c e d a t aw a r e h o u s er e f r e s h m e n ti so f t e nv i e w e da sap r o b l e mo fm a i n t a i n i n gm a t e d a l l z e dv i e w s i nt h i sp a p e r , w e p r o p o s eaf r a m e w o r k f o rr e f r e s h i n gd a t aw a r e h o u s e si n c r e m e n t a l l y i ti ss h o w nt h a tt h ed a t aw a r e h o u s e r e f r e s h m e n t p r o c e s s i sa c o m p l e xp r o c e s sc o m p r i s i n g s e v e r a l t a s k s ，e g ，m o n i t o d n g ，e x t r a c t i n g ， t r a n s f o r m i n ga n di n t e g r a t i n go p e r a t i o n a ld a t a ，l o a d i n ga n dr e f r e s h i n gt h ed a t aw a r e h o u s e w h e nt h ed a t a w a r e h o u s ei sm a i n t a i n e di nu s u a lw a y , c h a n g ei n f o r m a t i o nw i l lb ed i r e c t l ya p p l i e dt ot h et a b l e sa n d m a t e r i a l i z e dv i e w si nt h ew a r e h o u s e i nt h i sp a p e r , ad e l t at a b l em e t h o di sp r o p o s e d c h a n g e sw i l lb ef i r s t e x t r a c t e dt ot h ed e l t at a b l e s ，a n dt h e nt h e s ed e l t at a b l e sa l eu t i l i z e dt om a i n t a i nt h ew a r e h o u s e t h r o u g h t h i sm e t h o 1 9 9 7 0 5 1 2 。通过比较时问戳标记，可以将从上一次刷新之后发生变化的数据抽取出来， 并存储在某个临时文件或辅助表中，然后再将它们传送到数据仓库端，用来对仓库进行增量维护。 4 )基于快照的抽取方法 在有些系统中，对数据源的数据库所允许的唯一操作只能是提取快照( 不允许在数据源上建立 触发器，也不提供a p i 函数抽取日志信息) 。在这类系统中，可以提取系统的当前状态，然后将之与 先前存储的快照进行比较，通过这样的计算可以得出发生变化的信息。在文献 1 4 中有关于数据仓 库的高效快照差分算法的详细讨论。 5 )基于数据复制的抽取方法 利用商业数据库提供的复制服务是探测和捕获数据源变化的另一个选择。如i b m 的d a t a p r o p a g a t o r 和s y b a s e 的r e p l i c a t i o ns e r v e r 等都提供了某些机制，将数据源中被修改的信息传播 到操作数据源的环境之外。“数据复制”是一种在多个地方维护一个给定数据集的机制，它将一个地 点( 源) 的改变信息复制到另外一些地点( 目标) ，并负责同步源和目标中的数据。数据源和数据目 标可以在同一台机器的数据库服务器上，也可以分布在网络中的不同服务器上。在3 2 节中将会以 d b 2 的d a t ap r o p a g a t o r 为例，详细阐述数据复制的原理。 6 )基于应用程序的抽取方法 对于非关系数据( 如t e x t 文件，x m l 文件等) ，修改已有的应用程序或者实现新的应用程序以 捕获数据源的变化是目前支持增量式刷新的唯一选择。创建相关数据的一个快照，并将它们逐一与 先前的版本比较，是这种情况的一个解决方法。另外，还可以修改已有的应用程序，为数据源中改 变了的数据加上一个时间戳，监视器周期性的查询数据源，选出时间戳大于上一次刷新时间点的数 据。 9 东南大学硕士学位沦文 3 2 基于d b 2 的数据复制方法 i b m 提供了许多支持数据复制的产品，但本文只介绍它的代表性产品d a t ap r o p a g a t o r ，其余的 产品原理与之相似。d b 2 d a t ap r o p a g a t o r 包括三个主要部分：管理接口( a d m i n i s t r a t o r i n t e r f a c e s ) ，改变捕获机制( c h a n g e c a p t u r em e c h a n i s m s ) 和应用程序( a p p l yp r o g r a m ) 。 1 )管理接口可以被用来部署复制环境，其中一个主要任务就是创建控制表( c o n t r o lt a b l e s ) ，控 制表中存储丁复制过程所遵循的标准，它是复制过程中各个部分进行交互的中介，稍后还会详 细讨论。控制表可以具有多种不同的类型，如用于登记复制源信息的r e g i s t e rt a b l e ，记录已 提交事务的u n i t o f w o r k t a b l e ( 简称u o w t a b l e ) ，用于调整捕获进程性能的t u n i n gp a r a m e t e r s t a b l e 等，都属于控制表的范畴。 2 )当部署好了复制环境之后就可使用改变捕获机制来捕获数据源中发生的变化，并将它们存储 到临时表中。d b 2 的数据复制方法提供了两种机制用于捕获数据： ( 1 ) 捕获程序( c a p t u r ep r o g r a m ) 。 当复制源是d b 2 表时，捕获程序通过日志信息捕获源数据库的变化，并将它们存储在一些 临时表中。捕获程序通常位于源服务器上，并且是持续运行的，但是当需要修改源的信息时， 可以将之停下来，修改完毕后再启动。 ( 2 ) 捕获触发器( c a p t u r et r i g g e r s ) 。 当数据源是非i b m 数据库时，就不能再通过日志信息来捕获源的变化，这时可以通过创建 触发器来捕获数据源中所发生的变化。每当特定的数据库事件( i n s e r t ，u p d a t e ，d e l e t e ) 发生时， 相应的触发器就会被激活。通常捕获触发器是由d a t ap r o p a g a t o r 自动创建的。 3 ) 应用程序读取记录在控制表和临时表中的相关信息，井将改变了的信息复制到目标表中。需要 注意的是，这里的应用程序与我们通常所说的应用程序是不同的概念，而是指d b 2 数据复制的 组件。 复制过程的各个部分是相互独立的，它们依靠存储在控制表中的信息进行彼此间的通信。捕获 程序、应用程序以及捕获触发器都分别修改控制表中的信息以标明复制过程的进展，同时对各个部 分进行协调。 复制过程的各个部分之间的通信方式将因数据源是d b 2 数据库还是非i b m 数据库而不同。对于 d b 2 服务器间的数据复制，捕获程序通过读取服务器上的日志信息来捕获数据源中发生变化的数据， 然后将捕获到的数据存储在临时表中，这样的临时表被称为变化数据表( c h a n g ed a t at a b l e ，简称 表) 。当数据源是非b b 2 数据库时，捕获触发器将会捕捉变化了的信息，同时也会将它们存储在 一些临时表中，这样的表被称为一致性变化表( c o n s i s t e n t c h a n g e d a t at a b l e ，简称c c d 表) 。 应用程序会将这些临时表中的数据拷贝到目标表中，目标表中的数据反映了数据源的变化。通 常的情况是：数据源的变化被捕获，这些被改变的行被插入到c d 表中，而相关的事务信息也被插入 到u o w 表中，将c d 表和u o w 表进行连接以判定哪些变化是被提交了的，从而将这些已经提交了的更 改复制到目标表中。 c c d 表除了可以用于存储非i b m 数据源中变化了的信息，还具有别的功能。例如，可以将上述 c d 表和u o w 表连接所产生的信息存储在c c d 表中，于是c c d 表中只包含提交了的变化信息，这样应 用程序可以直接读取c c d 表中的信息，而避免了由于将c d 表和u o w 表进行连接所带来的性能负担。 c c d 表分为以下几种类型： l o 第三章增量数据的欹取 1 ) 本地和远程c c d 表 本地c c d 表驻留在源数据库中，而远程c c d 表驻留在本地数据库之外，也就是说在网络上任何 一个a p p l yp r o g r o m 能够访问的数据库中。如果目标表在远程，通过使用远程c c d 表可以减少网络 传输的负载。 2 ) 完全和非完全c c d 表 完全c c d 表中包含了满足条件的所有数据，除了以后捕获到的变化了的数据外，在复制开始时， 数据源表中的所有信息都将被刷新到c c d 表中。因而，如果a p p l yp r o g r a m 将完全c c d 表当作数据 源表，同样可以达到将真正数据源表中变化了的信息复制到其它的目标表的目的。非完全c e d 表中 只包含数据源中变化了的信息，在复制开始时，a p p l yp r o g r a m 并不会用数据源中表的数据来刷新 它。因此，刚开始非完全c c d 表中的信息是空的，只有当数据源中的数据发生了变化时，才会在表 中存储信息。 3 ) 压缩和非压缩c c d 表 压缩c c d 表中只保留最近的变化信息。例如，数据源表中的一行被改变了五次，那么在压缩c c d 表中只保留最后一次修改的信息，前面四次修改的休息都将丢失，它的好处在于将多次修改进行合 并，以减少网络传输的负载。而对于非压缩c c d 表，它将会记录每次修改的信息，因而最终表中将 会有五行记录，它的好处在于可以记录修改的历史信息。 下图说明了使用d b 2 的数据复制方法捕获数据源变化的过程，在图中只画出了一些相关部件 其它部件( 如i n t e g r a t o r 等) 都被省去了。 国4 使甩数据复翻的方法捕获数据源的变化 下面将对数据复制基于日志的通信方法做一个总结，基于触发器的通信方法与此类似。 从数据源中捕获数据 1 ) c a p t u r ep r o g r a m 读取r e g i s t e rt a b l e 中的信息，判定需要捕获变化信息的数据源有哪些。当 c a p t u r ep r o g r a m 在运行时，如果定义了新的复制源，这些新定义的数据源将不会被c a p t u r e p r o g r a m 所知道，除非重新启动捕获程序。 2 )c a p t u r ep r o g r a m 监控d b 2 数据库的日志，以探测被定义为复制源的数据源表信息的变化。 3 ) 对于在d b 2 日志中发现的每一个更新，c a p t u r ep r o g r a m 在c d 表中插入一行记录( 如果将u p d a t e 看成是d e l e t e 和i n s e r t 两个操作的话，将会插入两条记录) 。每个复制源都有一个c d 表。 4 ) c a p t u r ep r o g r a m 在u o w 表中存储已提交事务的相关信息这个控制表中的信息确认源服务器 中哪些事务是已提交事务。在基于日志的捕获方法中，每一个d b 2 源服务器都有一个对应的u o w 表。 5 ) c a p t u r ep r o g r a m 更新r e g i s t e rt a b l e ，记录对于每个复制源已经有多少已提交数据被捕获。 东南大学硕士学位论文 将数据复制到目标表中 1 ) a p p l yp r o g r a m 首先通过将数据源表中的所有数据复制到目标表中实现复制源和目标的同步。 这个动作称为完全刷新拷贝( f u l 卜r e f r e s hc o p y ) 。经过完全刷新拷贝之后，c a p t u r ep r o g r a m 开始捕获数据源的变化。 2 ) a p p l yp r o g r a m 检查r e g i s t e rt a b l e 己确定是否有改变信息需要被复制。 3 )a p p l yp r o g r a m 更新p r u n i n gc o n t r o lt a b l e 以便和c d 表中捕获到的变化进行同步。 4 ) a p p l yp r o g r a m 将c d 表和i j o w 表进行连接，并将变化的数据复制到目标表中。通过将两个控制 进行连接，a p p l yp r o g r a m 能够确保只复制了在数据源中已经提交了的更改数据。( 也可以将c d 表和u o w 表连接所产生的信息存储到c c d 中，a p p l yp r o g r a m 只需直接从c c d 表中读取信息即 可) 。 裁减控制表 i ) a p p l yp r o g r a m 更改p r u n i n gc o n t r o lt a b l e 以标明已经将多少更改数据复制到目标表中了。 2 ) c a p t u r ep r o g r a m 首先确定那些更改已经被应用了，然后将它们的相关信息分别从c d 表和u o w 表中删除。这可以通过查询控制表来确定，因为被提交了的事务和被应用了的更改已经分别被 记录在r e g i s t e rt a b l e 和p r u n i n gt a b l e 中了。 3 3 小结 目前很多研究文献都强调了对数据仓库进行增量式刷新的重要性，但是它们都假设已经获得了 变化数据，并以此为基础来探讨各种实现增量式维护的方法，然而事实并非如此。本文对常用的捕 获数据源变化的方法进行了总结，并重点讨论了基于d b 2 的数据复制方法。关于这些方法优缺点的 分析和比较以及相关性能的分析，在文献 1 5 】中有详细的讨论。另外，该文献还提出了称为。口一d e l t a 的抽取变化数据的方法，这种方法也是基于日志信息的，但它并不是从日志中抽取变化了的数据， 而是抽取引起数据变化的操作。例如，对于如下的一条更新语句：u p d a t es a l e ss e t q u a n t i t y 2 q u a n t i t y + 6 6w h e r ed a t e 1 9 9 9 1 卜0 5 ，它可能会引起上千条数据的改变，将这些变化的 数据捕获并存储在临时表中，然后再将它们传送到数据仓库端，这个过程会占用掉很多存储空间， 而且会增加网络传输的负载。但就这条更新语句本身来说，它包括的字节数很少，如果直接将这条 更新语句传送到数据仓库中，无疑会节省很多空间，也提高了传输的效率。虽然o p - d e l t a 方法对提 高系统性能很有帮助。但在具体实现上还有许多问题需要解决。例如。由于数据源和数据仓库在设 计模式上是存在差异的，因而对数据源的更新语句不能够直接应用到数据仓库上，而需要经过变换。 再如，没有了变化数据，仅凭一些更新语句如何实现数据仓库的自维护性，这也是一个值得探讨的 问题。 1 2 第四章数据传送和集成 第四章数据传送和集成 当捕获到了数据源巾的变化数据之后，下一步工作就是要将这些数据转换为符合数据仓库中所 定义的公共模式并将它们传送给集成器( i n t e g r a t o r ) ，这是由包装器( w r a p p e r ) 负责实现的。 由 于各个数据源所提供的数据类型是有差异的，因此，原则上对每种类型的数据源都要提供一个相应 的包装器。另外，包装器还负责将所捕获到的变化数据与数据源中相关的表进行连接的工作，并处 理可能出现的数据异常。集成器负责对各个包装器传送上来的数据进行汇总或连接( 如果需要的话， 也要处理可能出现的数据异常) ，会进行进一步的数据丢失或数据冲突等情况的处理，并将最终结果 传送到d e l t ad a t ar e p o s i t o r y 中相应的表内。 4 1 数据的传送 w r a p p e r 所做的工作相当于是集成前的一次预处理，它会向集成器提供较规范的数据格式，方 便于集成器的工作。从数据源到目标的转换规则是在数据仓库的配置阶段定义的，这些规则将被当 作元数据的一部分而存储起来。可以用如下的语法格式表示源数据到目标数据的映射： ( s o u r c ea t t r i b u t en a m e ，t a r g e ta t t r i b u t en a m e ， m a p p i n g 其中m a p p i n g 可以表示各种映射关系，如i ：l 、1 ：n 、n ：i 等，它也可以标识一个过程或函数， 以实现更复杂的映射机制。m a p p i n g 部分是可选的，默认情况下，它将表示一个1 ：1 的映射，例如， 关于顾客的婚姻状况信息，当某些数据源所采用的方法和数据仓库中所采用的表示方法一致时，就 可以进行直接映射。对于顾客姓名的表示。在某些数据源中可能将l a s tn a m e 和f i r s tn a m e 合在一 起作为一个n a m e 属性存储，如果在数据仓库中是采用两个属性表示的话。在传送的过程中就需要对 这个n a m e 属性进行拆分，这是一个l ：n 映射的例子，即数据源中的一个属性需要拆分成相应于数据 目标中的多个属性。如果将上面这个例子反过来，则是一个n ：l 映射，即数据源中多个属性对应于 数据目标中一个属性。正如本文在第二部分所提到的那样，对于商品价格( p r i c e ) 的表示，各个地区 可能采用不同的方法，这个时候就需要通过一些用户自定义函数来完成不同表示方法之间的转换。 送往集成器的数据有可能涉及到同一数据源中多个表的信息，因而，除了将所捕获到的数据转 换成公共模式外，包装器另外一个重要的任务就是要负责将所捕获到的变化数据和相应的表进行连 接，以产生最终所需要的数据。对于在此过程中可能出现的异常及其解决方法，将在本章的4 3 小 节单独列出来讨论。 4 2 数据的集成 当i n t e g r a t o r 接收到各个包装器送来的数据后，它将会对这些数据进行进一步的处理，然后再传 送给相应的d e l t a 表。例如，当各个销售点有新的销售信息时，这些信息会被捕获并由相应的w r a p p e r 传送给集成器，集成器将这些销售数据合并( u n i o na 1 1 ) 之后，再送到相关的d e l t a 表中。但是，有时 候送往d e l t a 表的数据并不是简单的将各个w r a p p e r 送上来的数据进行汇总即可，有可能需要将某个 w r a p p e r 送上来的数据与其它数据源中的相关数据进行连接，这同样会面临着数据异常的问题。虽 然w r a p p e r 所面临的是单数据源的情况，而i n t e g r a t o r 所面临的是多数据源的情况，但它们在处理方 法上却非常相似，只要把相关的算法稍作修改就可以满足需要，因而在本文中不再单独列出来讨论。 本文在这一章的小结中还会提到这一点。 如果需要的话，集成器还会对数据丢失或数据冲突等情况进行处理，这可以归纳为一种语义层 上的处理，而不再是简单的模式转换。例如，录入人员在进行数据录入时，可能认为某些属性不重 要而将之忽略了，但在决策分析中可能要用到这些数据，因而需要想办法为属性填上空缺的值。一 东南大学硕上学位论文 般有以下几种方法可以解决这个问题：1 、忽略元组。除非元组有多个属性值空缺，否则这种方法并 不是很有效。2 、使用一个全局常量填写空缺值。将空缺的属性用同一个常量( 如u n k n o w n ) 来填写， 使用这种方法将数据集成到数据仓库后，在决策分析时可能会形成一些有趣的主题，因为它们都具 有相同的值( u n k n o w n ) 。3 、使用最有可能的值填充空缺值。可以用线性回归或其它的数理统计方法 来推测丢失的数据。采用这些方法填入的值可能不正确，但是，由于它们考虑了其它属性的值，有 更大概率和其它属性保持联系，因而在主题层使用，对于决策分析和进一步的数据挖掘比较有好处。 除了数据丢失之外，还有可能存在数据冲突的情况。例如，对于在引言中所提到的运行实例，由于 各个销售部门分别保存自己的顾客信息，很可能会出现一些顾客的数据存在于多个操作数据库中的 情况。当把各个销售部门的顾客信息集成到数据仓库时，就必须要将一些重复的信息过滤掉，否则 在进行统计分析时就会得到不准确的数据。 4 3 数据传送过程中的异常及其解决方法 从上面的讨论可知，包装器将数据源中的变化信息传送给集成器，集成器对这些信息做进一步 处理之后再传送到d e l t a 表。如果由w r a p p e r 送上来的数据是从单个表抽取上来的，则只需直接将 它们送往集成器即可- 但是，如果送往集成器的数据涉及到数据源中多个表的信息，情况就会变的 复杂，因为某个表的变化数据需要和别的关系表连接，才能最终产生送往d e l t a 表的变化数据。这 些情况可以用l 可乒，表示： d a t as o u r c e l d a t as o u r c e 2 臣4 id e t a 表中钓数据司以扶单个表或多个表连接中得到 1 4 第四章数据传送和集成 为了能够突出主要问题，在图中只画出了一些相关部件，而省去了其它一些部件。从留童，可 以看到，数据源l 巾的信息是从单张表r l 中直接抽取出来的，而w r a p p e r 2 送到i n t e g r a t o r 的信息， 则是将数据源2 中的r 2 和r 3 表连接所得。这些情况都可以通过查询元数据得到。需要注意得是， 数据源2 并不知道关于w r a p p e r 2 和i n t e g r a t o r 以及d e l t at a b l e 的任何情况，因为它本身是一个 独立、自治的系统，也就是说，如果r 2 表中的信息发生了变化，它可以将变化的情况通知给w r a p p e r ， 但它并不知道要将变化的信息和r 3 表进行连接，以产生d e l t at a b l e 所需要的变化信息。 一般情况下，在一个数据仓库环境中，数据源是早期已经存在的、独立、自治的系统，它们并 不了解数据仓库的信息。当某个数据源发生了变化时( 例如，雇了一名新的员工，或一位病人已经 支付了医药费) ，它可以用某种方式通知数据仓库，但是这个数据源并不能确定，为了刷新数据仓库 它还要提供其它的信息。只能是当一些简单的信息到达数据仓库之后，数据仓库发现还需要另外一 些信息才能够对自身进行正确的维护，因而它会再向数据源发出一些查询，以获取所需的信息。这 种情况可以用图重2 表示。 图4 2 当数据源发生变换时对数据仓奉送行更藐韵过程 图中的虚线表明，如果是从单张表中抽取信息的话，q u e r y 和a n s w e r 两个过程就可以省略了。 从留盔2 可知，数据仓库有可能会向数据源发出查询信息，数据源再对查询求值并做出应答，但此 时数据源的状态可能已经改变( 例如，又有新的数据插入或被修改了) 。这种数据源和数据仓库的维 护相分离的情况，可能会导致仓库中的数据不一致( 在本文中，会导致捕获到的变化数据不一致， 最终影响数据仓库中的数据) 。接下来本文将要通过几个例子说明在数据传送过程中可能出现的各种 情况( 包括正常情况和异常情况) 。 4 3 1 数据传送过程中可能出现的异常 在讨论异常情况之前我们先看一个正常维护的例子 例l 正确的增量维护 假定在数据源中包含如下的两个关系表r 1 和r2 wx 12 xy 24 令d t 2 兀w ( r 1 r2 ) ，d t 是存储变化数据的辅助表，刚开始时d t = 妒，然后变化数据不断被捕获到 d t 表中，再将d t 表中的数据传送给i n t e g r a t o r 。为了表述方便，文中将用i n s e r t ( r ，t ) 表示将元 组t 插入到关系表r 中，用d e l e t e ( r ，t ) 表示将元组t 从关系表r 中删除，用( t 1 ，i t2 ，i t 。 ) 表示某个关系表中有元组t 。，t2 ，t 。现在发生如下的事件： 1 5 东南大学硕士学位沦文 1 在数据源插入了一个元组：u = i n s e r t ( r ， 2 ，3 ) 。既然数据源并不知道关于数据仓库的任何 情况，它只是简单的发一个通知信息给w r a p p e r 。 2 w r a p p e r 接收到u ，它通过查询数据仓库中的元数据定义，发现需要将r 和r ，连接才能产生所 需的变化信息，于是它向数据源发送查询q = h ( 。l 2 ，3 3 ) 。 3 数据源接收到查询q ，并对它求值，得到a = ( 1 ) 。数据源将a 返回给w r a p p e r 。 4 w r a p p e r 接收到a ，并将( 1 ) 插入到d t 表中。 开始时r l r2 = ( 1 ) ，插入元组 2 ，3 之后r lx 。2 = ( 1 ， 1 ) ，可见相对于初始状态，变化 的情况确实是插入了一个元组 1 。下面是两种异常的情况。 例2 插入异常 假设有如下的两个关系表r l 和r2 ： wx xy 23 考虑和例l 一样的增量表d t 2 n ( r lx r 2 ) 。现在有两个连续的事件u i = i n s e r t ( r l ， 1 ，2 ) 和 u 22 i n s e r t ( r2 ， 2 ，4 ) 。考虑如下的事件 1 在数据源发生更改u l = i n s e r t ( 。l ， 1 ，2 ) 并将u 1 送到w r a p p e r 。 2 w r a p p e r 接受到u j ，向数据源发送查询q i = y i 矸，( 1 ，2 。2 ) 。 3 在数据源发生了更改u 2 = i n s e r t ( r2 ， 2 ，4 ) 并将u2 发送到w r a p p e r 。 4 w r a p p e r 接受到u 2 ，向数据源发送查询q2 = i i ( r 1 x 2 ，4 ) 。 5 数据源对q l 求值，此时数据源的状态为：r l = ( 1 ，2 ) ，r2 = ( 2 ，3 ， 2 ，4 ) 。可以得到 a l2 ( 1 ， 1 ) ，a l 被返回给w r a p p e r 。 6 w r a p p e r 接收到a l ，并将( 1 ， 1 ) 插入到d t 表中。 7 数据源对q 2 求值，得到a2 = ( 1 ) ，a2 被返回到w r a p p e r 。 8 - w r a p p e r 接收到a 2 ，并将( 1 ) 插入到d t 表中，此时d t 表中的数据为( 1 ， 1 ，h i ) 。 通过采用例1 中的方法，可以得知d t 表中正确的数据应该是( 1 ， 1 ) ，但是现在表中却多了 - - - f - 元组 1 。之所以会出现这种情况是因为d e l t a 表的维护和数据源的更改是独立的，当w r a p p e r 向数据源发出查询信息时，数据源此时刚好发生了变化。 1 6 第四章数据传送和集成 例3 删除异常 考虑如下的两个关系表 wx xy 12 23 令d t = 1 1 wr ( 。l r2 ) ，发生如下的事件： 1 在数据源中发生更改u i = d e l e t e ( 。l ， 1 ，2 ) ，u l 被发送到了w r a p p e r 。 2 w r a p p e r 接收到u l ，向数据源发送查询q 1 = 兀w y ( 1 ，2 x r2 ) 。 3 数据源中发生了更改u2 = d e l e t e ( r 2 ， 2 ，3 ) ，u2 被发送到了w r a p p e r 。 4 数据源接收到了q ，此时数据源的状态为r l = 妒，r2 = 妒。对q l 求值得到a ，= 妒，a 。被发送到 w r a p p e r 。 5 w r a p p e r 接收到a l ，发现它的值为空，将不对i ) t 表做任何修改。 6 数据源接收到了q2 ，对q2 求值得到a 22 妒，a2 被发送到了w r a p p e r 。 7 w r a p p e r 接收到a2 ，发现它的值为空，将不对d t 表做修改。最终d t 表中的数据仍为空。 d t 表的数据为空，说明没有捕获到任何变化，这显然是不对的。采用例1 中的方法，将最终状态和 初始状态相比较，会发现应该有一条删除信息 1 ，3 。 4 3 2 对异常的常用解决方法 目前对于可能出现的异常，有如下几种解决方法： 当向数据源发出查询时，数据源中相应的关系表应该被锁定，直到相关的查询结果被计算出来 之后，才可以解除锁定。但这样对数据源的限制比较大，不利于并发执行。 采用快照的方法。如6 1 1 小节所述，计算前后两次的状态，它们的差就是需要捕获的变化。 这样就抛弃了动态更新的方法，在数据量很大的时候效率较低。而且它需要保存最近次的快 照，在计算新的快照时要对数据源锁定。 在上面的快照方法中，当需要计算快照时，要向数据源发送查询信息，而且要锁定数据源。为 了克服这个缺点，可以在数据仓库端保存和关系表完全一样的副本，这样计算就可以完全在仓 库本地进行，而不要增加数据源的负担，而且减少了网络传输的负载。如对于上面的例2 ，可 以在仓库端保存r i 和r2 的最新副本，当u l 发生并被送到w r a p p e r 时，w r a p p e r 可以直接用 1 ，2 3 2 ，3 得到变化的数据( 计算时应对r2 副本锁定) ，由于此时对r 2 的修改还没有反映到仓库 中，因而可以保证得到的数据是正确的。这种方法增加了存储的负担，而且需要即时更新副本， 使它们保持最新状态。 采用补偿的方法。该方法的基本思想就是在发往数据源的查询中再添加一个补偿查询，以弥补 并发操作所带来的影响。如当r l 发生变化8r 。时，为了计算变化信息，w r a p p e r 将会向数据源 发送查询6r l 。2a 但此时r 2 发生了变化6 。2 ，因而最终得到的查询结果将是：6r 】( r 2 + 东南大学硕士学位论文 6 。2 ) = 6r l r2 + 6r i 6 。2 。此时就必需要将多出的查询6r l 6 。2 去掉，否则下次将6 r 2 发往数据源计算变化数据时，又会出现一次8 r 1 6 r 2r 这样就造成了重复计算。考虑4 3 i 节中的例2 ，假定消息是按顺序发送的，并且数据源处理请求是一个原子动作( 例如，数据源发 生更改并最终将更改信息发送到数据仓库，这些是一个原子动作，是不可被中断的。如果此时 有查询消息或其它更改消息到达，它们都必须等到正在执行的动作做完) ，在第4 步中，当 w r a p p e r 接收到数据源的更改信息u 2 时，它所发出的查询q l 还没有得到应答。这时w r a p p e r 就可以推断，0 l 查询将会访问到u2 变化后的信息( 否则按照前面的假没，将是q l 的消息先到 达) ，从而产生“不正确”的状态。为了进行补偿，w r a p p e r 所发出的查询将是q 2 = 兀 ( r l 2 ，4 ) 一兀w ( 1 ，2 2 ，4 ) 4 3 3 相关概念的介绍 我们首先定义什么是事件( e v e n t ) ，所谓事件是指在同一地点发生的一系列操作的集合。例如， 在数据源端有如下两种事件： 1 ) su p ：数据源执行更改操作u 。然后将这个更改发送给w r a p p e r 。 2 ) s q u ：数据源对接收到的查询q 进行求值，然后将所求的结果返回到w r a p p e r 。 在包装器端也有两种类型的事件： 1 ) w _ u p ：w r a p p e r 接收到更新u ，然后产生一个查询q ，并把q 发送到数据源以求值。 2 ) w a r t s ：w r a p p e r 接收到数据源返回的对q 的求值结果a 。 每个事件的执行都应该具有原子性，也就是说在本地( 包装器端或数据源端) 应该有一种机制 保证某个事件的执行不会被中断，否则就会出现按先后顺序到达的事件，执行结果却不可预知的情 况。本文将采用消息队列的方式来保证这种原子性，这和w i n d o w s 的消息机制很相似。以数据源端 为例，每一个到达数据源的消息都先被放入到消息队列中，由主程序不断的扫描消息队列。如果发 现队列不为空，则从中取出消息逐条执行，这样可以保证按先来先服务的方式执行每一个消息，并 且只有当本次的消息执行完之后，主程序才能取出下一条消息执行，从而保证了事件的原子性和有 序性。 正如前面所述，m o n i t o r 所捕获到的数据源变化信息中是包含引起变化的操作的，当有元组被 插入到关系表中示，对应操作模式为1 ，当有元组被从关系表中删除时，对应的操作模式是一1 。例 如，考虑数据源发生的一个操作u l = d e l e t e ( r l ， 1 ，2 ) ，这会引起w r a p p e r 向客户端发送如下的查 询：q i2 n ( 1 ，2 r2 ) ，如果加入引起变化的操作信息，则这个查询可以表示为 q 1 2 h w , o p - m o d 。( 1 ，2 ，1 r 2 ) ，元组 1 ，2 中附加的一1 表明这是一个插入元组。假设关系表吒中 仅有元组 2 ，3 ，则q l 的结果为 1 ，一1 。这个查询结果将通过w r a p p e r 和i n t e g r a t o r 被送往某个 d e l t a 表，在使用这个d e l t a 表对数据仓库进行维护的过程中，当扫描到这个元组时，发现它的操 作模式是删除，就会将元组1 从数据仓库中相应的表中删除。如果u 。是一个插入操作，元组 1 ，2 可变换为【1 ，2 ，1 ，最终元组 1 被插入到数据仓库中相应的表内。 1 8 第p q 章数据传送和集成 一般的，对于被捕获的插入元组，其对应的动作操作模式是1 ，对于被删除的元组，其对应的 动作操作模式是一1 。当这些变化的元组被片j 于和关系表连接，以产生发往数据源的查询语句时，最 终返回的结果集也是带有操作模式的，用关系代数可以表示如下： 从上面的表示可以看出，选择操作和投影操作并不会影响元组的操作模式。当将两个元组作连接操 作时，所产生结果的操作模式刚好是这两个元组原来操作模式的乘积，下面将以t 和t ，分别为插 八元组和删除元组的情况来验证t l t2 的操作模式。当在关系表r 中插入一条元组时，对应的更 改t l 将会被捕获，并被送到w r a p p e r 端。w r a p p e r 发出查询0 l = l 。2 ，此时关系表。2 刚好被删 除一条元组，所发生的变化t 2 被送到w r a p p e r 端。因而，查询q 1 中将会多出一部分t l x t2 ，由于 。i 是插入操作，而t2 是删除操作，通过查询上面的表可知，t l t2 是一个删除操作，这就相当于 多删除了一部分元组。为了消除这样的影响，w r a p p e r 将会发出一个补偿查询一t ，x t ，前面的符 号刚好将t l t2 的操作模式反过来，相当于插入了一部分元组，这样刚好弥补了前面的删除操作。 其它的情况也可类似的解释。另外，t 1 - t2 可表示为t 1 + ( 一t2 ) ，t2 表示删除元组t2 ，因而有如下的 表达式成立： 1 ，2 ，1 卜 1 ，2 ，一1 = 1 ，2 ，1 + ( 一 1 ，2 ，一1 ) = 1 ，2 ，1 + 1 ，2 ，1 。注意，上面的+ 、一操 作都是针对元组的操作，并不是一般意义上的加、减。 从上面的讨论可知q i = d t - z 田e u q s qj 可被转化为：q f = d t + z 口，。唧q 卜u ， 。 可以将一u 前面的“一”号反映到元组u i 的操作操作模式上，即原来如果是插入操作( 1 ) ，将变成删 除操作( 一1 ) ，原来如果是删除操作，将转成插入操作。关于这个表达式的定义，将在下文中解释。 4 3 4 补偿算法 给定一个定义d t = f 研a c o d ( 毛) ) ，如果w r a p p e r 接收到一个删除操作 u = d e l e t e ( r 2 ， 3 ，4 ) ，