数据集成、清理以及转换的研究概况

1.2 国内外概况数据集成是数据仓库建立的基础，数据集成时往往还需要对数据进行清理和转换[4-36,44-100]。如图1.1，在所谓ETL（extraction, transformation, loading）过程中，数据集成工具从各个异构的数据源中抽取数据并进行清理和转换，然后装载到数据仓库中。如图1.1所示的，所有的数据清理和转换工作都在那些已被转换的数据装载到数据仓库之前完成，且处于一个独立的阶段，现在已有许多工具可用来支持ETL任务，但是一个重要部分——数据的清理和转换不得不用人工或者低级程序来处理，难以维护和书写。这使得数据集成成为创建数据仓库中最为费时费力的操作，可能占到2/3的工作时间[96]。数据清理、转换和集成在近年来常常被混用。目前这个领域的研究员都倾向于将这三者统一到数据集成上来，或者数据转换、数据集成并举，这是因为在以前的研究中，这三者的任务覆盖了许多共同任务。此外，数据集成系统上的操作[64,73,85-87,94]得到了不少团体的关注和研究，它们从另一角度阐述和充实了数据集成。作者认为还应当从狭义上重新定义数据转换、清理与集成，以便确认数据清理与数据转换各自的任务，同时有利于更深入地了解数据集成。因此，本文中定义数据集成为数据转换、数据清理及其上的操作的集合，数据转换为数据格式和数据类型的映射，数据清理为源数据质量检测及问题清除。根据这个定义，作者将分别介绍有关数据转换、数据清理和数据集成上的操作的研究情况。 1.2.1数据质量问题首先应当知晓数据的质量问题所在，对症下药，才能解决数据质量问题。数据质量很大程度上依赖于模式和完整性约束控制许可的数据值。对于那些没有模式的数据源，如文件系统缺少限制以致任何数据可以数据和存储，发生错误和不一致的概率较高。数据库系统则增强了数据类型、数据值、完整性约束等限制，但是也有可能因为模式设计不好，输入错误等出现数据质量问题，使得它也需要清理。文献[32]对此作了较为系统的论述，将数据质量问题分为单数据源问题和多数据源问题以及模式和实例等四种形式。显然模式问题反映到实例级。模式级问题可通过模式设计、模式转换、模式集成解决；另一方面，如数据错误或不一致等实例级问题并不反映到模式级，它们目前主要通过数据清理来解决。数据质量问题如图1.2所示。 1．单数据源问题表1.1显示了单数据源的模式级的主要质量问题[32]。经分析，可以发现，这些问题产生的主要原因是缺乏足够的约束。表1.1 单数据源模式级问题示例范围/问题 脏数据（DIRTY DATA） 注释属性（Attribute） 值不合法 bDate=30.13.70 超出范围（月份：13）记录（Record） 属性依赖冲突 Age=22, bDate=30.02.70 年龄可计算出来记录类型（Record Type） 唯一性冲突 Emp1=(name=”john Smith”, ssn=’123456’) emp2=(name=”Peter Miller”, ssn=’123456’) 这里ssn应该唯一数据源（Source） 引用完整性冲突 emp=(name=”John Smith”, deptno=127) 部门号127不存在 在关系模式的实例级，除了因缺少足够的模式约束而出现的数据质量问题外，还有拼写错误、信息来源本身问题等导致的质量问题。具体来说主要有如下几种情况，如表1.2所示[32]。表1.2 单数据源实例级数据质量问题示例范围/问题 脏数据（DIRTY DATA） 注释属性 值缺乏 Phone=9999~999999 拼写错误 City=”Beigin“ 打印、语音导致错误 含糊不清、简写 Experience=”B” Occupation=”DB Prog” 包含过多 Name=”J. Smith 12.02.70 New York” 包含太多的内容 不正确的字段值 City=”German” 记录 属性依赖冲突 City=”wuhan” zip=”440000” 城市和邮编不对应记录类型 单词换位 Name1=”J. smith” Name2=”Petter M.” 自由格式的文本 重复记录 Emp1=(”John smith”, ….) Emp2=(”J. smith:”, ….) 输入错误导致 矛盾的记录 book1=(“商务入门”,1995) book2=(“商务入门”,1996) 同一实体被描述成不同的值源数据 错误的引用 Emp=(name=”J. smith”, deptno=127) Deptno=127不存在 2．多数据源问题多数据源的数据质量问题比单数据源复杂。首先，所有单数据源存在的问题在多数据源都存在。其次，除了这些，多数据源还存在许多问题：（1）在模式级，主要问题在于命名冲突和结构冲突。命名冲突是因为常常用相同的名字表示不同的对象或者用不同的名字表示相同的对象；结构冲突发生在同一个对象在不同的数据源中表现形式不同，如性别，有的数据源用0、1表示，有的用“男”、“女”表示等。（2）在实例级，还有可能出现相同的属性名和相同的数据类型但是表现形式不同或者解释不同，比如属性销售额的单位是美元还是人民币的问题。可见，在具有较好的集成模式前提下，数据质量问题可分为两种：一是数据格式问题，二是数据重复、错误等问题。格式问题可用数据转换解决，而数据重复错误问题则需进行数据清理。 1.2.2 数据转换数据转换的目的是将遗留系统迁移到一个更现代的应用、查询优化、从一个数据模式到另外的一个数据模式、集成异构系统到联邦数据库或数据仓库、实施数据净化或清理，实现企业范围的集成。因此，数据转换在信息管理系统中是一个支柱（bread and butter）技术，涉及系统的多个方面。数据转换的研究起步较早，在五六十年代文件系统时期就存在数据转换的需求。现在数据仓库的兴起等引起了更大的数据转换需求，多种多样的集成以及新的数据格式的不断产生，使得数据转换的任务也越来越复杂。目前要转换的数据模型有网络模型、关系模型、面向对象模型，现在又增加了XML web模型。由于数据集成中数据转换的重要性，一些大的数据库商家都研制并推出了一些数据转换工具，如微软的DTS、IBM的Warehouse Manager、Oracle的Warehouse Builder、SAS公司等，研究团体也给予了足够的关注。象Abiteboul 等提出了异构数据源的数据转换[16]，他们的解决方案是采用中间件数据模型和一脚本语言来映射数据源，并做了一些任务的自动化研究；Bernstein和Bergstracesser报告了基于Microsoft SQL Server 7.0的数据集成工具[17]，包括数据和元数据的转换，他们描述了称之为Microsoft Repository的仓库函数，如数据转换服务，以帮助用户开发程序；Carrer, Joshi, et al.描述了一个称为Oracle MediaAnnotator的基于Oracle8i的元数据转换和管理工具[17]，Oracle MediaAnnotator能够自动从多媒体数据源中抽取和转换元数据到一个逻辑标注，这样就简化了多媒体对象的索引和检索；Davidson and Kosky开发了一个描述性语言（Horn－Clause）：WOL[20]，可以用来说明复杂的数据类型和递归结构的数据转换，WOL能够很容易地根据源数据的模式作相应的改变，WOL映射可以解决源数据和目的数据之间的不相容；Michael[52]则详细地介绍了集成工具Infomaster的转换功能。随着XML作为信息交换的主要标准出现，XML与关系、对象数据库系统的集成已成为一个极其活跃的领域。映射XML或半结构化数据到关系/对象数据库模型或把关系/对象数据输出为XML文档提供关系数据的XML视图或扩展关系查询引擎以处理XML数据的查询等技术目前得到了大量研究团体的关注。在商业领域许多主要的关系数据库商已经提供XML数据的本地存储和XML文档管理和一些用于简易的API用于关系数据导入/导出XML文档。在关系模式到XML模型的转换中存在许多不同的方法，主要有两种方式：1.使用用户定义映射规则的方法。如，IBM的XML Extender[108]、SilkRoute[89]、XPERANTO[29]等算法都要求用户指定从给定关系到XML模型的映射；2.利用算法自动实现从关系模式到XML的转换。如，DB2XML、FT、NeT、CoT等算法[57]。 XML Extender使用一个称为DAD或XML Extender的转换语言定义映射[108]；SilkRoute则提供了一个描述性查询语言RXL浏览XML中的关系数据[89]。XPERANTO[29]使用XML查询语言XQL浏览XML中的关系数据。在SilkRoute和XPERANTO中，用户不得不用合适的查询语言定义查询。FT的算法按照关系的平面结构直接将关系模型转换为与之对应的XML模型，因此不能利用XML提供的正则表达式如（*，+）等，缺乏层次，也不够直观。NeT不要求用户输入关系模型到XML模型的映射规则，能自动推导出具有层次的、较为直观的XML模型，然而它只能处理单一的关系模式。CoT在此基础上作了进一步的工作，能建立满足一定完整性约束（外键约束）的、更为直观的XML模式。CoT首先对外键约束进行处理，将多关系转换为适合NeT处理的单一关系模式，然后利用NeT算法建立完整的XML模式。而NeT算法需要多次nest操作才能得到较直观的具有层次特点的XML模式，十分费时。从XML到关系也有两种不同的方式。一是使用映射规则的方法。通过执行引擎将数据从XML模型转换到关系模型；另一个方式是利用算法自动实现从XML到关系的转换[55,56]。文献[55,56]研究了从XML到关系模式的自动推导算法，这个算法具有较强的理论依据，但存在关系过多的缺点。因此，尽管已有大量学者在此课题上做了大量的工作，但是人们依旧对这个技术有兴趣。虽然市场上有一些可以达到一定功能的转换工具/产品，但它们都局限于一个特定的问题或一个特定的数据模型。如何提供通用的方法解决所有的或者至少上述的大部分问题依旧有待研究。 1.2.3 数据清理数据清理主要用来检测、清除数据的错误及不一致以改善数据的质量。由于输入时误拼、信息缺失或其它的无效数据，数据质量问题可出现在单一的数据容器中，如文件或数据库等。当多个数据源需要集成的时候，数据质量问题尤其突出，除了单数据源存在的问题外，还存在语法语义的不同，数据源之间经常包含有大量表现形式各异的冗余数据。如数据仓库的建立和维护过程中，常常需要从不同的数据源装载以及连续地刷新数量巨大的数据，而其中一些数据源包含有脏数据可能性很高。更重要的是数据仓库常用于决策制定，为了避免错误的决策，数据的正确性极其重要。如果数据重复或者缺失往往会导致统计错误乃至决策错误。联帮数据库和web信息系统面临同样的问题。所以，为了保证提供正确且具有一致性的数据，清理重复的信息成为一项必须的工作。多数据源的清理的一个主要问题就是识别重复的数据，即识别数据源中对世界同一实体的不同的映射。这个问题也称为对象身份识别问题、重复记录清除或合并/清除问题。如何识别给定的记录是否重复存在两个问题：一是等值理论问题，即重复记录的判定依据；二是重复记录识别算法。等值理论问题是数据清理的核心问题之一，也是数据清理的基础。由于涉及到语法、语义以及人工智能等固有问题，所以没有得到研究人员应有的重视，仅见于文献[31]。文献[31]首次提到了等值理论问题，并指出，等值理论问题是个非常复杂的课题。但是无论如何，等值理论是一个值得研究的重要领域。重复记录识别算法主要用于识别给定的两个数据是否重复。根据关注点不同，作者将识别算法分为记录间算法和记录内算法。记录间算法主要通过减少记录间的比较次数提高清理的速度。由于数据集的数据量庞大，如何在保证一定的重复记录识别精度的同时，减少重复记录的识别时间是重复记录识别算法的重点；而记录内算法则主要解决给定的两个数据是否近似重复。目前，重复记录识别的记录间算法研究成果较多。具体地说，有基于滑动窗口算法如滑动窗口算法[31,98]（也称作排序邻近算法）及多路排序邻近算法等、距离过滤算法、优先队列[33]等算法，具体如下所述。 1.滑动窗口类算法利用排序的方法将重复记录调整到邻近的位置，使得重复记录可在一个窗口内比较完毕，从而避免了大量不必要的比较。同滑动窗口算法比较，多路排序邻近算法[31]通过Partition数据的方法在进一步提高执行速度的同时，还提高了重复记录的识别精度。滑动窗口算法的不足主要在于排序关键字以及Partition算法的选择对重复记录的识别精度和执行效率有较大的影响，是一个经验工作；此外窗口的大小也对识别的精度也有较大的影响。 2.距离过滤算法则通过增加查询条件限制的方法减少待比较的记录数，从而提高了重复记录识别的速度，特别适用于重复记录具有聚族特征的情形。然而，距离过滤算法的查询条件的选择是件较为困难的事，可能需要经过多次查询，效率很低；另一方面，距离过滤算法的识别精度一般不高。 3.优先队列算法[33]利用队列存储具有同一聚类特征的数据，然后在队列内进行数据的比较过程。在窗口类算法中，一个窗口内的数据可能只有极少甚至没有重复记录，此时进行的重复记录比较都是没有必要的，另外当数据集过大时又可能由于重复记录的位置偏差超过了窗口的容纳范围而引起重复记录的识别精度下降。优先队列算法避免了这两个问题，因此优先队列算法在重复记录识别精度和速度上比排序邻近算法有所提高，但是优先队列算法可能存在队列过大问题以致影响算法的执行速度。相对记录间算法而言，用于识别记录是否近似的记录内算法却极少被相关文献提及，尽管有些研究文献提到了使用编辑距离作为数据近似识别的算法，但没有具体算法介绍。字符串模式匹配算法可以引入到重复记录识别的记录内算法中。字符串模式匹配算法不仅种类多，而且功能也在逐步多样化，如支持正则匹配、近似匹配、缩写匹配、允许误差的字符串近似匹配算法等。字符串近似匹配算法主要有两大类：1.基于动态规划；2.过滤等算法。具体来说，主要有经典动态规划算法、基于比特的快速算法、启发式剪枝算法、快速过滤算法等。然而这些算法需要进一步研究，因为首先这些算法的主要目的是模式匹配，和重复记录识别的目的不同；其次，这些基于编辑距离的算法是机械的、功能有限的，不能满足语义清理的需要。综上所述，目前关于数据清理的研究取得了一定的成果。这些成果或多或少都存在缺憾，甚至是是远远不够的。无论是作为数据清理核心和基础的等值理论，还是重复记录识别算法，都还需要进行大量的研究。 1.2.4 数据集成模型及其上的操作数据集成是数据转换、清理以及集成系统上的操作的集合。数据集成同数据转换密不可分，数据集成时必然需要数据转换，有时还需要进行数据清理。但是，数据集成并不等同于数据转换和数据清理，因为数据集成应当除数据转换和数据清理外还同应用到数据集成上的操作有关。数据集成的框架及其上的操作如查询和管理、维护等都存在实际的应用意义。研究人员从多个方面对数据集成进行了研究，包括集成的模型以及操作等。如，Renee Miller[60]开发了一个异构数据源的集成工具Clio。Clio侧重于集成时的信息管理，提出三个子管理系统模型，应用三个子管理系统存储管理集成的信息。第一个子管理系统为模式和数据管理，由于集成中的核心任务就是数据和模式的再现，而集成结果很大程度依赖于数据和模式的信息的正确性和完整性，因此保存数据和模式、约束、关系等信息就十分必要。第二个子系统为相关性管理，它主要用于了解模式之间和数据之间倒底有什么不同及相关性。第三个则是映射管理，这里映射指用于不同模式之间数据转换的一段程序或者查询。 Ariel等[64,87,94]研究了集成系统的不一致管理课题。他们认为在任何集成系统中，不一致管理都是一个基本的工作。因为模式集成过程并不总能反映用户脑海里的全局模式语义，在很多例子中甚至可能没有符合用户要求的一致性模式。在此情形下，文献[64]探讨了一个查询结果一致的方法。文献[54]则认为，集成系统并不象一些研究人员所认为的那样数据完整，可能存在噪声。在虚拟数据仓库情况下，如何根据完整性约束条件给用户提供一个准确的一致的答案？文献[54]对此作了深入的研究。实数据仓库模型中存在查询优化以及更新的问题。高效及时地响应用户提交的查询是集成系统任务之一，另外由于外部数据不断更新，保证集成系统中数据的有效性和及时性成为集成系统的另一重要任务。虚拟数据仓库模型中不仅存在一个查询的重写问题，查询优化变得更加重要。当用户提交一个查询给全局模式时，如何实现查询重写以实现全局查询到各数据源中的查询以及查询的高效响应也是一个值得研究的课题。文献[71]探讨了虚拟数据仓库模型下的自适应查询优化技术。一般地，集成系统不同，其上操作的优化技术也大不相同。数据立方作为一个的集成系统[104-107]，能有效地进行数据分析，因此数据立方得到了较为广泛的应用。然而数据立方十分庞大，它的查询与更新非常费时，文献[107]提出了前缀和算法，通过预先计算方法将查询的效率提高到O(1)，而更新效率则从O(1)上升到O( )，仅适合于查询较多更新极少的数据立方；文献[104]提出了相关前缀和算法，查询和更新的时间复杂度为O( )；文献[105]在此基础上提出了双相关前缀和算法，更新和查询的时间复杂度都为 ，比较适合查询和更新比较均衡的情形。相关前缀和算法以及双相关前缀和算法的不足是它们都是基于平均分块的方法，不具备结构独立性，结构的变化将引起数据立方的重构；另一方面，数据立方上的查询基本都是在较粗的粒度上进行的，很少涉及到细节型数据，此外这些算法空间浪费较大

TAG: 清洗 数据集成 转换
10秒注册会员 结交数据仓库朋友 分享你的精彩