（管理科学与工程专业论文）数据仓库的数据获取关键技术研究.pdf

国 防 科 学技 术 大 学 研 究 生 院 学位 论 文 摘要 数据获取过程是构建数据仓库的核心和灵魂， 是负责完成数据从数据源向目标数据仓 库转化的过程， 是实施数据仓库的重要步骤。 本文设计并实现了 数据获取系统， 主要研究 数据获取中的两个关键技术:数据源增量数据获取技术和相似重复一记 录检测技术。 在数据源增量数据获取技术研究中， 通过对几种快照差分算法进行理论研究及实验分 析，了 解掌握了它们的适用范围、 处理速度及精度; 对于有日 志系统支持的数据源， 分析 了o r a c i e , s q l s e r v e r 数据库的日 志记 录内容， 分析了获取增量数据的流程。 考虑到w h i p s 项目的一些缺陷， 做出一些改进: 调整了监视对象粒度， 支持对某个源表字段的监视， 过 滤掉那些无关的数据变化， 可以提高监视的效率: 提供可定义的监视规则， 其中包括了 检 测分析周期等， 监视器就按照这些规则检测分析和报送数据源的变化， 使得数据仓库更新 策略更加符合数据仓库应有的特性。 在重复记录检测方法的研究中， 提出一种高效的基于条件概率分布的相似重复记录检 测方法， 采用二次聚类方法， 即首先选用一种低价的距离度量方法将整个数据集划分为几 个大类， 然后使用更严格的距离度量方法和聚类算法进行分类。 使用该方法， 对仿真数据 进行了实验，获得了比较好的聚类结果。 关键字;数据获取 快照差分 相似重复记录检测 字符串距离度量 动态聚类 概率后缀树 第 1页 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 a b s t r a c t t h e c o r e o f b u i l d i n g d a t a w a r e h o u s e , d a t a e x t r a c t i n g p r o c e s s , i n t e g r a t e d i n a c c o r d a n c e w i t h u n i f o r m r u l e s a n d e n h a n c i n g t h e v a l u e o f d a t a i s r e s p o n s i b l e f o r t h e c o n v e r s i o n o f d a t a f r o m d a t a s o u r c e t o t a r g e t d a t a w a r e h o u s e , a n d a c t s a s a n i m p o r t a n t m e a n s 她i m p l e m e n t d a t a w a r e h o u s e . t h i s p a p e r i n t e n d s t o i l l u s t r a t e t h e d a t a e x t r a c t in g s y s t e m d e s i g n , w i t h f o c u s o n t w o k e y t e c h n o l o g i e s i n d a t a e x t r a c t i n g , n a m e l y , i n c r e m e n t a l d a t a e x t r a c t i n g a n d d u p l i c a t e r e c o r d d e t e c t i n g . i n d a ta s o u r c e i n c r e m e n t a l d a t a e x t r a c t i n g p r o c e s s , t h e s y s t e m d e s i g n w a s f o r m u la t e d w i t h r e f e r e n c e t o wh i p s p r o j e c t b y s t a n f o r d u n i v e r s i t y d a t a b a s e g r o u p . s e v e r a l s n a p s h o t d i f f e r e n c e a lg o r i t h m s w e r e e m p l o y e d to c o m p r e h e n d a n d m a s t e r t h e i r a p p l i c a t i o n s c o p e , p r o c e s s i n g s p e e d a n d a c c u r a c y . a s f a r a s t h e d a t a s o u r c e w i t h l o g s y s t e m s u p p o r t , t h e c o n t e n t o f th e l o g r e c o r d s i n o r a c le , s q l s e r v e r w a s a n a l y z e d a n d t h e p r o c e d u r e t o e x t r a c t i n c r e m e n t a l d a t a w a s p r o p o s e d . we m e l i o r a t e t h e i m p l e m e n t o f d a t a s o u r c e m o n i t o r a s f o l l o w i n g : 1 . t h e m o n i t o r e d o b j e c t s a r e c h a n g e d f r o m b a s e t a b l e s t o s o u r c e v i e w s a s t o a v o i d p r o p a g a t i n g t h e u n n e c e s s a r y s o u r c e d a t a c h a n g e ; 2 . we p r o v i d e t h e m o n i t o r r u l e s a c c o r d i n g t o w h i c h m o n i t o r d e t e c t s , a n a l y z e s a n d p r o p a g a t e s t h e c h a n g e i n s o u r c e d a t a , a n d t h e s e r u l e s c a n b e p r e d e f i n e d t o m e e t t h e c o m p l i c a t e d d e m a n d s o f i n t e g r a t i o n - e n d s u c h a s th e m o n i t o r i n g p e r i o d . d e t e c t i n g d a t a b a s e r e c o r d s t h a t a r e a p p r o x i m a t e d u p l i c a t e s , b u t n o t e x a c t d u p l i c a t e s , i s a n i m p o r t a n t t a s k . i n t h i s p a p e r , w e i n v e s t i g a te t h e p r o b 、 二 o f d e t e c t i n g d u 抖 i c a f i o n s b a s e d o n t h e i r s tr u c t u r a l f e a t u r e s , a n d th e n w e p r e s e n t a n e f f i c i e n t a n d e f f e c t i v e a l g o r i t h m f o r r e c o g n i z i n g c l u s t e r s o f a p p r o x i m a t e l y d u p l i c a t e r e c o r d s . t h e c o n d i t i o n a l p r o b a b i l i t y d i s t r i b u t i o n ( c p d ) o f th e n e x t s y m b o l g i v e n a p r e c e d i n g s e g m e n t i s d e r i v e d a n d u s e d t o c h a r a c t e r i z e s e q u e n c e r e c o r d a n d t o s u p p o r t t h e d i s t a n c e m e a s u r e . a v a r i a t i o n o f t h e s u f f i x t r e e , n a m e l y p r n h a b i l i s t ic s u f f ix t r e e , i s e m p l o y e d t o o r g a n iz e t h e c p d i n a c o n c i s e w a y . a n d b a s e d o n t h e n e a r n e i g h b o r s r u l e s w e s e l e c t a r u l e f u n c t i o n t o c o m m e n t t h e c l u s t e r in g r e s u l t s . f i n a l l y , d y n a m ic c l u s t e r i n g a l g o r i t h m i s e m p l o y e d t o c l u s t e r t h e d a t a s e t . c o m p r e h e n s i v e e x p e r i m e n t s o n s y n t h e t i c d a t a b a s e r e c o r d s c o n f i r m t h e e f f e c t i v e n e s s o f t h e n e w a l g o r i t h m k e y w o r d s : d a t a e x t r a c t i n g , s n a p s h o t d i f f e r e n c e , d i s t a n c e b e t w e e n t w o s t r i n g s , a p p r o x i m a t e l y d u p l i c a t e d r e c o r d s , d y n a m i c c l u s t e r i n g , p r o b a b i l i s t i c s u f fi x t r e e 第 1 1页 独 创性声明 本人声明 所呈交的学位论文是我本人在导师指导下进行的 研究工作及取得 的 研究成果。 尽我 所知， 除了 文中 特别加以 标注和致谢的 地方外， 论文中 不包含 其 他人已 经发表和 撰写过的 研究 成 果， 也 不 包含为 获得国防 科学技术大学 或其它 教育机构的学 位或证书而 使用过的 材料。 与我 一同 工作的同 志对 本 研究 所 做的 任 何贡献均已 在论文中 作了明 确的 说明 并 表示谢意。 学 位 论文 题目 :数 据 仓 库 的 数 据 获 取 关 键 技 术 研究_ 学位论文作者签名:啦 乳 日 期: /p 咤年 ( r月滓 日 学位论文版权使用授权书 本人完 全了 解国防 科学技 术大学 有关 保留 、 使用学 位论文的规定。 本人 授权 国防 科学技术大学可以 保留 并向国 家有关部门 或机构送交论文的复印 件和电 子 文 档， 允许论文 被查阅和 借阅 ; 可以 将学 位论文的 全部 或部分内 容编入有关数据 库进行检索，可以 采用影印、 缩印 或扫描等复制手段保存、汇 编学 位论文。 ( 保密学位论文在解密 后适用本授权书 。 ) 学 位论文题目 : 数 据仓 库的 数 据 获 取关 键技 术 研究 学位论文作者签 名 作者指导教师签名 : 根 i .日 期:纳 考年 ，月限日 日 期 : 3 年 ( 月 r 学 日 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 图目 录 1军用海量异构数据集成与共享技术研究总体图 l . zw h 工 p s 项目 的数据仓库构造过程. ， 二， _ _ . . ， ， ， 叼月，口j，八口nlq月孟仄曰只0门刁dj内b门2八洲0门八尸门八必门，们 卜1勿zqn自乙八。曰乙。自d八j自0飞口马j门。4444 .-，.，.1;，;:!. ;.!，:-，:，;:卜. .-.，. 2 . 1快照差分检测方法说明. 2 . 2各种算法消耗的工 /0量比较 . 2 . 3基于日志的检测分析说明 . . 图图图图图 图2 . 4 o r a c l e 数据库的日 志分析流程二 图 25r e c o r d d a t a 内容 二，. ， ， _. ， 二， . ， 二 甲 二 “， ，二 .，- 图2 . 6 r o w d a t a 内容二卜 . . . . . . . ， . . . . . . ， . . . . . . . . 图2 . 7 s q l s e r v e r 数据库的日 志分 析 流程. . ， ， ，. ， ， ， . 二 图3 . 1 数据获取系统结构图. 、 . ， . . ， ， . ， . ， . _ ， 图3 . 2简单数据转换模块结构图 . . . . 二 . . ， ， ， . . . 图3 . 3简单数据转换功能模块图 ， ， ， . _ _ . ， ，二 ， . ， ，. 、 . . ， ， ， ，. 图3 . 4数据源监视模块结构图 . . ，. . . . . . 二， . ， _ 图3 . 5检测分析模块结构图. “ ， 二_ _ . . ， ， ，. “ . “.， . . 图3 . 6重复记录检测模块结构图. . . . . 卜 . . ， . 卜 . . ， . 图4 . 1带有仿射g a p 的字符串 距离产生模型. . . . . . . . . . . . . . . . . . . 图4 . 2产生式模型的训练算法 . . . ， ， ， .二， 二， . . ， . ， . . 图4 . 3字符串生成的后缀树 . . . . . . . ， . ，二， . . . . . . . . . . . 图4 . 4基于距离的字符串匹配算法比较、 ， ， ， ， ， . .， ， . “.， 二_ 图4 . 5基于标记的字符串匹配算法比较 . . . . . . . . . 卜 . . . . . ， . 图4 . 6几种高性能的字符串 算法比 较 ， ， . ，. ， . . ， 二 ，. ， . 图4 . 7不同数据规模下算法的检测精度- . . 一 . . ，. ， . 图4 . 8不同数据规模下的算法运行速度 _ . . . . . . . . ， . . ， ，_ 图4 . 9在不同错误类型下比 较算法检测精度， ，_， ， ， 二 ， _ ， . 二下 ， 图4 . l d不同的数据规模下比较算法运行时间 . ， 卜 卜. . 卜 ， . 卜 . ， ， . . 11朋20小朋 表目录 表2 . 1算法结果比较图 . . ， . ，. . . . . ， . 二 ， ， . ， 表2 . 2 d b m s we l o g m n r . s t a r t - - l o g m n r 3 3 过程参数含义 r 卜 卜 ， . ， ， 二， . 表2 . 3 r e c o r d d a t a 作用 . . ， . . . . . . . . . . . . ， ，. . . 表2 . 4 r o w d a t a 字段作用. 二 ， ， ， ， 甲. ， 一 介， ， - ， ， ， ， ， 一 表4 . 1实验数据来源及其数据大小. . _ . . _ . . . . . . . . . . . . 一分 - 一一一 一. - 一. 一一一. - 一一 ;i 国防科学技术火学研究生院学位论文 1 ，l 。l 课题来源 第一章绪论 1 。l 课题背景与意义 信息作为军队的宝贵资源，占据着越来越重要的地位，成为军队科学训练、指挥的基 础，正确决策的前提，有效调控的手段。目前根据自己的特点和作战的需要，建立了一大 批各自的业务处理系统和指挥自动化系统，积累了大量的历史数据。 目前，军队现代建设呈现出“数据集中化、决策科学化”的发展趋势，雨大多数军队 单位由过去遗留下来的异构的系统已经不能满足这样的需求。很多军队单位立足于多年积 累的数据和作战需要，提出了建立海量数据中心的规划和实施方案，为军队的指挥自动化 及协同作战打下基础。这些年来，在信息技术领域兴起并日益成熟的数据仓库技术成为了 研究和应用的热点。事实证明数据中心在为军队科学地提高决策支持水平，提高军队应变 能力和军队的协同作战能力等方面有重要的意义。 论文的项目背景是军用海量异构数据集成与共享技术研究，该项目立足于完成对 现有异构数据的集成，并且针对不同用户的需求构建数据中心，从而为联合作战、装备统 一管理等打下良好基础。 图1 1 是该项目的总体结构图，系统以数据中心和相应的集成与共享工具为核心，按 模块化的方式设计，整个系统分为数据获取、数据管理和数掂服务三个层次。 数据管理层主要完成数据的集成、组织、管理与维护。主要包括以下功能：资源分析 与定位；根据元数据分析当前层次的数据资源的类型、结构、分布等特征信息，确定该数 据资源的统一资源位置，及当前层次所包含资源的整体信息；资源获取引擎：根据当前层 次的数据资源的特征信息，利用相应资源引擎，获取数据资源；资源展现：根掘当前层次 的数据资源的性质，展现该数据资源； 数据服务层主要提供数据需求建模工具让用户将需求按照统一模式提交到数据管理 层：另外用户可以依靠目录服务从数据管理层提取数据到用户数据集；数据挖掘工具让用 户能够分析数据以辅助决策进行。 论文研究的数据获取技术来自于数据获取层，这一层负责把分布于网络上的数据资源 注册为数据中心的数据源，并根据各异构、自治数据源的业务特性，制定相应的数据监视 与抽取策略，利用数据抽取工具适时地从各数据源中抽取、转换数据至数据管理层的数据 集成区。 第i 页 国防科! 学技术大学 f 究生院学位论文 瑶崮k 哗章捐口1 一 圈11 军用海量异构数据集成与共享技术研究总体图 1i ，2 数据蔹取的研究意义 数据仓痒星然为决莱支持系绕鹚数据存储和管理攘供了解次玄鬟。但是原婚数据还存 储在文本文件、x m l 文档、电子袤格和关系数据厍等各种数据源中，如何将这些数据加载 到数据仓库中成了新的问题。因为数据仓库的数据存储和组织形式与文件、电子表格相差 甚远，即使是与操作型关系数据库相比也有褶当大的差异，所以把各种原始数掘直接导八 数据仓库是不切实际的。 首先，数据在从面向应用到面向主题的转变过程中。要丢弃原柬不必要钓、不适于分 析的信息，统计生成决策分析所需要的信息。因此，当数据从操作型业务数据库或其它数 据源提取出来时，要先对其进行必要的处理才能将它们加载到数据仓库中。其次、在原 有的数据库模式中，有关某一主甄的信息可能被分散在各个数据源中，没有形成关于该主 蹙寇整一致的信息集合，所以还需要对源数据接主题重新组织。例如：某证券公司的业务 数据痒申蓑于“客户”这一主题的信息锕可链存在、盟务数据库的交易予幂绕、敷襄 善愚了 辰统咿而向主题的数据组织就是要鸦原乐关于两品的分散的信息组织起震，形成元整一 熬宕勺籀述，勰载到数据仓库中。再凌，业务数据霹中关于同一主题的数燕莅往存兹重复售 第2 页 国防科学技术夫学研究生院学位论文 息，或同一对象在命名方式或表达方式上不一致这些数据在被加载割数蘅仓库h j 斋妥嗣 其进行处理，去除重复数据，消除不一致现象。最后，前面提到数据仓库需要定期更新维 护来保持数据的准确性，从而对决策提供支持。因此需要对正常运行故业务数据系统定觋 获取增量的数据，并且根据面向主题、重复记录清洗的要求进行处理后，报送到数据仓库 中保持数据仓库数据与业务系统数据的一致性。因此，开发个具有通用性、性能稳定、 执行效率高的、适台多种数据源的获取工具就成为数据仓库在军事辅助决策中发挥重要作 用的重中之重。 数据获取是指从源文件或源数据库中获取数据，并经过集成、清洗、转换、优化届， 将其加载到数据仓库的过程“1 。其中，集成是将业务数据从多个数据源耿出，并映射到数 据仓库的新结构上去；清洗是指除去那些在给定范围之外或不符台数据仓库要求的数掘的 操作：转换是将操作数据转换成另一种更符合数据仓库要求的格式，优化是指根据实际需 要，应用优化算法对数据进行处理，使之便于分析和挖掘。 数据获取的目的有三个：一是去除源数据中韵大量重复和对统诗分祈无甬的数据，并 保证数掘的完整性，提高数据仓库中数据的质量：二是将数据按主题合理的组织，提高仓 库数据的可用性：三是定期对业务数据系统进行监视，获取增量数据，保持数掘仓库数掘 和业务数据的一致性。 数据获取过程是构建数据仓库的核心和灵魂，按照统一的规则集成，并提高数据的价 渔，是负责完成数据从数据源向目标数据仓库转化的过程，是实掩数据仓库的重要步骤。 如果晚数据仓库的模型设计是一座大厦的设计蓝图，数据是砖瓦的话，那么数掘获取就是 建设大厦的过程。在整个项目中最难部分是用户需求分板和模型设计，恧因为数据获取步 骤涉及到大量的业务逻辑和异构环境，数据获取规则设计和实施则是工作量最大的，其工 作量要占整个项目的6 0 一8 0 “3 ，这是国内外业界人士从众多实践中得到的普遍共识。 数据获取为数据仓库提供数据支持，使仓库中的数掘正确有效：使数据从而向应用转 换到面向主题；对原始操作型数据进行集成和聚合；使数据格式规范统一，方便决策系统 使用；对数据进行优化，使其更适合进行挖掘和分析。 从整体角度来看，数据获取工具的主要作用在于其屏蔽了复杂的业务逻辑从而为各种 基于数据仓库的分析和应用提供了统的数据接口，这也可以蜕是构建数据仓库最重要的 意义所在。 1 2 ，1 国外研究现状 l 。2 国内外研究现状 国外对数据仓库的研究比较早，技术相对成熟。许多数据痒系统提供了专门的数据转 换工具，如s q ls e r v e r2 0 0 0 的d t s ，o r a c l e 的s q l * l o a d e r ，i b m 的v 】s u a l 1 r e h o u s e 等。另外一些第三方软件开发商也推出了一些产品，例如：a s c e n t i a l 公司的d a t a s t a g e s a g e n t 公司的p o w e r c e n l _ - e r 等等。这些数据库跗带的、第三方公司开发的数据获取产品 对于结构化数据转换和加载的速度，海量数据的处理，对多种数据源的接口有很好的支持。 而对于数据库研究组来说，上面提到酌转换、加载速度并不是他舔j 钓硪究重点。不少 研究组织针对其他一些重要的技术展开研究工作，例如数据源监视方法，脏数掘清洗，重 复记录清除，数据仓库动态维护筹等。结合本文，重点介绍数据源监视技术和相似重复记 第3 页 国 防科 学 技 术大 学研 究 生 院学位 论 文 .g , -j 百-蔺奋蔽万 式 或 表 达 方 式 土 不 一 致 . 这 些 数 据 在 被 加 载 到 数 据 仓 库 时 需 要 对 其进行处理， 去除重复数据， 消除不一 致现象。 最后， 前面提到数据仓库需要定期更新维 护来保持数据的准确性， 从而对决策提供支持。 因此需要对正常运行的业务数据系统定阴 获取增量的数据， 并且根据面向主题、 重复记录清洗的要求进行处理后， 报送到数据仓库 中， 保持数据仓库数据与业务系统数据的一致性。 因此， 开发一个具有通用性、 性能稳定、 执行效率高的、 适合多种数据源的获取工具就成为数据仓库在军事辅助决策中发挥重要作 用的重中之重。 数据获取是指从源文件或源数据库中获取数据，并经过集成、清洗、转换、s i p 化后， 将其加载到数据仓库的过程【 ， 。 其中， 集成是将业务数据从多个数据源取出， 并映射到数 据仓库的新结构上去; 清洗是指除去那些在给定范围之外或不符台数据仓库要求的数据的 操作: 转换是将操作数据转换成另一种更符合数据仓库要求的格式， 优化是指根据实际需 要， 应用优化算法对数据进行处理，使之便于分析和挖掘。 数据获取的目的有三个; 一是去除源数据中的大量重复和对统计分析无用的数据， 并 保证数据的完整性， 提高数据仓库中数据的质量: 二是将数据按主题合理的组织， 提高仓 库数据的可用性; 三是定期对业务数据系统进行监视， 获取增量数据 保持数据仓库数据 和业务数据的一致性。 数据获取过程是构建数据仓库的核心和灵魂， 按照统一的规则集成， 并提高数据的价 值，是负责完成数据从数据源向目标数据仓库转化的过程，是实施数据仓库的重要步骤 如果说 数据仓库的模型设计是一座大厦的设计蓝图， 数据是砖瓦的话， 那么数据获取就是 建设大厦的过程。 在整个项目中最难部分是用户需求分析和模型设计， 而因为数据获取步 骤涉及到大量的业务逻辑和异构环境， 数据获取规则设计和实施则是工作量最大的， 其工 作量要占 整个项目 的6 0 % - 8 0 % ， 这是国内 外业界人士从众多实践中得到的普遍共识。 数据获取为数据仓库提供数据支持， 使仓库中的数据正确有效; 使数据从而向应用转 换到面向 主题; 对原始操作型数据进行集成和聚合; 使数据格式规范统一， 方便决策系统 使用;对数据进行优化，使其更适合进行挖掘和分析。 从整体角度来看， 数据获取工具的主要作用在于其屏蔽了复杂的业务逻辑从而为各种 基于数据仓库的分析和应用提供了统一的数据接口， 这也可以说是构建数据仓库最重要的 意义所在 。 1 . 2 国内外研究现状 . 21国外研究现状 国外对数据仓库的研究比较早， 技术相对成熟。 许多数据库系统提供了 专门的数据转 换t具，如s q l s e r v e r 2 0 0 0 的d t s , o r a c l e 的s q l * l o a d e r , i b m 的v i s u a l w a r e h o u s e 等。 另外一些第三方软件开 发商也推出了 一些产品， 例如: a s c e n t i a l公司的d a t a s t a g e s a g e n t 公司的p o w e r c e n t e r 等等。这些数据库附带的、第三方公司开发的数据获取产品 对于结构化数据转换和加载的 速度， 海量数据的处理， 对多 种数据源的接口 有很好的支持 而对于数据库研究组来说， 上面 提到的转换、 加载速度并不是他崛 飞 的研究重点， 不少 研究组织针对其他一些重要的技术展开研究工作， 例如数据源监视方法， 脏数据清洗， 重 复记 录清除， 数据仓库动态维护等等。 结合本文， 重点介绍数据源监视技术和相似重复记 第 3页 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 录检测技术的相关研究情况。 i 数据源监视器的研究现状 s t a n f o r d 大学w h i p s 项目 主要研究数据仓库的维护而不是应用问题(3 s 8 1 。 负责这一i ii? r 的j o a c h i m h a m m e r 等人认为数据仓 库存储了 从多 个数据源中抽取的集成数据; 这些数 据可以看作定义在数据源基表上的实化视图。视图是定义在一个或儿个基表 l 的导出关 系，当视图中的元组被实际存储时，别称为实化视图。 因此， 当数据源中的基表发生变化时， 必须维护数据仓库中的实化视图以反映这一变 化。j . h 二 二 等人提出了实现这一维护过程的体系结构，如下图所示: r tr, t 乙 钊 蔽a田 - 3 4 涵 厂 尸 监视模监视模块 、飞 卜 应 妙 口 刃厂 数据源基表数据源基表数据源基表 图1 . 2 w h i p s 项目 的数据仓库构造过程 图1 . 2 中， 位于体系结构底部的是数据源， 其中的数据发生变化后， 这些变化就被抽 取并集成到接近顶部的数据仓库中去。 最顶部的是客户应用程序， 这是用户与数据仓库进 行交互的工具。 介于数据仓库和数据源之间有两个组件， 其中监视模块负责检测分析数据 源的变化， 并发给集成模块。 而集成模块的任务有两个: 接收监视模块报送来的数据源变 化， 并转化为数据仓库可以理解的格式; 将转换格式后的数据源变化合并到数据仓库中去。 维护数据仓库的功能主要依赖这两个组件来完成。 数据源监视模块用于完成数据仓库维护的 第一个步骤: 检测分析数据源变化( 增量数 据) 并报送。文献仁 3 中讨论了检测分析数据源变化的两种可能方法: 如果数据源是功能完备的数据库系统， 则可以通过定义一组触发器， 或者通过读取日 志的方式来检测分析数据源的变化。 该方法的可行性及实现依赖于具体的数据源类型， 比 如文本型数据源就不支持日 志或触发器机制。 可能出于这限制， w h i p s 项目 没有相关文献 对该方面工作进行深入探讨。 而对于任意类型的数据源， 都可以 用快照差分的方法检测分析数据源的变化: 每隔一 定时期重新生成基表的快照， 同上一次的旧快照作差分计算， 得到反映基表自上 次到本次 生成快照以来变化的增量数据。 增量数据中可以只包含数据源中被删除或插入的元组。 文 献 4 综述了可应用于快照差分的算法， 包括几种常用算法: s o r t m e r g e 算法、 p a r t i t o n h a s h 算法、w i n d o w 算法和一类新提出的基于压缩策略的算法并对所有这些算法作了 详尽的分析; 文献 5 , 6 针对两类特殊数据讨论了监视数据变化的方法， 它们分别是树 型数据和层次型数据。 第 4页 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 集成模块用于完成数据仓库维护的第二个步骤: 接收数据源变化( 增量) 并集成到数据 仓库中。 由 于这方面并不是本文的 研究重点， 相关研究状况不详述， 有兴趣可参看 7 , 8 1 0 2 ，相似重复记录清洗的研究现状 集成数据的质量是整个系统的关键点。 由于现存的管理系统中存在的问题造成很多种 脏数据类型:滥用缩写词、 惯用语、 数据输入错误、 重复记录、 丢失值、不同的计量单位 和过时的编码等19 . in ) 。其中由于多数据源合并 造成的相 似重复记 录( d u p l i c a t e r e c o r d ) 问 题是指一个现实实体可能由多个不完全相同的记录来表示， 也就是说两条记录语义上是等 价的， 而表现形式可能有些出入。 因为相似重复记录给决策分析带来很大的危害， 所以重 复记录问 题最为关键， 相关的重复信息的 检测和消除也成为研究的热点 ， 1. 12 纵观多年来该方向的 研究文献， 相似重复记 录的清洗采用 “ 排序 而文献 1 4 使用“ 联结” 的方法来近似 匹配记 录的域;文献【 1 2 根据用户自己定义的键重排记录，然后再使用滑动窗口来做 p a i.r - w i s e 比较窗口内记录: 文献 1 2 提出用户可以定义多个键。 也就是使用m u f t i - p a s s 方法对0录进行排序，提高了检测的准确率;文献 1 6 1 改进了记录排序的思路，提出 u n i o n - f i n d 算法，最终将记 录分为几个u n i o n ，然后进行p a i r - w i s e比较;文献 1 7 , 1 8 1 将每个记录看作“ 源记录蛋 ， 以之为基础查询和构造相似记录组， 采用 n - g r a m 聚类算法将 相似一记 录聚到一个c l u s t e r 中，并对每个c l u s t e r 中的记 录进行p a i r - w i s e 比较。 在记录相似度度量算法方面的 研究也已 经有了 一些成果。 文 献 1 9 , 2 0 ) 提出了计算字 符串“ e d i t - d i s t a n c e ” 的算法， 两者比 较类似; 文献 2 川对文献巨 9 的算法进行了改进， 增加了字符交换的处理功能，算法的复杂度都为o ( m n ) :文献 2 1 , 2 2 1 提到的 s m i t h - w a t e r m a n 算 法复 杂 度为。 ( m x n x m a x ( m , n ) ) ， 现 在也 有 研究并 行s m i t h - w a t e r m a n 算法。 此外，除了 数据库研究领域研究相似度度量算法外，其他的研究领域如人口 统计、 人工智能、 网络安全及生命d n a 研究， 也对字符串匹配展开研究， 其中的一些理论非常值 得借鉴，第四章中会对这些思想展开详细描述。 1 . 2 . 2国内研究现状 国内在数据仓库方面的研究和应用起步比 较晚， 目 前还没有商品化的产品， 大多还处 于实验室阶段。 目前。 国内大部分数据仓库系统采用针对系统本身设计开发的e t l 工具， 有的甚至用 手工方法实现数据仓库的加载。 因此当 数据仓库结构发生变化或者重建数据仓库时， 需要 重新编程实现该过程。 相似重复一记录检测方面， 复旦大学周傲英教授和他的学生对相似重复一记 录清洗方向有 一定研究， 并且发表多篇文章5 9 . m l h 。 其中 文献仁 5 9 对数据质量， 尤其是数据清洗的研究进 行了综述。首先说明数据质量的重要性和衡量指标， 定义了数据清洗问题。然后对数据清 洗问题进行分类， 并分析了解决这些问题的途径。 最后说明数据清洗研究与其他技术的结 第 5页 国 防 科 学 技 术 大 学 研 究 生 院 学 位 论 文 合情况， 分析了几种数据清洗框架。文献 6 0 提出了一个可扩展的数掘清洗框架。它以术 语模型、 过程描述文件、 共享库等概念和技术实现了模块的高度独立性和系统的可扩展性， 并提供了一个可视化的流程定义环境。文献 s 川提出了一种高效的基于n - g r a m 的聚类算 法，该算法能够适应常见的拼写错误从而较好的聚类相似重复记 录。 1 . 2 , 3存在问题 当前。 国内外现有的数据获取系统大多数存在针对性较强， 缺乏普遍的适用性， 难以 进行二次开发等问 题。 因为， 有些产品主要是大数据库提供商基于自己公司的数据库产品 开发出来的， 虽然有较高的执行效率， 但是对于没有数据库引擎支持的数据源就缺乏很好 的处理方法，而且不能完成重复记录的清洗工作。 对于数据源监视，在现状中提到s t a n f o r d 大学的w h i p s 项目 提出的数据仓库体系结 构图中， 由监视器负责监视数据源的变化并报送给集成器。 但在对监视器的设计中存在一 些不足s k . 不能定制哪些数据变化是要需要进行监视的( 即不能指定需要监视韵具体字段) 。 造成传输和处理不必要信息的额外开销; . 对监测到的数据变化采用立即 报送的策略，不提供对报送方式的定制比 如周期 等，这就违背了数据仓库不是时新的特性; . 该项目 仅仅对有数据库管理系统的数据源进行监视， 对象平板文件那样的数据源 并没有展开研究。 相似重复记录的检测问题也是研究的热点之一， 上面提到了 大量的文献专注于此。 但 是，算法由于精确率低、复杂度高，一直没有得到很好的应用。 检测方法都是要基于记录的关键字段或者是记录的结构特征来进行的， 而且因为字符 串的p a i r - w i s e 比 较是一个重要的原子 操作， 它的低效会直接影响到整个算法的效率， 可 以看出设计一个精确度高的、快速的相似度量方法是检测相似记录的关键。 在实际数据中经常会出现这样的问 题， 例如中文文章的参考文献写法不同， 姓和名经 常 会颠 倒写， 如 b ia n z h a o q i , z h a n g x u e g o n g e t a l . p a t te r n r e c o g n i t io n ( i n c h in e s e ) , 2 d e d i t i o n . ” 有些人会写成“ z h a o q i b i a n . x u e g o n g z h a n g e t a l . p a t t e r n r e c o g n i t i o n ( i n c h i n e s e ) , 2 d e d i t i o n . ，这个例子人工检测一定会认为这是两个相似重复记录，但是如果使用 e d i t - d i s t a n c e 的算法却会认为 它们之间的距离很大， 可见字符串 编辑距离并不是一 个理想的选择。 同样的在中文字符串中， 描述地点的两个字符串“ 湖南长沙” 、 “ 长沙湖南” 和 “ 湖南益阳”三个字符串之间根据编辑距离计算，第一个字符串到第二个的距离为4 , 而第一个到第三个的 距离为2 ， 而我们从语义上来理解， 前两个的相似度要明显大于第三 个。 从这两个例子中明显可以看到基于编辑距离的字符串度量方法没有考虑到字符串在结 构上的特点， 而上面两个例子在数据记录中是经常存在的， 因此引发了对字符串 距离度量 算法的进一步改进。 尽管文献 2 6 , 2 7 ) 中 提出块操作概念， 块操作是指一个字符串中连续 的块在进行插入/ 删除/ 移位/ 翻转操作时， 编辑距离为一个 恒定值， 但是仍然不能完全的 解决这个问题。 由于 e d i t - d i s t a n c e 算法的 局限 性， 驱使 研究 者寻 找一 个替 代的方 法。 概率 树 专个 ( s u f f i x t r e e )在查找子串、 序列比 较上的应用引起了 研究者的注意， 文献 3 0 注于d n a 序列的聚类问题， 构建了基于序列统计属性的相似度测量方法， 因为紧接着- 第 6页 国防 科 学技术 大学 研 究 生 院 学位 论 文 s e g m e n t 的 寺 异 乡 的 条 件 概 率 分 布 能 够 更 准 确 的 描 述 这 个 序 列 的 结 构 特 性 ， 克 服 了 前 面 几 种 方法的不足:并且提出了 基于 概率的 后缀树 ( p r o b a b i l i s t i c s u f f i x t r e e ) 被用 来组织 获取的一个du s t 、 中序列的条件概率分布，这使得才 别 以 度的估算变得更准确。 如何改进记录相似度度量 字符串距离度量) ，使其拥有较高的准确率，并减少算法 的复杂度;还有对记录排序方法的改进都是提高重复记录检测方法效率和准确率的关键 点。 1 . 3 论文研究的主要内容 结合课题背景， 本文深入研究了数据仓库的数据获取技术， 其目的是为了能够支持各 种异构数据源集成为数据仓库的构建提供高 质量的可靠数据， 最终为用户的决策分析提供 保障。具体来讲，主要包含以下几个方面的内容 : i .针 一 对平板数据源的增量数据获取展开研究 首先了解数据源监视获取增量数据的研究现状， 对现存的方法进行比较; 针对平板文 件数据源， 选用基于快照差分算法的数据源监视方法， 对三种快照差分算法进行复杂度分 析，并且做实验对算法的工 / 0 量作比较 最后确定选用w i n d o w 算法作为系统使用的差分 算法。 针对数据源监控的粒度问题进行研究， 调整了该模块的监视粒度， 支持对某个源表字 段的监视，过滤掉那些无关的数据变化，可以 提高监视的效率;提供可定义的监视规则， 其中包括了检测分析周期等， 监视器就按照这些规则检测分析和报送数据源的变化， 使得 数据仓库更新策略更加符合数据仓库应有的特性。 2 .数据获取原型系统的设计与实现工作 系统的设计主要解决现状分析中提到的问题。 对于如何检测数据源的更新数据， 并报 送到数据仓库， 我们使用快照差分算法和基于日 志的检测方法， 来分别处理无数据库功能 支持和有数据库支持的数据源; 对于半结构化数据， 我们使用一系列的行列变换， 满足数 据仓库决策数据的要求: 如果存在两个或者两个以上的相近数据源准备报送到数据仓库的 数据， 为了避免出现相似重复记录的现象， 提高分析决策的可靠性， 可以使用相似重复记 录检测算法， 对相似重复记录进行标示提交用户判断。 整个系统包括四个模块: 数据转换 模块、数据源监视模块、重复记录检测模块和总控制台模块。 3 .针对相似重复记录检测