（计算机应用技术专业论文）利用数据沿袭改进数据清理质量的机制的研究.pdf

利用数据沿袭改进数据清理质量的机制的研究摘要 利用数据沿袭改进数据清理质量的机制的研究 学科专业：计算机应用技术 指导教师：丁晓明副教授 研究方向：数据仓库与数据挖掘 研究生：钟莉云 中文摘要 随着通信技术及网络技术的发展，互联网已经将大量的数据源联结在一起， 形成一个巨大的、分布式异构数据库环境。越来越多的应用需要集成己结构化的 异构数据源，然而，现存的大量数据源仍是半结构化甚至还未进行结构化。如何 得到格式一致，高质量的数据是提升各种应用服务质量所面临的主要问题。 数据清理是一种有效的改进数据质量的方法，被广泛运用于决策支持系统和 数据仓库系统，但在实际运用中仍有较多的不足。首先，用于数据清理的e t l 工 具的执行具有明显的单向性，无法对数据清理的中间结果进行回溯；其次，不能 对数据清理所得最终结果给出合理解释；最后，缺乏相应的用户交互机制，使用 户无法及时对数据清理程序进行必要的调整。 针对以上不足，本文在数据清理过程中引入数据沿袭机制。我们所提出的数 据沿袭机制允许对数据清理过程中每一个步骤的中间结果进行回溯，并提供交互 数据修改功能，以及时对数据清理算法及各种外部函数的参数进行修正，最大限 度地提高数据清理的质量。 为此，我们首先构造了五个可追溯操作，通过定义各个操作的详细语法，为 每个操作所得结果给出合理的解释：同时也为进一步构造由多个操作组成的数据 清理程序奠定基础。 接下来的数据沿袭机制通过传递各个操作的标识值，实现了对构造于可追溯 操作基础上的数据清理程序的追踪，从而提供了对数据清理程序执行过程及结果 的分析和解释功能；同时利用交互式数据修改功能以及时纠正和改进数据清理过 程中所出现的异常，并对数据修改过程中所涉及到的增量执行模式及操作冲突进 行了充分地分析与研究。 由于数据清理所要处理的数据量非常大，在纠正异常时引进机器学习技术以 及对聚类方法与增量执行模式之间关系的进一步研究是未来工作的重点。 关键词：数据沿袭、数据清理、数据质量 型里墼塑堂壅苎垄墼塑塑里堕墨盟垫型盟竺塞塑茎 t h em e c h a n i s mo f u s i n gd a t al i n e a g ei m p r o v i n g d a t ac l e a n i n gq u l i t y m a j o r ：c o m p u t e r a p p l i c a t i o n t e c h n o l o g y s u p e r v i s o r ：v i c e p r o f e s s o r d i n g x i a o m i n g d i r e c t i o n ：d a t aw a r e h o u s ea n dd a t am i n i n g a u t h o r ：z h o n g l i y a n a b s tr a c t w i t ht h ed e v e l o p m e n to fc o m m u n i c a t i o nt e c h n o l o g ya n dn e t w o r kt e c h n o l o g y , i n t e r n e th a sg a t h e r e dp l e n t yo fd a t as o u r c e st o g e t h e rt of o r mah u g ed i s t r i b u t e d h e t e r o g e n e o u sd a t a b a s ee n v i r o n m e n t m o r ea n dm o r ea p p l i c a t i o n sn e e di n t e g r a t e s t r u c t u r e dh e t e r o g e n e o u sd a t as o u r c e s ，w h i l eal o to fe x i s t i n gd a t as o u r c e sa r es t i l l s e m i s t r u c t u r e e do ru n s t r u c t u r e d h o wt og e tc o n s i s t e n ta n dh i 曲q u a l i t yd a t ai st h e m a i n q u e s t i o nt oi m p r o v e t h ee f f i c i e n c yo fa l lk i n d so f a p p l i c a t i o n s d a t ac l e a n i n gi se f f i c i e n t t e c h n o l o g yt oi m p r o v et h ed a t aq u a l i t ya n di sw e l l k n o w ni nt h ea r e ao fd e c i s i o ns u p p o f ts y s t e m sa n dd a t aw a r e h e u s e s h o w e v e r , t h e r e a r es t i l lm a n y i n a d e q u a n c e i nt e r m so f p r a c t i c e f i r s t ，t h ep r o c e s so f d a t ac l e a n i n gt o o l e t l ( e x t r a c t i o nt r a n s f o r m a t i o nl o a d i n g 、i s u n i d i r e c t i o n a la n dc a r l a tt r a c et h e c l e a n i n gm i d - r e s u l t ；s e c o n d ，t h ep r o c e s sl a c ks u i t a b l ee x p l a i nm e c h a n i s mt ot h e c l e a n i n gr e s u l t ；t h i r d ，t h ep r o c e s sh a v e n ti n t e r a c t i v em e c h a n i s mt ot u n et h ed a t a c l e a n i n gp r o g r a m c o n s i d e r i n gt h ei n e f f i c i e n c i e sa b o v e ，i nt h i sp a p e rw ei n , e d u c ed a t al i n e a g e m e c h a n i s mi n t ot h ep r o c e s so fd a t a c l e a n i n g t h e m e c h a n i s me a i tt r a c ee a c h c l e a n i n g m i d r e s u l tt h r o u g ha l l o p r a t e r sa n dp r o v i d ea ni n t e r a c t i v ei n t e r f a c et oc o r r e c tt h e c l e a n i n gd a t as ot h a tw ec a na d j u s tt h ed a t ac l e a n i n ga l g o r i t h ma n dp a r a m e t e r so f e x t e m a lf u n c t i o ni nt i m et or e a c ht h eb e s tq u a l i t ys t a n d a r d w ef i r s tc o n s t r u c t e df i v et r a c e a b l eo p r a t o r e sa n dc o n f i n e dt h ed e t a i l e ds y n t a xo f t h e s ef i v eo p r a t o r e ss ot h a tw ec a ne x p l a i ne a c hr e s u l to f o p r a t o r e sa n dc a nc o n s t r u c t t h em u l t i o p r a t o r e sd a t ac l e a n i n g p r o g r a m t h r o u g hp r o p a g a t e t h ek e yi n f o r m a t i o no fe a c h o p r a t o r e s ，t h em e c h a n i s mo fd a t a l i n e a g e c a nt r a c et h ed a t a c l e a n i n gp r o g r a m ，w h i c hc o n s t r u c to v e rt h et r a c e a b l e o p r a t o r ss ot h a tw e c a na n a l y s i sa n de x p l a i nt h ec l e a n i n gr e s u l t a c c o r d i n gt o t h e a n a l y s i sa n dr e s e a r c ho ft h ei n c r e m e n t a lm o d ea n dc o n f l i c to fd a t am o d i f i e a t i o n ，w e c a nc o r r e c ta n d i m p r o v e t h e e x c e p t i o n s w h i c h a p p e a rd u r i n gt h ed a t am o d i f i c a t i o n f o rt h e r ei sm u c hd a t at od e a lw i t hi nd a t ac l e a n i n g p r o g r o m ，s ou s i n gm a c h i n e l e a r n i n gt e c h n o l o g yd u r i n gt h ee x c e p t i o nc o r r e c t i o na n dt h ef u r t h e rr e s e a r c ho nt h e r e l a t i o nb e t w e e n d u s t e r i n g a n di n c r e m e n t a lm o d ei st h ed i r e c t i o no f t h ef u t u r ew e r k k e y w o r d s ：d a t al i n e a g e ，d a t ac l e a n i n g ，d a t aq u a l i t y i i 第一章引言 1 1 论文研究背景、现状 第一章引言 随着通信技术及网络技术的发展，互联网已经将大量的数据源联结在一起， 形成一个巨大的、分布式异构数据库环境。各种应用不再只是从单一的数据源中 获取数据，而是需要集成大量已结构化的异构数据源，然而，现存的大量数据源 仍是半结构化甚至还未进行结构化。因此，如何将分布如此广泛并且包含不同语 义的数据转变为格式一致的、清洁的、高质量数据成为影响各项应用服务质量 的首要问题。 数据清理技术是一种有效的改进数据质量的方法，被广泛运用于决策支持系 统和数据仓库系统，它的主要任务是从原始数据集中去除不一致的数据及错误数 据。数据仓库中的数据来自不同的数据源，通常有上百个属性、大量数据表及数 百万个元组，其中夹杂着大量格式不一致且内容重复的数据，甚至错误数据。数 据清理工具能按照预先设计好的算法通过一系列的数据抽取和转换步骤对含有 大量“脏数据”的源数据进行处理，得到预定格式和内容的数据，为数据的进一 步处理奠定基础。 目前已有许多用于数据清理的e t l 工具及数据重建工具，它们为我们提供了 功能强大的软件平台，用来支持一个复杂的数据转换链。这个数据转换链可以从 各种数据源中抽取数据，并利用一系列的数据转换操作将数据转换成无重复、无 错误并满足预定格式的数据，并将所得的最终数据重新加载回特定的数据库中。 然而，源数据中的错误越多，用固定不变的转换步骤来对数据进行自动清理就变 得越困难，因此，用户的参与是解决问题的必要途径。在现有的数据清理工具中， 并不支持专门的用户协商机制，只是将数据写入到特定的文件中用于用户事后进 行分析。在这种情况下，纠正后的数据将得不到数据清理程序的正确处理，同时， 对数据清理的结果也缺乏合理的解释机制。最后，在现存工具中，数据清理操作 只能单向执行，只有通过事后检视清理程序的日志文件才能对数据清理所做过的 操作进行逆向分析。这是目前对数据清理程序各操作步骤进行分析工作所面临的 最大障碍。 我们提出一种基于可追溯操作基础上的数据沿袭机制，利用这种机制对出现 的异常进行分析及追踪，从而实现：对所出现的异常给出语法上的解释；提供一 种用户交互机制以便对出现的异常进行分析，以及时对数据清理算法和外部调用 函数进行调整：提供数据沿袭机制，对数据清理中各个操作所得结果的源数据进 行追溯。 第一章引言 1 2 研究意义 数据库技术发展至今已在各行各业广泛应用，特别是近年来随着计算机网络 技术的发展及互联网的迅速普及，对数据的存、取不再受地域及计算机操作平台 的限制。互联网已将各种异构数据源联结在一起，形成了一个庞大的分布式异构 数据库环境。面对如此众多的数据源，如何确定各种应用所用数据的来源以及如 何确定所用数据与源数据的一致性，成为令人关注的问题。对数据沿袭机制的研 究为以上问题的解决提供了坚实的理论与实践指导，同时，也为基于网络用户授 权管理及数据仓库视图更新提供了理论依据。 其次，现有e t l 工具对来自多个异构数据源的数据进行清理的过程具有明显 的单向性，不能对所得的结果进行回溯查询，缺乏对所得结果的合理解释机制， 因此，迫切地需要有相应的技术来保证所得结果的可信度。沿袭机制提供了对每 个操作的中间结果进行向前、向后回溯查询功能，能够对每一个操作步骤所产生 的结果给出合符逻辑，清晰完整的解释。 第三，由于现存数据清理工具缺乏用户交互机制，不能及时处理数据清理过 程中出现的异常，从而影响数据清理过程的质量。沿袭机制对数据清理每个操作 步骤出现的异常作出定义，并引入用户交互纠错方式以及时处理数据清理过程中 出现的各种异常，并对用户数据清理的算法及外部调用函数进行调整，最大限度 地提高数据清理质量。 1 - 3 论文主要工作 囊 本文对视即沿袭、距离筛选优化法、近似法、数据沿袭机制及数据清理 技术等相关基础理论进行了深入的研究，并在各操作语法基础之上提出了一种数 据沿袭机制，对实现这种机制的具体操作及语法进行了详细介绍，并由此设计了 一个实验用来验证机制的可行性。最后，对数据沿袭机制所面临的问题及未来的 工作做了评价和展望。 论文分6 章，包括：1 引言；2 相关基础理论：3 数据清理过程中五个操 作的语法；4 数据清理过程中的数据沿袭；5 数据沿袭机制应用实例；6 小结 与展望。 2 第二章相关基础理论 第二章相关基础理论 2 1 数据清理概述 2 1 1 “脏数据”的类型 数据清理问题在其它领域也被称为“脏数据”处理问题。按提出的方法， 要处理的“脏数据”可以分成二类：单数据源和多数据源。 单数据源中要处理的“脏数据”全部来自同一个数据源，可按“脏数据”产 生的范围分成以下四类： 属性值：属性值丢失，属性值书写错误、缩写、一个属性值中嵌套另一个属性 值、属性值不匹配； 记录值：违反属性值之间的依赖性； 数据表：同一个属性具有不同格式，重复记录，不一致记录： 数据源：不正确地引用其它数据表内容； 当数据来源于多个数据源时，除了以上出现的问题外，还会出现以下问题： 对象识别：主要用来识别来自不同的数据源、由不同的人，在不同的时期，按 照不同的协议生成的数据是否为同一对象。 多值问题：同一个属性，不同的人会输入不同表达形式的数据： 2 1 2 数据清理的应用 将“脏数据”从信息系统中去除是以下三个领域的关键问题：单数据源的数 据清理：数据转换过程中的数据清理：数据集成过程中的数据清理。 单数据源的数据清理 数据清理被广泛用于单数据源中的异常纠正，例如：数据集成问题、属性值 的标准化过程、缺值的填充问题及重复数据的合并问题。一个非常广泛的运用是 对销售领域的客户名单列表中的姓名进行处理。另一个运用领域是对从网站上收 集到的用于电子交易的客户数据进行维护。在这种情形中，数据的准确性是至 关重要的，必须尽可能将其中的重复数据去除。 数据转换过程中的数据清理 数据清理还被运用于将未结构化的数据或结构化程度不高的数据转换成结 构化的数据。在数据转换过程中，数据清理工具被用来确定、提取遗留数据源中 相应信息，然后，对它们进行转换，最后将数据转换成所需的数据模式。 3 第二章相关基础理论 数据集成过程中的数据清理 数据仓库的构造也与数据清理密切相关。数据仓库是在多个数据源的基础上 设计、开发一个集中管理并且高度集成的数据库，在这个过程中数据清理所用系 统开销占到了数据仓库构造过程系统总开销的5 0 9 6 以上，而且，目前清理过程所 用到的大部分的程序都难以维护。 正如“”所述，在相关的信息被抽取出来之后，数据清理分别对每一个可操作 数据源进行清理动作。这样可以改进现存数据的质量，使数据的价值最大化，同 时使得传入数据仓库中的错误昂小化。 同样在“”中也谈到，构造数据仓库时e t l 的集成阶段也与数据清理密不可 分。在这个阶段，来自多个数据源的数据被转换成目标数据仓库所具有的数据模 式。对象识别问题是这个集成转换过程的一个重要组成部分。 2 1 3 数据清理应用工作过程 用于数据清理的e t l 过程包含从数据源抽取“脏数据”执行数据转换过 程并将清理结果装载到目标数据库中。 数据清理程序中包含一系列的数据转换过程，每个数据转换过程所应用的清 理标准都含有相应的启发式规则以获得准确的数据。用来评价数据清理所得数据 的质量标准比较复杂，而且高度依赖于相关知识领域的专家系统所产生的转换规 则。 数据分析工具有助于发现用户没有发现的数据问题。数据分析工具的目的在 于对数据实例进行观察并从中获得质量特征的元数据以及有用的数据模式、关 系和规则。数据轮廓( p r o f i l e ) 工具分别对每个属性的数据质量特征进行测定 ( 如：数据类型，长度，数据值的范围、离散数据频率、参照完整性、唯一性 等) ，对这些再工程元数据的分析有助于侦测数据质量问题。数据挖掘工具“”被 用于从大数据集中发现数据模式( 例如：对欺诈模式进行侦测) 。这些工具被广泛 用于商业规则发现纠正错误数据以及补全丢失数据。 清理标准被确定下来，数据转换工具就必须按标准严格执行，并且有效的地 执行相关逻辑。这些工具的使用能够减少人为检测数据，并且使编程变得更加容 易，使得不具有编程基础的商业分析人员能够使用它们，同时，e t l 工具还必须 具有定的可扩展性，能支持不同的应用域。 数据清理标准的主体部分包含复杂的商业规则“”。当这些规则被运用于大型 数据集时，执行这些标准的转换操作不能自动对整个的数据源进行清理。这是因 为正确的质量启发规则没有被完全发现，而且，数据通常将隐藏的异常封装起来。 因此，数据清理标准需要进行调整，有些还要进行重新定义或重新执行。这一系 列的活动由用户多次重复直到获得满意的数据准确性为止。另外，在某些情形下， 为了解决清理程序不能自动识别的问题，用户的参与是必要的。实际上，在某些 情形中，“脏数据”不能通过单一的清理标准处理，它们需要借助于用户的主观 4 第二章相关基础理论 判断来做出最后的选择。 2 2 视图沿袭理论 视图的沿袭追溯问题是数据仓库技术中一个重要的环节。对于给定的数据仓 库视图中的数据项，我们需要确定产生它们的源数据项的集合。 2 2 1 视图中元组的沿袭 首先，假设具有模式r 的表r 中包含有一系列的元组 t l ，t 。) ，数据库d 中包 含一系列的基本表 ，视图v 是对d 中基本表进行查询的结果。从基本 表到视图表的映射就叫做视图定义，用v 表示。如果v = v ( r 1 _ ，r 。) ，就说r l i ，r m 能导出v 2 2 1 1 视图 在定义视图时，我们使用以下符号来描述各个操作：选择( 口) ，投影( 石1 ， 连接( 嘲) ，聚类( d ) ，并集( u ) 差集( 一) 以下是各操作的标准语法： 表：r = tj t r ) 选择：盯d v l ) = t l t v l 且t 满足条件c 投影：矾( v ) = f t a i t e v ) 连接：州。( v l ，v m ) = t 1 ，t m t i e v i 其中i _ 1 ，i n 并且t i 满足条件p ) 聚类：口g g 酗b ) ( v 1 ) = t ga g 倒限唧v 1 ，r vt , t e t , t ”隹t r g = t gat ”g t g ) 并集：v 1 u u v 。= t n v i 其中i e l m ) 差集：v 1 一v 2 = t l t v 1 且圣v 2 由此，视图定义语言的语法可以描述如下： v ：r j a c ( v , ) l j r a ( v 1 ) i v lh m v m i 口q a g 呻) ( v 1 ) l v lu uv m i v l 一v 2 其中r 是基本表，v l ，v 。是视图，c 是选择条件，a 是v 中的映射属性列表，g 是v - 中的分组属性列表，a g g r ( b ) 是作用到v t 属性上的一系列聚类函数的缩写。 为了公式表达的简洁，当一个视图不止一次都用到同一个关系时，我们每次都将 它作为个不同的关系。 2 2 1 2 各种操作的元组的沿袭 根据相关的语义，每一个操作都能够得到与输入元组相对应的输出元组。对 于从操作o p 所得结果中选出的一个元组，在0 p 的输入元组中存在一个子集能生 成元组t 。我们称这个子集中的元组生成了t ，同时，我们称整个子集为t 的沿袭。 图l 表明了一个结果元组的沿袭。 5 第二章相关基础理论 t t 1 t 2 图l 元组t 的沿袭 图中操作o p 作用于表t ，和t ：上，当然t 。和t 。可能是基本表或是其它的中间 结果，通常我们用r s 来表示基本表，用t s 来表示不能明确决定是属于基本表 还是导出表的这一类的表，t 是操作的结果。给出t 中的元组t ，只有t ，子集t 1 。 和t ：子集t 2 共同产生t ，所以 叫做t 的沿袭。 定义2 1 ( 操作的元组沿袭)假设o p 为表t i ，t - 上的操作，t = o p ( t 【，t ) 。 对于给定的t e t ，我们称t l ，- ，l 中与操作0 p 对应的t 的沿袭为：0 p 。，( t ) = ( t l i 一，r i ) ，其中t l ，”，t l - 是t l i 一，t 上的最大子集，使得： ( a ) 0 p ( t l ，”，t 0 = f t ( b ) vt 。：v t t 。：o p ( t ， t + ，t 中 我们说，0 p t 。( t ) = t 。是t 在t ；中的沿袭，元组t 是t 。( i = 1 ，。m ) 中 产生t 的元组i 在定义2 1 中，条件( a ) 用来确保输入元组集合t i 能推导出t ，条件( b ) 保证 其中的每一个元组都能产生相应的输出。通过定义t i 为满足条件( a ) ，( b ) 的最 大子争集，我们就可以确定沿袭中的确包含产生t 的所有的元组，因此。沿袭 完全能用于解释为什么结果中会存在那么一个结果。 o p 1 能被扩展用来表示一个元组集的沿袭：o p “ 定理2 1 ( 沿袭的唯一性) 对于任意t e o p ( t 1 ，t 二) ，t 在口1 ，t k ) 中与0 p 相 对应的沿袭是唯一的。_ 定理2 2 ( 操作的元组沿袭关系)设1 t l ， t 。是表。t i 代表t 的模式。 o c 一小( c ) = t ) ) 其中t o r c f d 石a j 毋= 其中t s r a ( t ) 6 第二章相关基础理论 闲0 1 册) ( t ) = ，其中t e t l 嘲州t m 口g , a e 酬b ) c t ) ( c ) = ，其中t e 口g , a 目( b ) u 。t 1 ， t m ，( t ) = ，毒中t e t lu u t m - 一。t 1 卫，( t ) = ，其中t t l t 2 2 2 1 3 各种视图的元组沿袭 如果一个基本元组t 能够在一个视图演化的过程中产生元组t ，并且t 能够 进一步产生一个视图元组t ，那么t 就能产生t 。我们将所有参与产生视图元组的 基本元组称为这个视图元组的沿袭。 定义2 2 ( 视图的元组沿袭)设d 代表数据库，r 1 i ，r m 是d 中的基本表，v = v ( d ) 是d 中的视图，则对于元组t e v ： 1 当v = r i 时，视图中的元组与t e r ；相同； 2 当v = o p ( v l - ，v k ) 时，( 其中：v i 是d 中的视图定义，j = l ，k ) ，假设 t e v i ( d ) 通过0 p ( 由定义2 1 定义) ，能产生t ，同时，t e r i ，通过视图v i 产生t ，那么t 通过v 产生t 。 我们定义d 中由v 产生的t 的沿袭为：v - i “t ) = ，其中r 1 ，r 。 是r 1 ，r 。的子集，如果t e r i 通过v 产生t ，( i - 1 ，m ) ，则t e r i ，同样，我 们称r 。i 为r i 中与v 对应的t 的沿袭，记作：v - l r i ( t ) 。 视图元组集合t 的沿袭由产生t 中所有视图元组的基本元组组成： v - ! d ( 1 ) = 【j v - 1 d ( t )_ 日 定义2 3 ( 沿袭的传递性) 假设d 是具有基本表r 1 ，r 。的数据库，v = v ( d ) 是d 上的视图。如果v 同时能表示成v = v ( v l ，。v k ) ，其中7 j - v j ( d ) g = i 。，k ) 是 d 上的中间视图。对t e 、v i 为v i 中与v 对应的t 的沿袭。那么，d 中与v 对应 的t 的沿袭是所有d 中与v j0 = 1 ，k ) 对应的v j 的沿袭的串联( c o n c a t e n a t i o n ) ： n v 1 d ( t ) = * v i 。1 咖i ) 其中0 代表关系列表的m u l l ：i - w a y 串联( c o n c a t e n a t i o n ) 一 注：二个关系列表串联r l ，r o s l ，s 卫结果为：r l r ，s l ，s p 。因前面我们 已经定义过，所有重复的关系都将改用新的名字，所以同一个关系的名字不可能会出现二次。 定理2 3 ( s l j 视图沿袭的等价性)具有等价性的s p j 视图其元组的沿袭也具有 等价性。对于给定的等价s p j 视图v l 和v 2 ，v t e v l ( 】d ) = v 2 ( d ) ：v 1 - 1 啪= v f l _ 2 2 2s p j 视图沿袭的回溯 s p j ( s e l e c t p r o j e c t ：一j o i n ) 视图中元组的沿袭能够利用基本数据之上的单 一关系查询来计算。 2 2 2 1 沿袭的回溯查询 我们可以为一个特定的视图定义v 和视图元组t 写一个查询语句，当将这个 7 第二章相关基础理论 查询应用到数据库d 上时，它能返回数据库d 中的t 的沿袭。我们将这种查询 叫做t 或v 的沿袭回溯查询。 定义2 4 ( 沿袭追溯查询)假设d 为数据库，v 是d 上的视图。对于t e v ( d ) ， 如果t o ( d ) = v 1 1 d ( t ) ，那么1 q 是与t ，v 有关的沿袭追溯查询，其中v l _ 1 d ( t ) 是d 中与v 对应的t 的沿袭，并且t q 。，与d 中实例无关。我们可以类似地定义 视图元组集t 的追溯查询，并记作：t qt 。( d ) 。_ 2 2 2 2s p j 视图的回溯查询 所有的s p j 视图都可以被转换成如下形式：石a ( 口c ( r 1 闻醐r 。) ) 。我们将 这种形式称为s p j 范式。从定理2 3 中我们知道s p j 转换并不影响到视图元组 的沿袭。因此，对于一个给定的s p j 视图，我们首先将它转换成s p j 范式，然 后再利用一个基于范式的回溯查询系统地追踪它们的元组的沿袭。下面我们介绍 s p j 视图回溯查询中用到的操作。 定义2 5 ( 分割操作) 假设t 是表并且有模式t 。分割操作s p l i t 将t 分成一 系列的表，其中的每个表都是t 作用到属性a c _ t 0 = 1 ，m ) 的投影： s p l t a l ，a 1 1 f i ) = 1 定理2 4 ( s p j 视图的沿袭回溯查询)假设d 是具有基本表r 1 i ，r m 的数据库， 并且v = v ( d ) = 万“c ( r l 嘲醐r 。) ) 是d 上的s p j 视图，对于t e v ，d 中与v 对 应的t 的沿袭可以对基本表执行以下查询计算： t q t , v = s p l i t r l ，r m ( o c a = t ( r 1 h 1 1 r m ) ) 对于元组集合t v ，t 的沿袭回溯查询为： t q l v = s p l i t r l ，r m ( 口c ( r l 酗l 叫r m ) k 1 ) 。 其中，k 是关系的半连接( s e m i j i o n ) 操作。 一 2 2 2 3 回溯查询的优化 定理2 5 ( 使用关键信息的沿袭追溯)假设r 1 是具有关键属性i ( i ( i = 1 ，m ) 的 基本表，视图v = 万a ( 仃c 皿l 嘲旧r m ) ) 包含所有基本表的关键属性，那么，视 图元组t 的沿袭为： _ 根据以上定理，我们能使用关键信息从基本表中直接取得元组的沿袭。最坏 查询复杂度由o ( n m ) 减少到o ( m n ) ，其中n 是基本表的最大值，m 是定义了v 的基 本表的数目。 2 2 3a s p j 视图的沿袭查询 现在我们来考虑集成的s p j 视图。尽管我们已经说明s p j 视图的沿袭回溯过 程中不必使用中间结果，然而，对于a s p j 视图来说，如果不对中间结果进行排 序或重新计算，那么a s p j 视图是不能进行回溯操作的。 2 , 2 3 1a s p j 视图的范式 和s p j 视图不同的是，a s p j 视图不存在一个简单的范式，因为在个a s p j 视图定义中一些选择、映射和连接操作不能被移动。然而，通过对s p j 视图的 8 第= 章相关基础理论 交换和组合，可以将任何a s p j 视图转换成由操作序列口一一盯一| ：组合而成的 形式，我们叫做a s p j 片段。我们将这种表达形式称为a s p j 范式。一个a s p j 片段可以省略操作，尽管a s p j 范式中除了最外层的操作之外的每一个片段，都 必须包括一个聚类操作，否则就必须用一个邻接的部分来将这部分合并。表的合 并恢复操作为：诉，投影恢复操作：j l t 选择恢复操作：d l 。 定义2 6 ( a s p j 范式)假设v 是d 上的a s p j 视图定义。 1 v = r ，具有a s p j 范式，其中r 是d 中的基本表。 2 如果7 ja = 1 ，k ) 是具有a s p j 范式且最顶层包含非恢复合并操作的a s p j 视 图，那么，v = 口g , a 黯啦) ( 石“仃c ( v 1 州喇v k ) ) ) 具有a s p j 范式。 2 2 3 2 单层a s p j 视图的沿袭回溯查询 由a s p j 片段定义的视图叫做单层a s p j 视图，我们能够用一个查询来追踪 单层a s p j 视图的元组沿袭。 定理2 6 ( 单层a s p j 视图的沿袭追溯查询)单层a s p j 视图 v = v ( r 1 ，r m ) = 口蛳磐 ( 玎“口c ( r l 蹦阳r 。) ) ) 中，对于元组t v ，在 r 1 ，r 。中与v 对应的t 的沿袭由以下查询计算： t q i ，= s p l i t m ，r i l i ( 盯c ag 篁t g 僻1 冈n r 。) ) 对于元组集合t c v ，t 的沿袭回溯查询是： t q t ，v ：s p u t r l ，r m ( 仃c ( r i 喇触r 。) d_ 2 2 3 3 多层a s p j 视图的沿袭回溯算法 对于一般a s p j 视图，我们首先将视图转换成a s p j 范式，并将它分成一系 列的a s p j 片段，同时，为每一个片段定义一个中间视图，然后，再循环自项向 下地逐层追溯元组的沿袭。在每一层我们使用单层a s p j 视图的回溯算法来进行 处理。 p r o c e d u r et u p l e d e r i v a t i o n ( t ，v ，d ) i n p u t ： a t r a c i n gt u p l et ，av i e wd e f i n i t i o nv ，a n dad a t a b a s ed o u t p u t ：t sd e r i v a t i o ni nda c c o r d i n gt ov b e g i n r e t u r n ( t a b l e d e r i v a t i o n ( t ，v ，d ) ) ； e n d p r o c e d u r et a b l e d e r i v a t i o n ( t , v , d ) i n p u t ： a t r a c i n gt u p l es e tt , av i e w d e f i n i t i o nv ，a n dad a t a b a s ed o u t p u t ：t sd e r i v a t i o ni nd a c c o r d i n g t ov b e g i n i fv = r e dt h e nr e t u r n ( t ，) ； 9 第二章相关基础理论 o t h e r w i s ev = v 。( v 1 ，v k ) w h e r ev i sao n e l e v e la s p jv i e w , 粥= v j ( d ) i s a ni n t e r r a e d i a t ev i e wo rab a s et a b l e ，j - - 1 ，- - ，k ( v 。1 ，v + k ) , - - t q ( t , v ， v i ，v d ) r e t u r n ( t a b l e l i s t d e r i v a t i o n ( ) ， v i ，。，v d ，d ) ； e n d p r o c e d u r et a b l e l i s t d e r i v a t i o n ( ， v l ，v k ，d ) i n p u t ：a l i s t o f t u p l es e t s t l ，t k t o b e t r a c e d , al i s to f v i e wd e f m i t i o n sv l ，v k , a n dad a t a b a s ed o u t p u t ：t h e c o n c a t e n a t i o no ft j sd e r i v a t i o n sa c c o r d i n gt ov i ，i = l ，k b e g i n d + _ 中： f o r j 1 1t o k d o d + - d o t a b l e d e r i v a t i o n ( t i ，v j ，d ) ； r e t u r e ( d + ) ； e n d 图2a s p j 视图沿袭算法 图2 说明一般a s p j 视图的沿袭算法。对于a s h 范式中的一个给定视图定 义v ，t e v ( d ) ，过程t u p l e d e r i v a t i o n ( t ，v ，d ) 负责根据d 中的v 来计算t 的沿袭。 算法中的主要计算由过程t a b l e d e r i v a t i o n ( t ，v ，d ) 承担，它主要完成根据d 中 的v 来计算元组集t v ( d ) 的沿袭。正如前述，我们假设v = v ( v l 一，v k ) ，其中 v 。是一个单层a s p j 视图，并且v j = vj ) ( j = l ，r o l e ik ) 是作为一个基本表或一个 中间视图。这个算法首先使用定理2 6 所定义的单层a s p j 视图回溯查询 t q ( r , v ， ) 来计算t 在 中的数据沿袭 ，然后，再 调用过程t a b l e l i s t d e r i v a t i o n ( v 。，v i * ) ，f v “，v 。) ，d ) 来计算与v j 对应的 元组集v l ( j = l ，k ) 中每个元组的沿袭，同时，将结果进行连接形成视图元组 集合的完整列表的沿袭。 2 2 4 多步操作视图沿袭的回溯查询 这一节，我们将视图的沿袭回溯算法扩展到一般a s p j 视图，使之适用于视 图定义中任意的并集及补集操作。 2 2 4 1 一般视图的范式 现在我们定义一个扩展的范式，其中包含视图并使用并集和补集，阻及聚类 、选择、映射和连接操作。扩展的范式是由二部分组成： a u s p j - s e g m e n t ：以口一u 一石一1 9 一刚这种形式出现的操作序列； d s e g m e n t ：包含一个差集操作。 a u s p j s e g m e n t 可以忽略操作序列口一u 一一仃一列中的任何操作，但是它 1 0 苎三兰塑羞兰型里丝一 必须满足以下的任一条： 1 操作的顶层有一个聚类操作； 2 a u s p j s e g m e n t 紧接在d - s e g m e n t 之后； 3 它位于联结操作之后，并且前面有其它的操作 4 它处于视图定义的最前端； p r o c e d u r ec a n o n i c a l i z e ( v 0 ) i n p u t ： a g e n e r a l v i e wd e f i n i t i o nt r e ev o o u t p u t ： ac a n o n i c a l i z e dv i e wd e f i n i t i o nt r e ev w i t hf i ni n t e r m e d i a t ev i e w a s s o c i a t e dw i t he a c hs e g m e n ti nv b e g i n c o p y v o t o v ； p u l lu n i o no p e r a t o r sa b o v e s e l e c t i o n sa n d p r o j e c t i o n s i nv ； p u l lp r o j e c t i o no p e r a t o r sa b o v ej o i n sa n d s e l e c t i o n si nv ； p u l ls e l e c t i o no p e r a t o r sa b o v ej o i n si nv ； m e r g e t h es a m e a l g e b r ao p e r a t o r sa d j a c e n tt oe a c h o t h e ri nv ； d i v i d evi n t os e g m e n t s ； d e f i n ea l li n t e r m e d i a t ev i e wo v e re a c hs e g m e n ti nv ； r e t u r n ( v ) ； e n d 图3 一般视图定义的范式 图3 中提出了一个范化过程，它将一个通用的视图定义转换成范式，首先将 视图定义划分成多个部分，然后，为每个部分分配一个中间视图。规范