（计算机软件与理论专业论文）在数据清洗过程中基于mmdb的数据匹配技术研究.pdf

摘要 本论文所讨论的数据清洗是通过对数据库海量数据冗余信息的匹配、探测并 去除错误数据和矛盾数据、提高数据质量的过程。数据质量问题出现在多个数据 集合之间。由于出现数据输入错误、数据源异构、数据表示方法通用性差等情况， 从而导致现有的数据库中存在这样或那样的“脏数据”。这些“脏数据”大大地干 扰了数据处理结果的正确性、有效性和利用率。“数据清洗”利用数理统计、数据 挖掘和预定义行业专家库等技术，将“脏数据”转化为满足数据质量要求的数据。 为此，“数据清洗”过程在银行、电信、移动的海量数据管理和维护中显得越来越 重要。 数据清洗过程可大致分为：数据解析、数据格式规范化、数据匹配、数据修 正、清洗结果检查这5 个比较大的步骤。本文主要讨论的焦点在于海量数据的数 据匹配问题，利用现在发展比较迅速的内存数据库系统( m a i nm e m o r yd a t a b a s e s y s t e m ，m m d b ) 的相关技术，根据数据匹配的一些特殊性，提出了一种m d b 树索 引结构，以及该索引结构下的插入算法和查询算法。数据匹配从一定程度上可以 说是数据库记录的精确匹配查询。传统的数据库查询优化的关注点是减少访问磁 盘数据的i o 次数。面对数据清洗中海量数据匹配查询，以前旧的d r d b ( d i s k - r e s i d e n td a t a b a s e ) 已经不再适用。随着计算机硬件技术的发展，在内存 中存贮整个数据库数据已经成为可能。这使得内存数据库系统( m a i nm e m o r y d a t a b a s es y s t e m ，m m d b ) 近年来发展迅速。它把所有数据都放入内存中，避免了 在查询过程中大量的磁盘i 0 操作，在一定程度上提高了查询的执行时间。 在删【d b 上，由于没有磁盘的i 0 操作，因此提高数据匹配效率的关键变成了 处理器的计算时间和缓存的有效利用率。处理该问题的方法很多，其中一种方法 就是建立合理的数据索引结构，减少查询过程中的匹配失效，从而缩短处理器的 执行时间。本文详细研究了现在数据库的数据索引结构，并根据数据匹配的一些 特殊性，提出了一种m d b - 树( m a i nd e l i c a t eb - t r e e ) 索引结构，以及该索引结 构下的插入算法和查询算法。利用c a c h e 和t l b 失效模型和执行时间模型，对该 索引结构和常见的索引结构进行了性能分析。从分析结果中可以看出，m d b 一树索 引结构克服了原有的索引结构在m m d b 中暴露出输出速率提升水平低、缓存冲突过 多、使用指针过度等缺点，提高了数据匹配效率。 关键词：数据清洗，数据匹配，i v i d b 树 a b s t r a c t a b s t r a c t d a t ec l e a n i n gc o n s i s t so f t h ef i v ec o u r s e sw h i c hi n c l u d i n gi n f o r m a t i o nm a t c h i n g 、 d e t e c t i o n 、c o r r e c t i o no f e r r o ri n f o r m a t i o na n di n c o n s i s t e n ti n f o r m a t i o n t h ep u r p o s eo f d a t ac l e a n i n gi st oi m p r o v et h ed a t aq u a l i t y t h ep r o b l e m so f d a t aq u a l i t yu s u a l l ya p p e a r a m o n g s e v e r a ld a t a - s e t s s o m e d i r t yd a t a m a ye m e r g ea tt h o s ed a t a - s e t s ，b e c a u s eo f d a t am i s i n p u t 、d i v e r s i t yb e t w e e nd a t a b a s e sa n dt h ed i s c r i m i n a t i n gd a t af o r m a t m o r e o v e r , t h o s e d i r t yd a t a b a f f l et h ec o r r e c t n e s s 、v a l i d i t y 、e f f i c i e n c y o f u f i l i z a f i o n w h i l et h ed a t ai sb e i n gp r o c e s s e d d a t ac l e a n i n g t r a n s f o r mt h e d i r t yd a t a i n t o q u a l i f i e d c l e a nd a t a ( t h ec o r r e c td a t e ) b y u s i n g t h em e a i l so f d a t a - s t a t i s t i c s 、 d a t a - m i n i n ga n dp r o - d e f i n i n ge x p e r td a t a b a s e t h u s ，d a t ac l e a n i n gp l a y sag r o w i n g i m p o r t a n t r o l ei nt h em a s sd a t am a n a g e m e n ta n dm a i n t e n a n c ei nt h ef i e l d so f t e l e c o m m u n i c a t i o na n db a n k s d a t ac l e a n i n gp r o c e s sc o n s i s t so f t h ef o l l o w i n gf i v em a i ns t a g e s ：d a t ad e c o m p o s i n g , s t a n d a r d i z a t i o no f d a t af o r m a t , d a t am a t c h i n g , d a t ac o r r e c t i n g , o u t c o m ee v a l u a t i n g t h ep a p e rf o c u s e s0 1 1t h ep r o b l e mo f d a t am a t c h i n ga m o n gm a s sd a t a t oac e r t a i n d e g r e e ，d a t am a t c h i n gm e a n st h ep r e c i s eq u e r y b e t w e e nt h ed a t a b a s er e c o r d s t r a d i t i o n a lo p t i m i z a t i o na b o u td a t a b a s eq u e r yf o c u s e do nh o wt or e d u c et h ei ot i m e s b e t w e e nd i s ka n dm a i nm e m o r y b u tw h e nc o n f r o n t i n gm a s sd a t aq u e r yi nd a t ac l e a n i n g , f o r m e rd r d b ( d i s k - r e s i d e n td a t a b a s e ) i sn ol o n g e rs u i t a b l e t h e d e v e l o p m e n ti nc o m p u t e rh a r d w a r et e c h n o l o g yh a sm a d e i tp o s s i b l et os t o r e t h e w h o l e d a t a o f a d a t a b a s e i n m e m o r y t h i sc a u s e d t h er a p i d d e v e l o p m e n t o f m a i n m e m o r yd a t a b a s es y s t e m ( m m d b ) i nr e c e n ty e a r s i nm m d b t h i st e c h n o l o g ys t o r e s d a t ai nm a i nm e m o r y , t h u sa v o i d sag r e a td e a lo f y oo p e r a t i o n sw h e nt h eq u e r yi s e x e c u t e d i nt h i sw a y , t h eq u e r ye x e c u t i n gt i m em a yb es h o r t e n e d i nm m d b ，t h e r ei sn of o o p e r a t i o n s ot h ek e yo f i m p r o v i n gm a t c h i n ge f f i c i e n c y f o c u s e so nt h ec p ue x e c u t i o nt i m ea n dt h ec a c h ev a l i d i t y t h e r ea r em a n yw a y st o s o l v et h ep r o b l e m o n em e t h o di st ob u i l da na p p r o p r i a t ed a t ai n d e xs t r u c t u r ei no r d e rt o r e d u c et h em a t c hm i s si nq u e r ya n ds h o r t e nt h ec p ue x e c u t i o nt i m e t h i sp a p e rf i r s t h i a b s t r a c t i l l u m i n a t e ss o m ek i n d so f i n d e xs t r u c t u r e si nc o m m o ni l s e t h e ni tp r e s e n t san e wi n d e x s t r u c t u r em d b - t r e ea n dt h ea r i t h m e t i co f e x a c tq u e r ya n di n s e r t i o n , a c c o r d i n gt o p a r t i c u l a r i t yo f d a t am a t c h i n g u s i n gt h ec a c h e a n dt l bm i s s e sm o d e la n dt h e e x e c u t i o nt i m em o d e l ，ac o m p a r i s o nb e t w e e nm d b - t r e ea n dc o m n l o r li n d e xs t r u c t u r e w i l lb ec a r r i e do u t b ya n a l y z i n gt h er e s u l t s ，ac o n c l u s i o nt h a tt h em d b t r e eo v e r c o m e s t h es h o r t a g e so f t r a d i t i o n a lq u e r ys t r u c t u r e - - l o wf a n o u t ，p o o rc a c h eb e h a v i o r , a n d e x c e s s i v eu t i l i z a t i o no f p o i n t e r sc a nb er e a c h e d i te n h a n c 韶t h ee f f i c i e n c yo f d a t a m a t c h i n g k e yw o r d s ：d a t ac l e a n i n g , d a t am a t c h i n g , m d b t r e e 1 v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：塞i l 二 日期：2 一。- 7 年午月z 争日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘厂允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：斐i ! =导师签名： 日期：2 - 一7 年午月2 - 孓日 第一章绪论 1 1 研究背景和意义 第一章绪论 数据清洗，同时也被称为d a t ac l e a n i n g 或者s c r u b b i n g ，数据清洗在不同 的应用领域其要求不完全相同。例如，数据的抽取、转换、清洗和装入 ( e x t r a c t i n g ，t r a n s f o r m a t i o n ，l o a d i n g ，e t l ) 是建立数据仓库系统的重要环节 之一。数据清洗是e t l 过程的一个重要部分，要考虑数据仓库的集成性与面向主 题的需要( 包括数据的清理及结构转换) ；在k d d ( 从数据库中发现知识) 中数据 清洗主要是提高数据的可利用性( 去除噪声、无关数据、空白数据域，考虑时间 顺序和数据的变化等) ，但主要内容还是一样的。数据清洗是一个减少错误和不 一致性、解决对象识别的过程。 本论文所讨论的数据清洗是通过对数据库海量数据冗余信息的匹配、探测并 去除错误数据和矛盾数据、提高数据质量的过程。数据质量问题出现在多个数据 集合之间。由于出现数据输入错误、数据源异构、数据表示方法通用性差等情况， 从而导致现有的数据库中存在这样或那样的“脏数据”。这些“脏数据”大大的干 扰了数据处理结果的正确性、有效性和利用率。“数据清洗”利用数理统计、数据 挖掘和预定义行业专家库等技术，将“脏数据”转化为满足数据质量要求的数据。 为此，“数据清洗”过程在银行、电信、移动的海量数据管理和维护中显得越来越 重要。 数据清洗过程可大致分为：数据解析、数据格式规范化、数据匹配、数据修 正、清洗结果检查这5 个比较大的步骤。数据解析就是把不同数据库的数据文件 解析成为清洗系统能够识别的数据项。数据格式规范化是把解析后的数据根据清 洗需求和清洗规则进行数据项的规范和数据格式的调整。数据匹配的主要工作就 是把来自不同数据库的数据根据匹配规则把来自不同数据库的对应数据关联起 来。数据修正是根据数据清洗需求和清洗规则对关联起来的数据进行扫描检测， 然后根据清洗规则修改“脏数据”。清洗结果检查负责对应用系统的整个或部分数 据质量状况进行评估，验证数据清洗的效果。 电子科技大学硕士学位论文 近年来，基于数据挖掘的技术正在越来越广泛和深入地渗入到社会生活的各 个方面，并且不断扩展。电子政务、电子商务、电子银行、电信、移动等众多领 域和行业的管理及运营都已经或正在从传统方式向电子化、信息化服务方向转变。 电子化、信息化的程度越高，对海量数据质量的要求就越迫切和重要。 同时，中国日益崛起的大众型企业正在实施的e r p 战略中也越来越多地依赖海 量数据库，相信在不远的将来，他们对数据清洗的需求也会越来越大。而数据清 洗平台就是针对国家和重要行业未来电子化、信息化过程中越到的数据冗余、垃 圾数据问题专题研制的。该平台保证了这些海量数据的高效与稳定。 本文主要讨论的焦点在于海量数据的数据匹配问题。据匹配从一定程度上可 以说是数据库记录的精确匹配查询，从而必然涉及到数据库的索引方式。 传统的数据库查询优化的关注点是减少访问磁盘数据的i o 次数，已经不再 符合数据清洗中海量数据匹配的效率要求。在d r d b ( d i s k - r e s i d e n td a t a b a s e ) 系 统上使用的数据匹配相关技术，例如索引等，并不一定能适用在e d d b 系统上。例 如，在传统的d r d b 系统上广泛适用的b + 树等索引，其索引本身也存储部分地被索 引数据，这样在查询索引时可以直接获取被索引数据，而不需再根据索引上的磁 盘地址去读取磁盘上数据。在枷d b 系统中，索引就无需存储被索引数据，只需要 存储指向被索引数据的指针就可以了。b i m d b 系统能够直接根据指针去读取内存中 的数据。原本在d r d b 系统上，还要考虑b + 树的深度等问题，这在m m d b 系统上就 显得并不是那么重要了。比如索引树的深度再深，也只是增加了几次内存访问而 已，开销很小。 在删d b 系统刚刚开始兴起时，也研制出了不少适合于姗d b 系统的索引，例 如t 树，h a s h 索引等。t 树基本上是平衡二叉树，但是它的每个结点上有多个索 引项，并且不包含其他中间结点。t 树具有相当好的空间利用率，每个结点上的 索引项都存储直接指向记录的指针 2 4 。h a s h 索引可以根据不同的策略采取多种 不同的实现方式。h a s h 索引对指针的查询很快，但是对范围查询( r a n g es c a n s ) 就无法快速的完成了，需要多次重复的查询。因为在树上可能相邻的两个元素， 在h a s h 表里很可能被分配到不同的桶( b u c k e t ) 上 2 4 。 但是如今，随着对处理器缓存作用的认识的逐渐加深，m m d b 的数据访问技 术的热点研究方向是在访问的过程中如何利用好处理器缓存，使得性能能得到最 大优化。人们重新研究过在m m d b 系统中曾普遍使用的索引，例如t 树，发现其对 缓存的利用率很差，反而制约了其性能潜力的发掘 2 s 。因此人们相继研制出对 缓存敏感的索引，例如，数组索引、t - 树、c s s 树、c s b + 树、h a s h 索引等。 2 第一章绪论 在数据清洗的匹配过程中，由于面对的是海量的数据匹配，因此提高数据匹 配效率的关键变成了处理器的计算时间和缓存的有效利用率。处理该问题的方法 很多，其中一种方法就是建立合理的数据索引结构，减少查询过程中的匹配失效， 从而缩短处理器的执行时间。本文详细研究了现在数据库的数据索引结构，并根 据数据匹配的一些特殊性，提出了一种帅b _ 树( m a i nd e l i c a t eb t r e e ) 索引结 构，以及该索引结构下的插入算法和查询算法。利用c a c h e 和t l b 失效模型和执 行时间模型，对该索引结构和常见的索引结构进行了性能分析。从分析结果中可 以看出，m d b 一树索引结构克服了原有的索引结构在m m d b 中暴露出输出速率提升水 平低、缓存冲突过多、使用指针过度等缺点，提高了数据匹配效率。 1 2 国内外研究现状和发展趋势 在当今时代，企业信息化的要求越来越迫切，其中一个很重要的方面就是企 业数据的管理。根据“进去的是垃圾，出来的也是垃圾( g a r b a g ei n ，g a r b a g eo u t ) ” 这条原理，为了支持正确决策，就要求所管理的数据可靠，没有错误，准确地反 映企业的实际情况。因此，企业数据质量的管理正在获得越来越多的关注。 最初，研究人员提出用数据质量以方便数据的评估和管理 2 。数据质量的基 本要素：正确性( c o r r e c t n e s s ) 、一致性( c o n s i s t e n c y ) 、完整性( c o m p l e t e n e s s ) 、 可靠性( r e l i a b i l i t y ) 。在进行大量的数据集成的时候，由于录入的数据源的复 杂性，其中包括滥用缩写词、惯用语、数据输入错误、数据中的内嵌控制信息、 重复记录、丢失值、拼写变化、不同的计量单位和过时的编码等，给数据集成和 数据仓库的创建维护带来非常大的困难，往往带来数据仓库创建失败。 在研究数据集成的过程中，很多工作的重点放在如何解决模式冲突上。其实， 在数据实例层次上同样有很多数据质量问题发生。数据清洗过程的目的就是要解 决这些“脏数据( d i r t yd a t a ) ”的问题。数据质量问题的一种情况是一个现实实 体可能由多个不完全相同的记录来表示，这样的记录称为相似重复记录 ( d u p l i c a t er e c o r d ) 。为了检测并合并这些相似重复记录，研究人员提出了很多 记录匹配算法。近年来，研究人员在数据清洗系统的框架、模型和语言以及如何 利用专家知识、如何结合数据清洗过程和数据挖掘方法等方面做了很多工作。 当建立一个信息系统的时候，即使进行了良好的设计和规划，也不能保证在 所有情况下，所存放数据的质量都能满足用户的要求 2 2 。用户录入错误、企业 3 电子科技大学硕士学位论文 合并以及企业环境随着时间的推移而改变，这些都会影响所存放数据的质量。因 此，有必要用元数据来表示数据质量，a e b i ，d 和p e r r o c h o n ，l 在 t o w a r d s i m p r o v i n gd a t aq u a l i t y 中提出了以形式化的方法定义了数据的一致性 ( c o n s i s t e n c y ) 、正确性( c o r r e c t n e s s ) 、完整性( c o m p l e t e n e s s ) 和最小性 ( m i n i m a l i s m ) ，而数据质量被定义为这4 个指标在信息系统中得到满足的程度。 1 9 9 3 年，第9 届国际数据引擎大会上，w a n g ，r yk o n ，h b 和m a d n i c k ，s e 提出了数据工程中数据质量的需求分析和模型，认为存在很多候选的数据质量衡 量指标，用户应根据应用的需求选择其中一部分。指标分为两类：数据质量指示 器和数据质量参数。前者是客观的信息，比如数据的收集时间，来源等，而后者 是主观性的，比如数据来源的可信度( c r e d i b i l i t y ) 、数据的及时性( t i m e l i n e s s ) 等。 在单个数据源中可能存在质量问题。例如，某个字段是一个自由格式的字符 串类型，比如地址信息、参考文献等；错误的字段值，由于录入错误或者其他原 因，数据库中一个人的年龄为4 8 5 等。考虑多个数据源的情形，比如数据仓库系 统、联邦数据库系统，或者是基于w e b 的信息系统，问题更加复杂。来自不同数 据源的数据，对同一个概念有不同的表示方法。在集成多个数据源时，需要消解 模式冲突，主要就是为了解决这个问题。还有相似重复记录的问题，需要检测出 并且合并这些记录。解决这些问题的过程称为数据清洗过程。数据清洗( d a t a c l e a n i n g ，d a t ac l e a n s i n g 或者d a t as c r u b b i n g ) 的目的是检测数据中存在的错 误和不一致，剔除或者改正它们，这样就提高了数据的质量。 针对数据质量的现状，很多学者提出了数据清洗的框架 2 3 。但是数据清洗 是一个领域相关性非常强的工作，而且数据质量问题非常零散，复杂，不一致， 到目前为止没有形成通用的国际标准，只能根据不同的领域制定不同的清洗算法。 目前的清洗算法的优良性衡量标准有以下几个方面：返回率( r e c a l l ) ：重复数 据被正确识别的百分率；f a l s e p o s i t i v ee r r o r ：错误地作为重复数据的记录的 百分比；精确度( p r e c i s i o n ) ：算法识别的重复记录中的正确的重复记录的百分 比；计算公式：p r e c i s i o n = l o o 一f a i s e - p o s i t i v ee r r o r 。 数据清洗过程必须满足如下几个条件：不论是单数据源还是多数据源，都要 检测并且除去数据中所有明显的错误和不一致；尽可能地减小人工干预和用户的 编程工作量，而且要容易扩展到其他数据源；应该和数据转化相结合要有相应的 描述语言来指定数据转化和数据清洗操作，所有这些操作应该在一个统一的框架 下完成。 4 第一章绪论 在模式转化和集成方面，人们已经做了很多的研究工作。而对于数据清洗， 尽管工业界已经开发了很多数据抽取、转化和装载工具( e t lt 0 0 1 ) ，但是它并没 有得到足够多的研究人员的关注。一些研究人员研究相似重复记录的识别和剔除， 还有一些与数据清洗相关的工作。在通过模式转化和集成获得了一致模式以后， 在实例层次上仍然需要消除不一致性。同一个现实实体在两个数据源的记录中可 能用不同的主键来标识，它们的信息可能存在冗余，有些互为补充，甚至有些互 相矛盾。为了识别并且合并这些相似重复记录，研究人员提出了很多算法。这些 算法有两个重要的评价标准：记忆率( r e c a l l ) 和准确率( p r e c i s i o n ) 。记忆率是识 别出的相似重复记录在所有相似重复记录中的百分比；准确率是指在算法识别出 的相似重复记录里，那些真正的相似重复记录所占的百分比。一般来说，在这两 个指标之间需要权衡，在提高记忆率的同时会损害准确率，反之亦然。 市场上的各种数据抽取、转化和装载工具或多或少提供了一些数据清洗功能， 但是都缺乏扩展性。鉴于此，一些研究人员提出了数据清洗系统的框架 1 3 。 g a l h a r d a s ，h 围绕上述框架，提出了数据清洗的模型和语言。该语言在s q l 基 础上扩展了新的数据清洗操作，比如m e r g e ，c l u s t e r 等。g a l h a r d a s ， n 、 f l o r e s c u ，d 和s h a s h a ，d 在数据清洗框架模型上采用了分层抽象的方法，最 上面是逻辑层，可以用来定义数据清洗的流程，不需要关心具体采用的算法：最 下面是物理实现层，这一层根据用户定义的逻辑流程，采用合适的算法和参数， 对算法的优化过程也是在这一层完成的。 绝大多数相关领域的研究人员认为，要很好地完成数据清洗过程，一定要结 合特定应用领域的知识。因此，人们通常将领域知识用规则的形式表示出来，利 用专家系统的外壳，以方便规则的表示和利用。在清洗过程中，需要专家的干预。 当系统碰到不能处理的情况时，报告异常，要求用户辅助做出决定。同时，系统 可以通过机器学习的方法修改知识库，以后碰到类似情况时，它就知道怎样做出 相应的处理了。 随着计算机硬件技术的发展，在内存中存贮整个数据库数据已经成为可能。 越来越多数据清洗平台中采用了近年来发展迅速的内存数据库系统( m a i nm e m o r y d a t a b a s es y s t e m , 姗d b ) 。 d r d b ( d i s k - r e s i d e n td a t a b a s e ) 采用的索引结构主要是b b + 树，其设计目标 是减少访问磁盘数据的i o 次数。而在m m d b 中，采用了一种新的索引结构t 树， 其设计目标是减少内存开销和c p u 指令数。t 树是由a v l 树和b 树发展而来，它 是一种一个节点包含多个元素的二叉树。由于是二叉树，t 树保持了a v l 树二分 5 电子科技大学硕士学位论文 查找的高效率，同时一个t 节点包含多个元素，像b 树一样，每个节点的充满程 度保持在半满和全满之间，这样索引一般不再需要溢出块，由插入和删除所引起 的数据移动通常只需在一个节点内进行，减少了为保持树的平衡所必须进行的旋 转操作，因此t 树又保持了b 树优异的更新和存储特性。由于索引和数据全在内 存中，在一个t 树节点中不需要像b 树那样存放n 个索引键值一指针对，只需存放 指向内存中相应记录对应字段的指针，这样索引中变长字段的存储不再是问题， 另外，由于指针一般比它指向的字段要小，大量的空间也被节省了。在s t a r b u r s t 、 d a t a b l i t z 、t i m e s t e n 中均采用了t 树作为通用索引结构。 在d r d b ( d i s k r e s i d e n td a t a b a s e ) 系统上使用的数据访问技术，例如索引等， 并不一定能适用在m m d b 系统上。例如，在传统的d r d b 系统上广泛适用的b + 树等 索引，其索引本身也存储部分地被索引数据，这样在查询索引时可以直接获取被 索引数据，而不需再根据索引上的磁盘地址去读取磁盘上数据。在m m d b 系统中， 索引就无需存储被索引数据，只需要存储指向被索引数据的指针就可以了。m m d b 系统能够直接根据指针去读取内存中的数据。原本在d r d b 系统上，还要考虑b + 树的深度等问题，这在m m d b 系统上就显得并不是那么重要了。比如索引树的深度 再深，也只是增加了几次内存访问而已，开销很小。 在m m d b 系统刚刚开始兴起时，也研制出了不少适合于m m d b 系统的索引，例 如t 树，h a s h 索引等。t 树基本上是平衡二叉树，但是它的每个结点上有多个索 引项，并且不包含其他中间结点。t 树具有相当好的空间利用率，每个结点上的 索引项都存储直接指向记录的指针 2 4 。h a s h 索引可以根据不同的策略采取多种 不同的实现方式。h a s h 索引对指针的查询很快，但是对范围查询( r a n gs c a n s ) 就 无法快速的完成了，需要多次重复的查询。因为在树上可能相邻的两个元素，在 h a s h 表里很可能被分配到不同的桶( b u c k e t ) 上 2 4 。 但是如今，随着对处理器缓存作用的认识的逐渐加深，姗d b 的数据访问技 术的热点研究方向是在访问的过程中如何利用好处理器缓存，使得性能能得到最 大优化。人们重新研究过在m m d b 系统中曾普遍使用的索引，例如t 树，发现其对 缓存的利用率很差，反而制约了其性能潜力的发掘 2 5 。因此人们相继研制出对 缓存敏感的索引，例如，数组索引、t 一树、c s s 树、c s b + 树、h a s h 索引等。 数组索引：数组索引使用有序数组来为数据提供索引 2 4 。在搜索时，使用二 分查找算法来定位索引项。如果数组索引可以被整个装入缓存中，则使用该索引 是简单高效的，因为索引的所有数据都可以从缓存中读取。但一般情况下，数组 索引大小远大于缓存容量。在此类索引上使用二分查找算法会带来较低的缓存操 6 第一章绪论 作效率。因为二分查找算法会多次读取前后索引项，相当于需要多次读取缓存外 的数据，必然会造成的多次缓存失效。而且数组索引的连续存储方式，也不利于 索引项的动态更新。 t 树：t 树是针对b + 树在内存数据库中的空间浪费问题而提出来的 2 4 。t 树 实质上是一种改进的二义搜索树。t 树所有的结点都直接指引数据项，节省了中 间结点所占空间。但是t 树的提出时间很早，在当时的环境下还没有意识到缓存 对索引性能的影响，设计重点只局限于降低索引的空间占用率上，而没有为缓存 做优化。因此t 树的缓存性能反而还不如b + 树。 c s s 树：缓存敏感搜索树 2 5 是数组索引的一种改进。它通过在数组索引前部 增加一个连续存储的二分搜索树a ，来减小二分查找的范围。同时，a 的设计完全 为缓存做优化，通过连续存储方式，去除了结点和数据项的指针，提高对缓存的 利用率，能提供比b + 树更好的查询性能。但是树的连续存储方式又限制了其动态 更新的能力，因此c s s 树比较适用于数据相对静态的o l a p 领域。 c s b + v ) ：缓存敏感b + 树 6 在b + 树的基础上，对缓存做优化。c s b + 树吸取了c s s 树的设计思想，在树的结点中不再保存子结点的指针，而只在结点头部保存一个 指向下一层子结点的指针。同时兄弟结点之间建立组的概念并连续存储，通过指 针和偏移量定位子结点。这样的设计，节省了结点内指针所占用的空间，可以将 更多的索引项放入结点并装入缓存，提高了对一缓存的利用率，减少了查询过程 中的缓存失效次数。同时，c s b + 树对索引动态更新的代价也要小于c s s 树。但是 c s b + 树也有缺陷。为了使查询过程中可以有多个结点被装入缓存中并减少结点操 作时的缓存失效次数，c s b + 树的结点大小都控制在一个缓存块左右，一般在6 4 字 节到1 2 8 字节。因此，当索引项数很大时，c s b + 树的深度将会很深，在查询路径 上会需要访问更多的结点，反而增大了缓存失效的次数，以及会带来更多的t l b 失效问题。 p b 树和f p b + 树：这种树基于b + 树基本结构，结点大小为缓存块大小的数倍， 但是小于缓存的容量。在查询过程中，利用硬件预取指令将要访问结点一次装入 缓存中，可以将原本访问结点时会产生的多次缓存失效减小到只有一次。但这种 方法也有局限性。首先，将整个结点装入缓存中，会占用多个缓存块的空间，但 并不是结点中的所有数据都会被使用到，反而降低了缓存的利用率。其次，缓存 的容量有限，将一个接近于缓存大小的结点装入缓存中，需要替换缓存中的大多 数数据，很容易引起缓存震荡问题。再次，由于使用到了特殊的硬件指令，会给 系统的移植带来麻烦。 7 电子科技大学硕士学位论文 带缓冲区索引树：通过在索引结点上附加缓冲结构，将对结点的访问指令先在 缓冲结构中保存。当缓冲结构满时，再逐条从缓冲结构中取出访问指令，送入不 同子结点的缓冲结构中。当叶子结点的缓冲结构满时，则从缓冲结构中取出访问 指令井执行。该技术通过利用时间和空间局部性原理，将原木处于离散时间点上 的多个访问指令重新组合，在特定时间点上将这些指令顺序执行，并且这些指令 所访问的数据处在同一个结点内。因此，在这些指令被执行完成前，所需要的数 据可以一直保存在缓存中，大大减少缓存失效的次数。但是每个结点上附加缓冲 结构不仅会占用不少的内存空间，而且由于访问指令会需要先被缓冲后再被批量 执行，因此该索引的响应速度会有较大波动。 但是如今，随着对处理器缓存作用的认识的逐渐加深，m m d b 的数据访问技术 的热点研究方向是在访问的过程中如何利用好处理器缓存，使得性能得到最大优 化。人们重新研究过在m m d b 系统中普遍使用的索引，例如t 树基本上是平衡二叉 树，但是它的每个结点上有多个索引项，并且不包含其他中间结点。t 树具有相 当好的空间利用率，每个结点上的索引项都存储直接指向记录的指针 4 。h a s h 索引可以根据不同的策略采取多种不同的实现方式。h a s h 索引对指针的查询很 快，但是对区域查询( r a n g es c a n s ) 就无法快速的完成了，需要多次重复的查询。 因为在树上可能相邻的两个元素，在h a s h 表里很可能被分配到不同的桶b u c k e t 上 4 。因此人们相继研制出对缓存敏感的索引，例如c s s 树 5 、c s b + 树 6 等。 同时多种针对缓存效率的索引优化方法也被使用 7 8 9 。 ， 从上面的材料可以看出，在数据清洗领域，大部分的研究工作都聚集在如何 查找“脏数据”，以及如何处理“脏数据”方面，而对于前期工作数据匹配 的研究相对较少。 1 3 本文主要工作及章节安排 本文主要讨论的焦点在于海量数据的数据匹配问题。数据匹配从一定程度上 可以说是数据库记录的精确匹配查询。传统的数据库查询优化的关注点是减少访 问磁盘数据的i o 次数。面对数据清洗中海量数据匹配查询，以前旧的d r d b ( d i s k r e s i d e n td a t a b a s e ) 已经不再适用。 随着计算机硬件技术的发展，在内存中存贮整个数据库数据已经成为可能。 这使得内存数据库系统( m a i nm e m o r yd a t a b a s es y s t e m ，m m d b ) 近年来发展迅速。 8 第一章绪论 它把所有数据都放入内存中，避免了在查询过程中大量的磁盘i o 操作，在一定 程度上提高了查询的执行时间。 在m m d b 上，由于没有磁盘的i o 操作，因此提高数据匹配效率的关键变成了 处理器的计算时间和缓存的有效利用率。处理该问题的方法很多，其中一种方法 就是建立合理的数据索引结构，减少查询过程中的匹配失效，从而缩短处理器的 执行时间。本文详细研究了现在数据库的数据索引结构，并根据数据匹配的一些 特殊性，提出了一种m d b 一树索引结构，以及该索引结构下的插入算法和查询算法。 利用c a c h e 和t l b 失效模型和执行时间模型，对该索引结构和常见的索引结构进 行了性能分析。从分析结果中可以看出，m d b 一树索引结构克服了原有的索引结构 在m m d b 中暴露出输出速率提升水平低、缓存冲突过多、使用指针过度等缺点，提 高了数据匹配效率。 本文的内容安排如下： 第一章讲述了数据清洗以及数据匹配的研究背景和意义，指出了数据清洗的 发展趋势，并且概述了本文的主要工作和章节安排。 第二章主要阐述了数据清洗和内存数据库的实现原理，介绍了利用以上两项 关键技术实现的数据清洗平台。 第三章首先介绍了数据清洗过程中数据匹配、数据比对技术的背景、发展以 及相关的关键技术的研究状况，然后从理论基础、处理模型和具体实现三个方面， 重点阐明本文提出的基于m m d b 的数据匹配技术在数据清洗过程中的应用。 第四章列出了该数据清洗平台实现后的相关测试结果以及结果分析。 第五章对项目作了总结，并对将来的工作做了展望。 9 电子科技大学硕士学位论文 第二章数据清洗平台技术分析 本章主要阐述了数据清洗和内存数据库的实现原理，并介绍一下利用以上两 项关键技术实现的数据清洗平台。 2 - 1 数据清洗原理 2 1 1 数据清洗技术的研究背景 数据质量问题，是创建数据仓库以及进行数据集成工作中的致命性问题。如 果没有很深刻地分析数据中存在的问题，就盲目进行开发和集成，不仅造成数据 仓库创建失败带来经济损失的后果，更有可能造成严重的决策失误。数据质量的 基本要素：正确性( c o r r e c t n e s s ) 、一致性( c o n s i s t e n c y ) 、完整性( c o m p l e t e n e s s ) 、 可靠性( r e l i a b i l i t y ) 。在进行大量的数据集成的时候，由于录入的数据源的复 杂性，其中包括滥用缩写词、惯用语、数据输入错误、数据中的内嵌控制信息、 重复记录、丢失值、拼写变化、不同的计量单位和过时的编码等，给数据集成和 数据仓库的创建维护带来非常大的困难，往往带来数据仓库创建失败。 针对数据质量的现状，很多学者提出了数据清洗的框架。但是数据清洗是一 个领域相关性非常强的工作，而且数据质量问题非常零散，复杂，不一致，到目 前为止没有形成通用的国际标准，只能根据不同的领域制定不同的清洗算法。目 前的清洗算法的优良性衡量标准有以下几个方面：返回率( r e c a l l ) ：重复数据 被正确识别的百分率；f a l s e p o s i t i v ee r r o r ：错误地作为重复数据的记录的百 分比；精确度( p r e c i s i o n ) ：算法识别的重复记录中的正确的重复记录的百分比； 计算公式：p r e c i s i o n = 1 0 0 一f a l s e p o s i t i v ee r r o r 。 数据清洗就是发现数据中的错误和不一致并加以消除，以提高数据的质量。 它直接对数据进行处理( 扫描数据、去除不必要的列、清理冲突数据) 为建立数 据挖掘模型做准备。因此数据清洗是建立数据挖掘模型中较为重要的步骤。数据 清洗的对象包括那些输入计算机中的数据。由于数据录入时的错误检测过程以及 人为因素，操作人员不可避免会犯某些错误( 输入错误的日期、输入错误的工资、 输入错误的地址、等等) 从而造成数据错误或数据冲突。如果建模者不是很仔细 1 0 第二章数据清洗平台技术分析 的话，这些数据冲突将会潜在的降低数据挖掘模型的性能。因此，在有限的时间 里尽量多地找出并改正那些错误和冲突是非常重要的。 2 1 2 数据清洗定义 数据清洗原理：利用有关技术如数理统计、数据挖掘或预定义的清理规则将脏 数据转化为满足数据质量要求的数据，如图所示。 图2 一l 数据清洗原理图 按数据清洗的实现方式与范围，可分为4 种： 手工实现。通过人工检查，只要投入足够的人力物力财力，也能发现所有错 误，但效率低下。在大数据量的情况下，几乎是不可能的。 通过专门编写的应用程序。这种方法能解决某个特定的问题，但不够灵活， 特别是在清理过程需要反复进行( 一般来说，数据清洗一遍就达到要求的很少) 时， 导致程序复杂。当清理过程变化时，工作量增大。而且这种方法也没有充分利用