（计算机软件与理论专业论文）面向数据集成的数据清理关键技术研究.pdf

u n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g yo fc h i n a adi s s e r t a t i o nf o rd o c t o r sd e g r e e da t acle anin g ind a t a in t e gr a t i o n a u t h o r sn a m e ： j i el i u s p e c i a l i t y ：c o m p u t e rs o f t w a r ea n dt h e o r y s u p e r v i s o r ：p r o f t a oh u a n g f i n i s h e dt i m e ： o c t o b e r , 2 010 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名：独查! 签字日期： | 矿i 口i t z 4 - 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 忆忪开口保密( 年) 作者签名：导师签名： 签字日期：垫! ! ：! ! ：圣! 摘要 摘要 数据清理是企业数据集成领域重要且热门的研究问题。随着企业应用日益 复杂，企业数据的质量及其管理代价成为越来越受关注的方面。传统的企业数 据质量管理基于静态质量规则来刻画和保障，在扩展性和自动化处理方面难以 满足企业应用的需求。如何以完整性约束理论为基础，自动化地推理和挖掘数 据清理规则并保证数据的一致性，是数据质量保障一个新的热点问题。本文针 对企业数据集成领域的数据质量保障问题，研究高效地检测和清理不一致数据 的方法与技术。 首先，本文提出了一种基于反向约束传播的异常数据检测方法，根据数据 集成目的端的质量约束推理源端需要满足的质量约束，从而在源端进行异常数 据检测。在数据集成流程中，数据源端的数据经过流程处理后，可能会将违反 目的端的完整性约束，导致不成功的加载或者成为目的端数据库中的脏数据， 因为数据量大，而且可能存在远程的数据传输，通过执行调试的方法来定位问 题数据的代价太大。本论文中提出反向约束传播( b a c k w a r d sc o n s t r a i n t p r o p a g a t i o n ，b c p ) 的方法，首先将数据集成流程建模为有向无环图，然后自动 将目的端数据库的完整性约束沿着数据流反方向，向数据源端推理。文中采用 一阶逻辑定义并证明面向基本关系代数操作的约束传播规则，并定义约束传播 规则支持采用属性映射和元组映射两个抽象操作标注的复杂数据操作，使b c p 可以支持大多数类型的数据操作。案例分析及实验表明该方法可以有效辅助捕 获异常数据并提高数据集成流程的设计效率。 其次，本文提出基于n u l l 修复的一致性查询方法，支持对不一致数据源在 查询时自动过滤不一致的属性信息。多个数据源的数据集成后，因为缺乏足够 的辅助信息进行清理，可能存在大量违反完整性约束的数据。一致性查询技术 ( c o n s i s t e n tq u e r ya n s w e r i n g ，c q a ) 研究如何在查询时采用虚拟修复的方法 获取一致的结果，但已有的方法大多基于元组删除的修复方法，可能导致信息 丢失，而且对于大多数约束求解c q a 是n p 问题。我们将约束类型限制在属性级， 即只有违反约束的属性为不一致信息，并提出基于n u l l 的修复语义，将所有不 一致属性使用n u l l 替换得到虚拟修复。当进行n u l l 修复后可能会产生新的不 一致属性，针对该问题提出约束扩展算法，通过一轮检测定位所有可能的不一 致属性。然后，基于n u l l 修复语义给出了s q l 重写算法来实现c q a 。文中进行 了实验与性能分析，表明该方法计算复杂度与数据库规模、不一致数据比例、 查询类型成线性比例关系。 摘要 再次，本文提出了一种数据清理流程的通用优化框架，支持对数据清理流 程操作的自动重构，优化流程的执行效率。随着数据量飞速的增长，性能成为 数据清理的瓶颈，如果对数据清理流程的逻辑模型进行优化，可以在不增加资 源的情况下获取性能的提升。本文提出一个框架，通过对流程进行语义等价的 结构变换生成备选流程，并预测各备选流程的执行代价选择最优的流程。支持 对操作组件标注其操作语义的特征属性，定义特定领域的流程变换规则，同时 提出根据流程代价相对关系来构建代价偏序图，提高流程选择的精确度。为了 表明该框架的通用性和有效性，将其应用到w e b 数据m a s h u p 工具中，实验表明 可以有效降低m a s h u p 的响应时间。 最后，本文研究开发了模型驱动的数据集成流程的开发平台o n c e d q ，并在 其上对提出的数据清理新技术进行了实现和应用。该平台支持用户可视化的设 计流程，并采用代码生成工具将流程自动生成平台独立的j a v a 代码，支持跨平 台部署。该平台基于o s g i 框架支持用户自定义操作组件和数据源接口。 关键词：数据集成数据质量完整性约束数据仓库数据清理性能优化 a b s t r a c t a b s t r a c t d a t ac l e a n i n gi sv e r yi m p o r t a n ti ne n t e r p r i s ed a t ai n t e g r a t i o n d u et o l a r g e a m o u n to fd a t aa n dt h ei n c r e a s i n gc o m p l e x i t yo fb u s i n e s si n t e l l i g e n c e a p p l i c a t i o n r e q u i r e m e n t s ，i ti sh a r dt oe n s u r et h ei n t e g r i t y , c o n s i s t e n c ya n da c c u r a c yo fd a t a i ti s e r r o r - p r o n ea n dl a b o r - i n t e n s i v et od e v e l o pd a t ai n t e g r a t i o np r o j e c t sd u et od a t aq u a l i t y i s s u e s i n t e g r i t yc o n s t r a i n t sp r o v i d eu s e raw a yt od e f i n et h ed a t ad e p e n d e n c i e si na d e c l a r a t i v ew a yt oe n s u r et h ec o n s i s t e n c ya n dt h e r e a r es o u n dt h e o r yb a s i st od o i m p l i c a t i o na n a l y s i so fi n t e g r i t yc o n s t r a i n t s i t i sah o ta r e at oi n d u c ea n dm i n ed a t a q u a l i t yr u l e sb a s e do nc o n s t r a i n tt h e o r i e s t h i st h e s i st a r g e t so nt h i sp r o b l e mi nt h e i n t e g r a t i o ns c e n a r i ot op r e s e n tn e wm e t h o dt oa u t o m a t i c a l l ya n de f f i c i e n t l yd e t e c ta n d c l e a nt h ed a t a f i r s t , w ep r e s e n tam e t h o dt oi n d u c et h ed a t aq u a l i t yc o n s t r a i n t sf o rt h ed a t a s o u r c e sf r o mt h ed a t aq u a l i t yc o n s t r a i n t sd e f i n e do nt h et a r g e td a t a b a s ei nad a t a i n t e g r a t i o nf l o w t h ed a t aq u a l i t yi nad a t as o u r c em a ye x c e e dt h ee x p e c t a t i o n so f d e s i g n e r sa tt h ed e s i g nt i m ew h e nv a l i d a t i o na n dt r a n s f o r m a t i o nr u l e sa r es p e c i f i e d ， a n dt h i sw i l lc a 峨u n s u c c e s s f u ll o a do ft a r g e td a t a b a s ed u et oc o n s t r a i n tv i o l a t i o n so r f l u s hd i r t yd a t ai n t ot h et a r g e td a t a b a s e d u et ol a r g ea m o u n to fd a t a , a n dt h e r em a y n e e dt ot r a n s f e rd a t ab e t w e e nd i s t r i b u t e ds e r v e 俗，i ti sc o s t l yt od e b u gt h ed a t a i n t e g r a t i o nf l o wb ye x e c u t i n gi t i nt h i sp a p e r , w ed e s i g nag e n e r a lf r a m e w o r kf o rt h e p r o b l e m ，c a l l e d b a c k w a r d sc o n s t r a i n tp r o p a g a t i o n ( b c p ) ，w h i c ha u t o m a t i c a l l y a n a l y z e sad a t ai n t e g r a t i o nf l o w , g e n e r a t e sd a t aq u a l i t yr u l e sf r o mt h e c o n s t r a i n t s d e f i n e di nt h ed w , a n dp r o p a g a t et h e mb a c k w a r d sf r o mt a r g e tt os o u r c e s t h ed e r i v e d d a t aq u a l i t yr u l e sc a nb eu s e dt od e t e c te x c e p t i o n a ld a t ai nt h ed a t as o u r c e sa n dh e l p d e s i g n e r si m p r o v et h ed i f s b c ps u p p o r t sm o s tr e l a t i o n a la l g e b r ao p e r a t o r sa n dd a t a t r a n s f o r m a t i o nf u n c t i o n sb yd e f i n i n gc o n s t r a i n tp r o p a g e a t i o nr u l e s c a s es t u d i e sa n d e x p e r i m e n t sa r ep r o v i d e dt od e m o n s t r a t et h ec o r r e c t n e s sa n de f f i c i e n c yo fb c e s e c o n d ，w ep r e s e n tam e t h o dt oa u t o m a t i c a l l yf i l t e rt h ei n c o n s i s t e n ta t t i r b u t e s f r o md a t as o u r c e sb a s e do nv i r t u a lr e p a i rb yn u l l a l t h o u g hi n t e g r i t yc o n s t r a i n t sc a n s u c c e s s f u l l yc a p t u r ed a t as e m a n t i c s ，t h ea c t u a ld a t ai nt h ed a t a b a s eo f t e nv i o l a t e ss u c h c o n s t r a i n t s w ec a na p p l yc o n s i s t e n tq u e r ya n s w e r i n g ( c q a ) t og e ta na n s w e rw h i c h i st r u ei ne v e r ym i n i m a lr e p a i ro ft h ei n c o n s i s t e n td a t a b a s e i th a sb e e np r o v e dt h a tf o r m o s tc o n s t r a i n t sa n dq u e r i e sc q ai san pp r o b l e mb a s e do nr e p a i r i n gb yt u p l e i i i a b s t r a c t d e l e t i o n so rt u p l ei n s e r t i o n s f u r t h e r m o r e ，r e p a i r i n gb yd e l e t i n gt u p l e sw i l la l s oc a u s e i n f o r m a t i o nl o s i n g i nt h i sp a p e rw ep r e s e n tan e wr e p a i rs e m a n t i c sn a m e dr e p a i r i n g 丽t hn u l l s ，w h i c hr e p l a c e st h ei n c o n s i s t e n ta t t r i b u t ev a l u e sw i t hn u l l s t oc a p t u r ea l l t h ei n c o n s i s t e n ta t t r i b u t ev a l u e s ，w es t u d yt h et r a n s i t i v i t yo fn u l l sa n dp r o v i d ea n a l g o r i t h mt oe x t e n dt h eo r i g i n a lc o n s t r a i n t s b a s e do nr e p a i r i n g 谢t hn u l l s ，t h e r ew i l l b eo n l yo n er e p a i ra n dc q ac a r lb ec o m p u t e di np t i m eb ys q lq u e r yr e w r i t i n g s f i n a l l y , e x p e r i m e n t ss h o wt h ec o m p l e x i t yo fo u tn e wa p p r o a c hf o rc q a i si nl i n e a r r e l a t i o n 晰t 1 1t h e s c a l eo fd a t a b a s e ，t h ep e r c e n to fi n c o n s i s t e n c ya n dt h eq u e r y c a t e g o r i e s t h i r d ，w er e s e a r c ho ne n h a n c i n gt h ep e r f o r m a n c eo fd a t ac l e a n i n gp r o c e s s e sv i a a u t o m a t i c a l l yr e f a c t o r i n gt h es t r u c t u r eo fi t sd a t af l o w s f i r s tas e to fo p e r a t i o n a l s e m a n t i c sf e a t u r e s a r es e l e c t e df o ra n n o t a t i n gt h eo p e r a t o r si nd a t af l o w sa n d r e f a c t o r i n gr u l e sa r ed e f i n e dt og e n e r a t ea l lc a n d i d a t es e m a n t i c se q u i v a l e n td a t af l o w s t h e nah e u r i s t i ca l g o r i t h mi sd e s c r i b e df o ra c c u r a t e l ya n dq u i c k l ys e a r c h i n gt h ed a t a f l o wo fm i n i m a le x e c u t i o nt i m eb yc o n s t r u c t i n gap a r t i a l l yo r d e r e ds e to fd a t af l o w s b a s e do nt h e i rc o s te s t i m a t i o n t ov a l i d a t et h ef r a m e w o r k , w ea p p l yi tt om a s h u p s c a s es t u d ys h o w st h ef r a m e w o r ki sa p p l i c a b l et og e n e r a lm a s h u pd a t af l o w sw i t h o u t k n o w i n gc o m p l e t eo p e r a t i o n a ls e m a n t i c so f t h e i r o p e r a t o r s a n dt h e e f f i c i e n c y i m p r o v e m e n ti sd e m o n s t r a t e db ye x p e r i m e n t s f i n a l l y , w er e s e a r c ho nm o d e ld r i v e nd e v e l o p m e n tm e t h o df o rd a t ai n t e g r a t i o n f l o wa n di m p l e m e n tad e v e l o p m e n tp l a t f o r m t h ed e t a i l so fi m p l e m e n t i n go u rn e w d a t ac l e a n i n gt e c h n i q u e si nt h es y s t e ma r ed i s c u s s e d k e yw o r d s ：d a t ai n t e g r a t i o n , d a t aq u a l i t y , i n t e g r i t yc o n s t r a i m ，d a t aw a r e h o u s e ， d a t ac l e a n i n g ，o p t i m i z a t i o n i v 目录 第1 章 1 1 1 2 1 3 1 4 第2 章 2 1 目录 绪论：1 研究背景 问题分析 研究内容 论文的组织结构 相关工作研究现状9 数据集成与数据质量9 2 1 1 数据集成系统9 2 1 2 数据质量管理1 0 2 1 3 研究问题1 4 2 2 数据集成流程建模与优化1 5 2 2 1 流程建模与设计1 6 2 2 2 流程性能优化1 8 2 2 3 研究问题2 0 2 3 基于约束理论的数据清理技术2 0 2 3 1 理论基础2 1 2 3 2 一致性查询2 2 2 3 3 面向数据清理的约束扩展2 3 2 3 4 研究问题2 4 2 4 小结2 4 第3 章数据集成流程中的异常数据检测2 7 3 1 引言2 7 3 2 问题定义2 8 3 2 1 数据集成流程2 8 3 2 2 数据质量规则2 9 3 2 3 异常数据检测3 0 3 2 4 一个例子3 1 3 3 反向约束传播框架3 2 v 目录 3 4 基于关系代数的投影规则3 5 3 5 基于语义标注的复杂转换操作的投影规则3 8 3 6 投影方法分析与比较4 6 3 7 实验评价4 7 3 8 相关工作4 9 3 9 小结5 0 第4 章基于n u l l 修复的一致性查询5 1 4 1 引言5 1 4 2 理论基础5 3 4 3 定位不一致属性5 6 4 4 查询重写方法6 0 4 4 i 非聚集查询6 0 4 4 2 聚集查询6 2 4 5 实验评价6 7 4 5 1 实验设置6 7 4 5 2 实验结果6 8 4 6 相关工作7 0 4 7 小结7 1 第5 章基于重构的数据清理流程性能优化7 3 5 1 引言7 3 5 2 问题定义7 4 5 3 数据流程变换规则7 6 5 4 最优流程选择算法7 8 5 5 案例分析与实验8 0 5 5 1m a s h u p 案例8 0 5 5 2 实验设置8 3 5 5 3 流程优化的效果8 3 5 5 4 最优流程选择算法8 5 5 6 相关工作8 5 5 7 小结8 6 第6 章数据清理技术在数据集成系统中的实现与应用8 7 6 1数据集成流程开发平台架构8 7 6 i 1 数据处理组件模型8 8 v i 目录 6 1 2 数据集成流程管理9 1 6 2 数据清理技术的实现9 3 6 2 1 反向约束传播的实现9 4 6 2 2 一致性查询的实现9 9 6 2 3 流程性能优化技术的实现1 0 0 第7 章总结与展望1 0 3 7 1 工作总结1 0 3 7 2 进一步工作1 0 3 参考文献1 0 6 致谢1 1 3 在读期间发表的学术论文与取得的研究成果1 1 4 v l i 目录 第l 章绪论 第1 章绪论 1 1 研究背景 数据集成是把不同来源、不同格式、不同语义的数据在物理上或逻辑上有机 地集中，从而提供一个统一的视图的过程。企业数据集成涵盖数据同步、数据迁 移、数据整合、数据质量等业务类型( i d c ，2 0 0 8 ) 。数据集成是现代信息学的里 程碑，每一个企业、组织，甚至个人每天都要处理广泛的数据源，数据集成也无 处不在。当一个企业并购另外一个企业后，需要将两个企业的数据信息进行集成； 一个卫生组织需要将来自各个医院、医生、实验室的信息进行集成，进行管理研 究；一个旅行者需要将来自多个旅行网站的信息进行集成来筹划适合自己的行程 ( h a s se ta 1 ，2 0 0 9 ) 。 数据集成涉及许多问题( h a s s ，2 0 0 7 ；h a l e v ye ta 1 ，2 0 0 6 ) ，不同的计算环 境，不同数据源类型，不同的集成目标都促使产生大量的数据集成技术和工具， 来完成具体的任务。有的工具负责进行相似对象识别，有的工具协助进行不同数 据源的模式匹配，有的工具则进行数据的清理，还有的工具辅助设计数据处理流 程等等( h a s se ta 1 ，2 0 0 9 ) 。数据仓库( d a t aw a r e h o u s e ) 和数据联邦( d a t a f e d e r a t i o n ) 是两个主要的数据集成技术，前者采用e x t m c t t r a n s f o r m l o a d ( e t l ) 工具将不同来源的信息都集成到一个统一的数据库中进行管理分析，后者是一种 虚拟集成，只是查询的时候到各数据源查询然后汇总为一个统一的结果。数据仓 库的构建可能需要几个月的时间，而数据联邦则提供实时的集成查询。两个技术 都需要额外的工具进行数据的清理与相似对象的识别。 图1 1 所示的例子，对两个部门的信息系统进行了集成，图中表示了四种集 成的模式( h a s s ，2 0 0 7 ) ，适合不同的集成目标。e t lj o b 和f e d e r a t i o n 已经介绍 过了，r e p l i c a t i o n 表示数据的复制，广泛存在于集成的过程中，可以看作是e t l j o b 的最简单的形式。c r a w l e r 表示对分散的数据源进行抓取内容，并建立索引， 提供搜索的服务，这也可以看作是数据联邦的一种特例，只是大多采用模糊的查 询方法。由此看来，数据集成的概念广泛存在，互联网的搜索引擎也可以看作是 一种数据集成应用。 第1 章绪论 f e d e r a t i o n r e p l i c a t i o n c r a w l e r 一 图1 1 四种数据集成模式 数据集成需求持续增长，i d c 调查显示，7 0 的企业正在建设或已经建设数 据集成新项目( i d c ，2 0 0 8 ) 。一个因素是数据集中管理已经成为中国金融、电信、 以及各级政府部门建设r r 系统的主要方向。另外，搜索引擎、信息门户、m a s h u p 等蓬勃发展，也都对w e b 数据集成产生新的需求。因此，数据集成的相关研究一 直都是信息系统领域的重要组成部分。 数据质量问题常常导致大量数据集成项目无法达到预期，导致项目延迟完 成，并大大增加了项目成本( i d c ，2 0 0 8 ) 。一方面数据集成环境复杂，数据的 完整性、一致性、准确性难以保障，存在大量异构系统的集成，遗留系统又缺乏 准确的元数据。另一方面，实施者对数据质量缺乏足够的分析处理，影响分析结 果的准确行和用户统一视图的全面性。低质量数据会给企业和国家带来巨大经济 损失，最近的统计分析显示脏数据每年给美国带来2 5 0 亿美元的损失( t d w i ， 2 0 0 9 ) 。数据质量包括多个维度，比如准确性、一致性、完备性、及时性、重复 性等，在实际的项目中需要综合考虑，并制定各个维度的指标，在项目实施的不 同阶段进行质量的监控和管理。图1 2 则表示了数据集成过程中可能存在的质量 2 第l 章绪论 问题的分类，因为存在异构数据源，比单数据库数据质量保障复杂的多。 数据质盘问露 单数据源问西 模式层实例层 多数据源 模式层 ( 缺少约束定义)( 输入错误) ( 舅构数据模型 或模式设计) 不符台嚏性拼写错误 名称冲突 不符合外镂 重复记录 络构冲突 冲突记录 层 惹苎：j 哮突、 闯题来源 不一致) “一1 一 数据时问不致 闯题例子 字段格式不同 重复记录 图1 2 数据集成中的数据质量问题 数据集成是近2 0 年来数据管理领域重要组成部分，( l e n z e r i n i ，2 0 0 2 ) ， ( h a i e v y o ta 1 ，2 0 0 6 ) ，( h a a s ，2 0 0 8 ) 分别从理论角度，技术角度，企业需求角 度对数据集成的技术发展进行了全面的总结。国内研究者对数据集成领域也做出 了很多贡献，( 孟小峰等，2 0 0 4 ) 在介绍数据库领域发展趋势时，列在第一位的 就是信息集成。数据质量是数据集成中不可避免的问题，数据集成本身也可以看 作是提高数据质量的手段，( r a h m ，2 0 0 0 ) 对数据集成中的数据清理给出了总结， 研究界针对相似对象识别，模式匹配，数据源分析等问题发表了一系列的成果。 本文重点研究面向数据集成的数据清理的关键技术，动机是因为在实际的数 据集成中间件开发和应用中，发现不一致数据给数据集成带来很大的处理代价， 比如分布在两地的数据进行交换时，发送端的数据很多时候存在不符合接收端要 求的数据，只能采用记录日志的办法后续进行调试，比如数据源存在很多问题数 据时，虽然信息很丰富，因为存在不一致性，而无法被实际应用采用。这些问题 传统的数据质量技术都不能很好的解决。 关系数据库中的数据依赖，即完整性约束，研究者已经进行了充分的研究。 完整性约束常常被用于查询优化和阻止非法的更新操作，并且通过正规化改进模 式的质量。最近完整性约束重新被人们关注，用于提高数据的质量。主要包含两 部分工作，一部分基于完整性约束理论进行不一致数据库修复和查询，另外一部 分研究者对经典的完整性约束类型进行修改和扩展，从而捕获显示生活中更多的 数据错误( f a n ，2 0 0 8 ) 。这些技术拥有很好的理论基础，基于完整性约束和关 系代数的相关理论，支持数据清理规则的推理和挖掘，为企业数据集成中的数据 3 第1 章绪论 清理带来了新的思路。本论文在这样一个背景下，针对数据集成系统中一些尚未 解决的问题，提出创新的方法进行解决。 1 2 问题分析 本论文选择了面向数据集成的三个数据清理问题进行研究，包括数据集成流 程的异常数据检测问题，不一致数据源的一致性查询问题，和数据清理流程的自 动性能优化问题。下面给出概要的问题分析，相应的问题在对应的章节会通过示 例给出详细的说明。 在数据集成系统应用中，数据可能来自传统的关系数据库系统，也可能来自 多样化格式的数据源，比如w e b 数据源。数据集成系统中的数据处理操作除了涵 盖基本的关系代数操作外，还包含复杂的数据清理过程。在数据集成系统中，来 自数据源的数据质量具有很大不确定性，这些数据可能违反数据集成流程中的验 证规则、转换规则，导致流程执行错误，无法加载到数据仓库中，更严重的会成 为数据仓库中的脏数据造成错误的商业智能决策后果。因为数据量大，而且可能 存在远程的数据传输，通过执行调试的方法来改进流程设计的代价太大。而据报 告，数据仓库项目的7 0 的代价在于构建e t l 。本文提出一个新的研究问题，即： 在数据集成流程设计时，如何检测数据源中的哪些记录经过流程处理后会违反目 的端的质量规则。如果我们可以在设计时对数据集成流程进行验证，找到所有可 能的异常数据，那将给设计者提供丰富的信息来改进流程的设计，比如添加过滤 器。如果可以实现，将大大提高流程设计的效率。 数据集成系统应用中，数据源可能存在违反其完整性约束的数据，如果要集 成这些数据就要将不一致数据进行检测和过滤。一种方法是采用流程将所有数据 都先转移到一个临时的数据中心，然后进行数据清理，还有一种方法就是在数据 集成流程中添加过滤操作直接获取一致数据。当约束比较复杂，或者存在多个约 束时，很难人工的定义过滤操作。从不一致数据库查询一致的结果的问题研究者 进行了大量理论研究，被定义为数据库的一致性查询( c q a ，c o n s i s t e n tq u e r y a n s w e r ) ( a r e n a se ta 1 ，1 9 9 9 ) 。已有的研究都是基于某种修复语义来研究查询 的方法，在某种修复语义下，所有可能的修复结果中查询的结果的交集就是一致 性的结果。对于大多数约束和查询来说，基于元组删除操作的修复c q a 都是一 个n p 问题。更进一步说，基于元组删除的修复方法会导致信息丢失。这些研究 还都停留在理论层面，由于复杂度的问题无法直接应用到数据清理中来。问题的 难点在于针对特定的领域，提出合理的修复语义，并使c q a 的计算复杂度达到 多项式量级。 数据清理也可以类似数据集成一样建模为流程，数据清理流程是数据集成流 4 第1 章绪论 程的一种，只是包含的操作组件有差异。e t l 工作流的逻辑优化问题在( s i m i t s i s e ta 1 ，2 0 0 5 b ) 进行了研究， 将每一个e t l 工作流逻辑模型定义为一个状态，提 出了一系列流程的等价语义变换的规则，对于流程中的操作节点可以采用次序交 换、合并拆分、并行等来改变流程的结构，比如过滤的操作尽可能提前做就可以 提高流程的执行效率。然后提出基于状态空间搜索的优化方法寻找最优的等价流 程，并研究了启发式的改进算法。该研究提出了几种规则，但是只适用于e t l 中几种特殊的操作，无法将该方法直接应用于数据清理流程等其他应用场景中。 另外该方法中基于性能预测的流程选择也存在精确度的问题，因为有的流程无法 计算出执行时间，因为操作组件的执行时间预测的重要参数是其输入的记录个 数，对于过滤器类组件，他们的输出是和输入数据的内容有关的，很难预测，导 致后继组件的性能预测存在误差。针对这些问题，需要研究一个更为通用的数据 清理流程优化框架。 1 3 研究内容 图1 3 研咒内容 论文对数据管理领域相关研究工作进行了广泛和深入的调研，以基于约束的 数据清理技术为基础，对数据集成流程中异常数据检测、数据源一致性查询、数 据清理流程的性能优化等方面进行了研究。如图1 4 所示，图中的流程可以表示 数据集成流程和数据清理流程。研究围绕数据集成系统中的数据清理技术为核 心，数据集成流程异常数据检测是采用反向约束传播( b a c k w a r d sc o n s t r a i n t s p r o p a g a t i o n ) 根据目的数据库的质量约束对数据源端数据库进行检测，基于n u l l 5 第1 章绪论 修复的一致性查询( n u l l - c q a ) 是根据源端的质量约束从不一致的数据源获取一 致干净的数据，数据清理流程的重构及优化( d a t ac l e a n i n gf l o wr e f a c t o r i n g ) 则是为了提高数据清理操作执行的性能。同时还对可扩展的数据清理流程的开发 平台技术进行了研究和实现。具体的研究内容接下来分问题介绍。 数据集成流程的异常数据检测 如果数据源s 的质量规则集x 可以由目的端d w 的质量规则集y 推理得到， 并且可以证明s 中所有违反x 的记录经过数据集成流程后必定会违反y ，那么x 就可以用来验证数据源。对于数据集成流程中的每一个操作，如果我们可以实现 根据其输出记录需要满足的质量规则推理其输入记录需要满足的质量规则，我们 就可以在整个流程中的进行迭代的推理，实现将质量规则从目的端推送到数据源 端。但是因为数据操作类型的多样化，实现这样的推理有很大的挑战性。我们的 思路是，将质量规则表示为完整性约束，对于可以用关系代数表示语义的，就采 用一阶逻辑来定义证明相应的推理规则，而对于其他复杂操作，采用规则语言来 定义推理方法。 本文第3 章将对本问题展开研究，主要包括： ( 1 ) 研究数据集成流程异常数据检测问题的定义和范畴。 ( 2 ) 研究给出一个通用的框架，描述必要的组成部分，给出相应的验证算法， 来实现数据集成流程的异常数据检测， ( 3 ) 针对不同的类型的操作组件，研究如何定义从输出端的完整性约束推理 输入端的完整性约束。需要分析研究已有的数据集成流程的建模方法， 分析操作组件的分类，操作组件的语义表示方法。 ( 4 ) 为了表明所提方法的有效性，需要进行具体的案例分析，并对所提方法 应用中的现象进行讨论。 ( 5 ) 设计合理的实验，来表明所提的方法可以提高流程设计的效率和正确 性。 因为缺乏企业级的数据，我们准备采用w e b 数据集成场景来进行方法的验 证，因为w e b 数据集成在数据转换清理上和企业数据集成是类似的，而且w e b 数 据我们都可以通过技术手段获取。 基于n u l l 修复的一致性查询 分析发现，有一类约束是为了对属性的值进行限制的，即当一个元组违反一 个约束时，只是认为相应的属性是不一致，元组并没有问题。而修复方法，可以 采用n u l l 替换这些不一致的属性。这种修复和实际应用中的错误数据更正相对 应，具有实际的语义。但是还存在一些难点，比如研究发现存在多个约束时，不 一致属性是不能通过直接将约束转化为s q l 查询的方法来确定的，对某些不一致 属性替换为n u l l 可能会导致新的不一致属性出现，需要对约束进行扩展，再将 6 第l 章绪论 新的约束转化为s q l 通过一次查询定位所有可能的不一致属性。另外如何基于该 修复语义实现c q a 也是一个挑战。 在第4 章，我们将针对该问题主要研究： ( 1 ) 研究分析属性级完整性约束的特点和应用场景，给出精确的定义，定义 不一致属性，研究给出n u l l 修复的定义。 ( 2 ) 针对不一致属性的定位进行研究，这是一个独立的问题，研究如何通过 约束扩展的方法找到所有修复后可能导致的二次不一致问题。 ( 3 ) 研究针对空值修复语义，一般性查询与聚集查询的s q l 重写算法，使得 重写后的s q l 可以直接一致性的结果。 ( 4 ) 研究设置实验环境，采用t p c h 的数据和不同类型的查询，对本方法进 行性能上的分析，主要分析该c q a 方法与数据库的规模，不一致数据的 比例，查询的类型等直接的关系。 数据清理流程的重构和优化 为了提出针对数据清理流程的通用的逻辑优化框架，首先需要支持可扩展的 操作语义标注和可扩展的转换规则定义，即提供一种流程转换规则表达语言，对 于一种新的数据清理流程工具，支持开发者定义自己的转换规则；为了提高流程 选择的精度，还需要提供有效的流程间代价比较的方法，我们的思路是根据流程 之间相互的转换关系推断出其代价相对关系并构建代价偏序图，因为有的流程变 换规则可以推理出代价的变化方向。为了更好的说明该框架的通用性，我们对 m a s h u p 进行性能优化的有效性验证。 在第5 章，针对本问题主要研究： ( 1 ) 研究定义数据清理流程模型逻辑优化的框架，明确抽象出必要的组成部 分，支持对各种操作标注其操作语义的特征属性，实现转换规则，操作 的可扩展性。 ( 2 )