（计算机软件与理论专业论文）生物数据抽取与更新若干问题研究.pdf

生物数据抽取与更新若干问题研究摘要 【摘要】 近十年来，在世界范围内众多研究机构的推动下，生物数据呈指数级增长。 如何将这些数据整合起来，为生物学家搭建方便而高效的查询分析平台，已成为 计算机界研究的热点。数据集成是实现在线数据查询和分析的有效方法，数据抽 取和更新是数据集成中的两个关键技术。 d e w r a p p e r 是一种面向复杂数据源的数据抽取程序，它使用扩展正则表达 式( e r e ) 及其对应的数据抽取树( d e 树) 作为数据抽取模型。然而由于生物 数据领域的特殊性，在使用d e w m p p p e r 进行数据抽取和数据更新时面临着一些 问题，如：e r e 的建立太复杂；e r e 中可能存在冲突；大量分布的异构生物数 据源使数据更新的实现非常困难等等。本文从元数据的获取和维护的角度出发， 对数据抽取和更新中存在的问题进行了研究，最后给出了系统实现。主要研究成 果如下： ( 1 ) 研究了e r e 中的切分二义性问题，提出了切分二义性的检测和定位算法， 给出了有害的切分二义性和有益的切分二义性的处理方法。 ( 2 ) 针对生物数据源的多样性、易变性、异构性、分布性等特点，定义了描 述生物数据源的通用元数据模型，并提出了集中式元数据仓储的结构。从而实现 了异构生物数据源的数据更新。 ( 3 ) 实现了d e w r a p p e r 的可视化编辑调试环境。该环境首先使用可视化界面 支持e 徊e 树可视化构建，然后自动检查该e r e d e 树是否具有二义性，最 后在样本数据上运行抽取算法并给出数据库结构和抽取结果，供用户进行评价， 从而逐步引导用户设计出满足要求的e r e d e 树。 ( 4 ) 实现了生物数据仓库的增量更新系统。该系统使用本文中定义的元数据 模型和数据仓储结构，保证了生物数据仓库增量更新的通用性和可扩展性。 关键词：数据抽取，数据更新，元数据，d e w r a p p e r ，e r e ，d e 树 中图法分类号：t p 3 1 1 生物数据抽取与更新若干问题研究 绪论 a b s t r a c t i nt h el a s tt e ny e a r s ，谢t l lt h ep r o m o t i o no ft h em a n ys c i e n t i f i co r g a n i z a t i o n ，t h e b i o d a t ah a sb e e ng r o w i n ge x p o n e n t i a l l y i ti su r g e n ta n di m p o r t a n tt o d e v e l o pa n a d e q u a t eb i o - d a t am a n a g i n ga n da n a l y z i n gs y s t e mt oi n t e g r a t ei m m e n s eb i o - d a t a d a t ai n t e g r a t i o ni sa ne f f e c t i v et e c h n o l o g y , w h i c hi n c l u e d sd a t ae x t r a c t i o na n dd a t a u p d a t e d e - w r a p p e ri sap r o g r a mt oe x t r a c td a t af r o mc o m p o u n dd a t as o n r c e ，w h i c h u s e st h ee x t e n dr e g u l a re x p r e s s i o n s ( e r e ) a st h ee x t r a c t i o n m o d e l h o w e v e r , t h e r e a r es o m ed i f f i c u l tw h e na p p l yd e w r a p p e rt oc r e a t ed a t ai n t e g r a t i o ns y s t e m f o r e x a m p l e ，t h ec r e a t i o no ft h ee r ei sv e r yc o m p l i c a t e d ；t h e r ea r es o m ea m b i g u o u sf o r t h ee r e ，a n di ti sv e r yd i f f i c u l tt oc o n d u c td a t au p d a t ei ns om a n yd i s t r i b u t e da n d i s o m e r o n sb i o l o g i c a ld a t as o u r c e b a s e so nt h ea c q u i r e m e n ta n dm a i n t a i n e ef o rt h em e t a d a t a ，t h i sp a p e rs t u d i e st h e p r o b l e m so ft h ed a t ae x t r a c t i o na n dd a t au p d a t et h e ni m p l e m e n t st h es y s t e m t h e a c h i e v e m e n t sp r e s e n t e di nt h i sd i s s e r t a t i o na l ea sf o l l o w ： ( 1 ) s t u d i e st h es y n c o p a t i v em a t c h i n ga m b i g u i t yo fe r ea n dp u tf o r w a r da m e t h o dt oe x a m i n ea n do r i e n t a t i o nt h es y n c o p a t i v em a t c h i n ga m b i g u i t y ，t h e nt h i s p a p e rd e s c r i b eh o w t od e a lw i t ht h eb e n e f i c i a l b e n i f i e a ls y n c o p a t i v em a t c h i n g ( 2 ) d e f i n e sac o m m o nm e t ad a t aw h i c hd e s c r i b et h eb i o l o g i c a ld a t as o u r c e s ；p u t s f o r w a r dt h es t r u c t u r eo fm e t a d a t ar e p o s i t o r y i ts a t i s f i e st h er e q u i r e m e n to fu p d a t ef o r t h ei s o m e r o u sb i o l o g i c a ld a t as o u r c ei nt h ed i s t r i b u t e de v i r o m e n t ( 3 ) av i s u a le d i t i n ga n dd e b u g g i n ge n v i r o n m e n tf o rd e - w r a p p e ri si m p l e m e n t e d f i r s t l y , t h i se n v i r o m e n te n a b l e st h ev i s u a l c o n s t r u c t i o nf o rd e t r e e s e c o n d l y , i td e t e c t t h ea m b i g u i t yo fe r e t h i r d l y , i tr u n st h ed a t ap r e - e x t r a c t i o na n ds h o w st h er e s u l t u s i n gg u i i th e l p st od e s i g nt h ee r e d e - t r e es t e pb ys t e p ( 4 ) a ni n c r e m e n t a lu p d a t es y s t e mi si m p l e m e n t e d i ta p u i e st h em e t a d a t am o d e l a n dt h ed a t ar e s p s i t o r yd e f i n e di nt h i sp a p e r , i n s u r et h ea d a p t a b i l i t ya n de x p a n s i b i l i t y k e y w o r d s ：d a t ae x t r a c t i o n ，d a t au p d a t e ，m e t a d a t ad e w r a p p e r , e r e ，d e - t r e e c h i n e s el i b r a r yc l a s s i f i c a t i o nn o t p 3 1 1 i i 生物数据抽取与更新若干问题研究绪论 第1 章绪论 1 1 研究意义 近十年来，在世界范围内众多研究机构的推动下，生物数据呈指数级增长。 迄今可利用的在线生物数据源已达5 0 0 多个 d 1 0 4 】。如何将他们整合起来，为 生物学家搭建方便而高效的查询分析平台，己成为计算机界研究的熟点 h e 0 4 【e r 0 4 】 c j m 0 4 。 数据集成是实现在线数据查询和分析的有效方法，它包含数据抽取和更新两 个关键技术【w i 9 5 】。数据抽取程序又称包装器。 d e - w r a p p e r 【d z 0 5 是一种面向复杂数据源的包装器。它提出了一种将模型 结构和抽取规则合二为一的数据抽取模型，该模型用无“选择”运算的扩展正则 表达式( e r e ) 和与之对应的数据抽取树( d e 树) 同时描述数据源结构和抽取 规则。 然而由于生物数据领域的特殊性，在使用d e w r a p p p e r 进行数据抽取和数据 更新时面临着一些挑战，例如： ( 1 ) d e - w r a p p p e r 使用e r e 描述数据源，这些e r e 的建立和维护需要用户手 工完成。由于生物数据源的结构往往比较复杂，手工书写描述数据源结构的e r e 是一件繁重的工作；另外，由于同一数据源在不同的抽取粒度下具有不同的e r e 描述，用户需要经过反复实验才能确定最终的e r e 。需要提供相应的辅助方法 对于e r e 的构造进行支持。 ( 2 ) 用户构造的e r e 可能存在二义性f 邓0 5 】，d e w r a p p e r 中允许用户使用 一些有益的二义性从而降低e r e 建造时的工作量，而禁止用户使用会影响数据 抽取结果正确性的有害二义性。用户很难自己去区分这两种二义性，因此需要提 供检查并定位e r e 二义性的方法。 ( 3 ) 由于不同的研究机构关注不同层面的生物学问题，导致生物数据源在结 构和语义上存在着巨大的异构性曹0 4 。而生物技术的迅速发展，也使生物数 据呈指数级迅速增长。如何从具有不同格式、不同存储模式和不同数据类型的多 个易变数据源中获取和转换数据，以实现生物数据的灵活更新，已为一项重要而 迫切的研究课题。 生物数据抽取与更新若干问题研究绪论 针对上述问题，本文从元数据的获取和维护的角度出发，对数据抽取和更新 中存在的问题进行了研究。对于e r e 的构造问题，提出了e r e 的可视化构造方 法；对于e r e 中存在的二义性问题，提出了基于有限自动机的e r e 二义性检测 和定位算法。针对生物数据源的多样性、易变性、异构性、分布性等特点，定义 了描述生物数据源的通用元数据模型，并提出了集中式元数据仓储的结构。从而 实现了异构生物数据源的数据更新。本系统已用于构建国内第一个整合的生物信 息数据仓库，详情见h t t p ：w w w b i o s i n o o r g b i o d w 。 1 。2 研究背景 1 2 1 生物数据集成 随着i n t e m e t 上可以获得的生物数据源爆炸式的增长以及数据源的异构性和 不同的实现方式，使得从多个数据源中获取所需要的信息变得越来越困难。如何 在异构的生物数据源之间实现数据集成与共享是有效利用生物信息资源的关键。 传统的使用手工方式浏览、查询、抽取，以及组合信息的方法无法满足生物学家 对于生物数据查询和分析的需求。显然应当有一种更好的方法来完成这种任务， 那就是数据集成。数据集成系统根据用户定义的条件帮助用户收集信息，找到合 适的方案。数据集成系统为解决多平台、多结构数据的集成问题提供了一条解决 途径。通过数据集成系统，用户可以通过一个单一的用户界面从多个数据源中获 取所需要的信息，从而大大减轻了研究人员的负担，为生物学的研究和发展奠定 良好的数据基础，具有重要的理论价值和实际意义。 根据集成系统所实现的策略进行分类，可将生物信息学数据集成方法分为如 下四种 h k 0 3 】【h s 0 3 】【d c b o i + 】 w o n 0 2 】 s l 9 0 】：数据仓库的方法( d a t a w a r e h o u s ea p p r o a c h ) 、联邦数据库集成方法( f e d e r a t i o na p p r o a c h ) 、基于中介器 的集成方法( m e d i a t o r - b a s e di n t e g r a t i o n ) 和链接驱动集成方法( l i n k d r i v e n i n t e g r a t i o n ) 。数据仓库的方法将各个数据源的相关数据汇集到具有全局数据模式 和索引系统的一个统一的系统即数据仓库中，所有的数据查询都将在数据仓库中 进行。数据仓库与其它解决方案相比具有效率高，便于数据清理和数据转换的优 点，是目前生物学领域最为常用的解决方案 s l 0 4 】。本文的数据集成系统采用 了数据仓库方案。 数据抽取和更新是数据仓库的数据集成方案中的两个关键技术，后面两节将 分别对生物领域的数据抽取和数据更新进行讨论。 生物数据抽取与更新若干同题研究绪论 1 2 2 生物数据抽取 数据抽取是数据集成的基础。数据抽取程序又称包装器。数据抽取负责从各 数据源提取所需数据，将其按照与数据源相关的数据库模式进行组装后提交给数 据集成的后序步骤。 从数据抽取的角度来看，与普通的半结构化数据( 例如网页) 相比，生物文 档有两个特性。首先，一然生物数据源数据量很大，现有的商用的包装器不能够 处理，如g e n e b a n k 生物序列展开文件总计达1 0 0 g b 。这种数据源必须使用文本 流的方法进行处理，而不能把整个文档都存放到内存。其次，生物领域往往需要 非常高的精度，虽然生物文档具有一些结构方面的解释，但是这些解释是面向读 者的，文档中并不具有网页中可别计算机程序处理的h t m l 标记，更加糟糕的 是，在注释部分中声明的分割字符可能出现在文档那个的任何位置( 例如，噪声 数据) 。实际上，目前的包装器，依赖于简单的分隔符，不能够正确地学习结构 或者抽取规则，因此抽取的信息的精度较低。生物数据库的建立者通常对于不同 的文本通常必须使用p e f l ，a w k 重复编写不同的程序，这使生物数据的维护者的 工作量极大，往往不能及时地完成任务。 为了解决从具有噪声的海量文本例如生物学文件中抽取数据，d e w r a p p e r 提出了一种将模型结构和抽取规则合二为一的数据抽取模型，o 用无“选择”运 算的扩展正则表达式( e r e ) 和与之对应的数据抽取树( d e 树) 同时描述数据 源结构和抽取规则( e r e 和d e 树的等价性证明见 邓0 5 】) ；用户只需给出 描述数据源结构的e r e ( 由一些嵌于圆括号中的局部抽取规则构成) ，无需分别 给出模型结构和全局抽取规则。是一个高效的数据抽取工具。 在d e w r a p p e r 中，e r e 是唯一需要人工维护的元数据d z 0 5 。但是在e r e 的构造和维护过程中，也存在着一些困难： ( 1 ) 由于实际数据源往往具有复杂的结构，所以构造描述数据源结构的e r e 是一件繁重的工作，d e w r a p p e r 虽然定义了e r e 的d e 树 d z 0 5 ，但是并没 有提供具体的可视化实现方法。所以使用g u l 支持可视化d e 树构造，以克服 手工书写e r e 时的困难是十分必要的。 ( 2 ) 由于同一数据源在不同的抽取粒度下具有不同的e r e 描述【d z 0 5 i ，用 户需要经过反复试验才能确定最终的e r e ，所以用户需要一种能够评价抽取结 果的工具以确定当前的e r e 是否满意。 ( 3 ) 语法上正确的e r e ，可能存在语义上的二义性。由于数据源的结构非常 生物数据抽取与更新若干问题研究绪论 复杂，完全禁止用户书写具有二义性的e r e 是非常困难的：另外，允许用户使 用一部份具有二义性的e r e 描述数据源可以大大降低用户的工作量。基于上述 的原因，d e w r a p p e r 将e r e 中的二义性分为有害二义性和有益二义性，并允许 用户书写具有有益二义性的e r e 。由于用户不能够自己去区分这两种二义性， 因此需要提供检查和分析这两种二义性的方法。在文章 邓0 5 】中虽然给出了检 测r e 二义性的方法，但是对于e r e 中的二义性并没有进行系统的研究。 1 2 3 生物数据更新 采用数据仓库方案的数据集成系统的一个很大的缺点是由于数据没有及时 更新导致查询结果的不可靠性。系统必须定期地检查数据源数据的变化并将这些 变化反映到数据仓库中。数据仓库的增量更新是采用这种方法所要解决的主要问 题之一 c k l 9 7 】，其具体步骤为包括定时从数据源抽取增量数据，对其进行清 洗和转换，并将新数据加载入数据仓库。 由于不同的研究机构关注不同层面的生物学问题，导致生物数据源在结构和 语义上存在着巨大的异构性。而生物技术的迅速发展，也使生物数据呈指数级迅 速增长。如何从具有不同格式、不同存储模式和不同数据类型的多个易变数据源 中获取和转换数据，以实现生物数据的灵活更新，已成为重要而迫切的研究课题。 为解决上述问题，需要对数据更新的元数据的定义和管理进行规范，具体工 作包括下面两方面的内容： ( 1 ) 建立元数据模型( m e t a m o d e l ) 。元模型为元数据提供了扩展性。即使系统 中的元数据的内容或结构发生变化，系统的运行仍然可以正确运行。此时我们称 该系统是元模型驱动的。 ( 2 ) 建立一个元数据仓储( m e t a d a t ar e p o s i t o r y ) ，以支持元数据的聚集、访问 及其生命周期管理。系统内的所有元数据均存放在此元数据仓储中，从而实现分 布式环境下元数据的集成管理。 使用上述方法有效地解决了下异构生物数据更新的通用性和扩展性问题。 1 3 本文工作 本文针对构造生物数据抽取和更新中存在的主要问题，从元数据获取和维护 的角度，对系统中的数据结构、算法、应用流程、以及系统架构进行了研究，其 主要研究成果如下： 4 生物数据抽取与更新若干问题研究绪论 ( 1 ) 介绍了e r e 中的切分二义性问题，并使用有限自动机理论提出了切分二 义性的检测和定位算法，并讨论了对于有害的切分二义性和有益的切分二义性的 处理方法。 ( 2 ) 对于数据更新中存在的问题，本文对系统中存在的元数据进行了分析。 针对生物数据源的多样性、易变性、异构性、分布性等特点，为数据更新过程中 的元数据建立了可扩展的元模型并给出了元数据仓储的实现思路。从而实现了异 构生物数据源的数据更新。 ( 3 ) 实现了d e w r a p p e r 的可视化编辑调试环境。该环境首先使用可视化界 面支持e r e d e 树可视化构建，然后自动检查该e r e d e 树是否具有二义性， 最后在样本数据上运行抽取算法并给出数据库结构和抽取结果，供用户进行评 价，从而逐步引导用户设计出满足要求的e r e d e 树。 ( 4 ) 实现了生物数据仓库的增量更新系统。该工具使用本文中定义的元模型 为基础，建立了以数据仓储为中心的元模型驱动的增量更新系统。 1 。4 论文结构 全文共分成6 章，文章结构及各章内容简介如下： 第一章是引言。主要是本文的立论意义，生物数据领域数据抽取和更新的研 究背景、挑战和研究方向，然后介绍了本文的研究内容和成果，最后，给出了本 文整体的组织结构。 第二章是背景知识的介绍。介绍了生物数据抽取和更新已有的工作；介绍了 元数据的基本概念，第二章是本文研究工作的基础。 第三章是e r e 切分二义性检测，本节首先讨论了e r e 切分二义性。基于有 限自动机提出了e r e 的二义性的检测和定位方法，最后讨论了各种切分二义性 的处理方法。 第四章是增量更新技术。本节首先分析了生物数据源的特点，然后为增量更 新过程中的元数据定义了可扩展的元数据模型，最后提出了元数据仓储的结构。 第五章是系统实现。主要介绍了d e - w r a p p e r 的可视化编辑调试工具v i d e 和增量更新的系统实现。 第六章是结论和展望，总结全文，展望进一步工作的方向。 生物数据抽取与更新若干问题研究e r e 剀分二义性检测 第2 章背景知识介绍 2 。1 正则表达式与扩展正则表达式 2 1 1 正则表达式 正则表达式( 是一个模式字符串，用于在给定字符串( 称“主字符串”) 中搜索与之匹配的子串。r e 由普通字符和元字符构成。表2 1 给出了部分r e 元 字符及其含义( 其中表示空串) 。 元字符含义及匹配例子 匹配任一字符。如：“r ”匹配“r a 和r u 等。 匹配0 次或多次。如“l l , t ”匹配s 、a 、；“， 匹配任意字符串。 + 匹配1 次或多次。如：“9 + ”匹配9 ”、9 9 ”等。 匹配0 次或1 次。如“a b ? ”匹配“a ，和“a b ”。 转义字符。如：“s ”匹配一个空格符；“8 ”匹配一个非空白符；“n ”匹 t 配一个换行符。 【】 匹配字符类中任一字符。如：“r 【 o 】t i 匹配“r a t 和 r o t ”；“【a l i t - g ” 【c 1 0 2 】 匹配任何字母；“【一a - z 】，匹配除大写字母外的任何字符。 【“c 1 - c 2 】 ir e 分组运算符，详见下文。 “选择”运算符。如：“a i l a 匹配a ”或b ”。 表2 1 正则表达式中的元字符 在r e 中，一对圆括号代表一个子r e ，称为“r e 组”或简称“组”。此外， 圆括号还表明其中含有需要抽取的内容。每个组有一个编号，整体是第0 组，其 余组的编号可通过对字符“r 从左向右从l 开始计数得到。若j j ，的下一个字符为 “一、“+ ”或“则称该字符为相应组的标记字符，否则组的标记字符定义为。匹 配成功后，每个组都会捕捉一个匹配字符串。例如，f ：f 刁- 彤曰盯矗叼”匹配字 符串 a 1 2 b a b ”。整体是第0 组；“( o - 9 1 ”是第1 组；“_ 口可”是第2 组，且第 0 组捕捉整个字符串；第l 组捕捉“凹”；第2 组捕捉“动”。有关正则表达式的详 尽论述请参阅p e r l 语言及相关文献。 2 1 2 扩展正则表达式及其抽取树 定义2 1 ( 扩展正则表达式) ： 扩展正则表达式( e r e ) 【邓0 5 是本文对数据源的 6 生物数据抽取与更新若干问题研究e r e 切分二义性检测 逻辑结构进行描述的模型。e r e 是一个具有下列格式的字符串： r o o t 此处， 表示根节点的名字： 表示一个非封闭的扩展正则 表达式( n e r e ) 。 一个n e r e 和一个r e 形式相同，其区别在于：在n e r e 中，除“ 、“+ ” 或“，外，组的标记字符还可以是、“”，“ ”，“”，7 ”或7 ”。 对于任意一个e r e 来说，第0 组的标记字符默认为“幸，。 d e - w r a p p e r 用符合p e r l 语义的受限r e 来描述抽取模型，即禁止“r j ”参与 “| ”和“加，n 2 ”运算( “1 j 厂可用“。j p f j ? ”模拟，“r j 加j ，n 2 1 ”可用“1 j 一 或“f ，+ ”模拟) 。r e 中的圆括号对称为组。若组的“) ”下一个字符为“”、“+ ” 或“? ”，则称之为该组的标记，否则其标记定义为s ( 即空串) 。我们用“r ”和” 将e r e 整体括起以示统一。e r e 中起始于“r ”、，”、 ”、+ ”或，7 ”下一个 字符，终止于“( ”或“) ”上一个字符的无圆括号非空子串称为原子。 我们将e r e 映射成数据抽取树( d e - 树) 【邓0 5 】以支持其可视化构造。图 2 2 展示了k e g g 化合物展开文件的e r e 对应的d e 树。 q-“ _ 图2 1k e g g 化合物展开文件的e r e 对应的d e 树 d e - 树中每个节点h 持有一个模板n f 和一个标记万t ，+ ，+ ，；， ，】，、， ， 一 。形式定义如下： 定义2 2 ( 数据抽取树) ：正则表达式陀的d e 树i r e ) l l p 在阳上运用下列递归规则 所生成的树：生成叶节点九( ) ，且满足九( ) f = 8 ，九( ) 丫= ；0 原子o 生成叶 节点九( 0 ) ，且满足九( o ) r = 0 ，九( e ) y = ；0 序列j = 6 1 6 2 6 i 生成节点c 1 ，q ，仇， 其中c 一是由6 ，生成的节点( f - 1 ，2 ，i ) ； 标记为7 c 且包含序列j 的组g = 氕生成非 ， 生物数据抽取与更新若干问题研究 e r e 切分二义性检测 叶节点巩酚，且满足j 生成的节点c l ，c 2 ，c k 都是行( 曲的子节点， 疗( 曲r = ( c 1 。f c 2 f c k fl 兀，以( 曲丫= 氕。 2 2 使用e r e 进行数据抽取 2 2 1 数据抽取技术和包装器 图2 1 3 给出了数据集成系统的基本结构。在这一结构中，抽取器是最为基础的 部件，负责从数据源抽取所需数据并按预定的数据库模式包装后提供给集成器进 行集成。 图2 3 数据集成系统的基本结构 数据抽取( d a t ae x t r a c t ) 弗不是简单的数据读取，用户必须在分析源数据库， 目标数据库元数据的基础上，在弄清数据库定义，转换需求的基础上，提取需要 转换的数据，从原来操作型数据库中抽取相关数据到数据仓库或另外的数据库 中。确定如何抽取或查询数据并不是件容易的事，在实施中它需要经过以下步骤： f 1 ) 建立起与源数据系统的连接 ( 2 ) 从源数据库中提取出源表的列表，确定提取的表。 ( 3 ) 根据源表、提取规则、最后提一次取的时间戳或用户数据提取的条件生 成动态提取语句。 ( 4 ) 将提取出数据通过网络传送到数据抽取程序程序所在的机器。 包装器( w r a p p e r ) 是一种数据抽取程序，包装器常用树或有向图来描述数据源 的模型结构( 其节点又称数据类型) ，用抽取规则在数据源中搜索数据对象 【b a 9 8 】 l r d 0 4 。在使用包装器的数据仓库中，数据仓库应提供方便的元数据管 8 生物数据抽取与更新若干问题研究 e r e 切分二义性检测 理和维护环境，以应对数据源数目的增加和结构的变化。这些元数据与数据抽取 过程密切相关，包括：数据源，o 数据模型，0 抽取规则， 抽取算法，o 与 数据源相关的数据库模式， 转换规则，即描述已抽取数据项向相应数据库模式 映射的元数据。 上述诸多元数据间存在着明显的依赖关系：数据源决定数据模型，数据模型 直接或间接地决定了所有其他元数据。当数据源结构变化时，这些元数据都要作 相应的修改。因此，充分利用元数据间的依赖关系，以减少需人工维护的元数据 数目，对需要从众多不断变化发展的数据源抽取数据的生物数据仓库而言有着重 要的应用价值。 然而，现有数据抽取方法并未有意识地利用元数据间的依赖关系，大多采用 将元数据分离或简单叠加的松散组织方式。例如，文献l b a 9 8 用一个g u i 指导 用户半自动地构造抽取规则集，并与手工定义的数据模型中的某个数据类型联系 起来，以驱动其抽取算法去抽取数据；已抽取数据的组装则凭借用o d l 手工给出 的数据库模式来实现。 2 2 2d e w r a p p e r 简介 目前许多大的机构都积累了大量的数据，但是由于历史的原因，这些数据往 往存放在多种异构数据源中，如何将这些数据集成起来，搭建方便而高效的查询 分析平台，已成为计算机界研究的热点。为此，必须解决两个关键问题：一是如 何从各种复杂的数据资源中获取有用数据；二是如何将获取的数据按其内在结构 存入关系数据库中。 d e w r a p p e r 邓0 5 是一种面向复杂数据源的数据抽取工具。为了充分利用 元数据间的依赖关系以降低元数据维护的工作量，d e w r a p p e r 采用扩展正则表 达式将上述元数据集成起来，提出了一种新的数据抽取方法，其基本思路是：用 e r e 作为唯一需要人工维护的元数据来描述数据源，其他元数据则通过本文给 出的关系数据库模式生成算法和通用数据抽取和组装算法自动导出或实现。图 2 4 给出了d e w r a p p e r 的框架结构。这一结构展示了用d e w r a p p e r 来抽取数据 源的步骤： ( 1 ) 通过参考数据源结构说明书和样本数据，数据库设计人员用d e w r a p p e r 提供的扩展正则表达式( e r e ) 准确地描述领域专家的数据抽取意图。 ( 2 ) 语法及逻辑检查程序检测给定的e r e 中是否存在语法或逻辑错误，若存 在错误，数据库设计人员需修改e r e ，直到语法与逻辑检查通过为止。 生物数据抽取与更新若干问题研究e r e 切分= 义性检测 ( 3 ) 抽取程序在给定e r e 的驱动下，对样本数据进行预抽取。如果领域专家 对抽取结果不满意，数据库设计人员需修改e r e ，直到领域专家满意为止。此 时，从预抽取结果中可获得相应的数据库模式，但各字段的长度还不能确定。 ( 4 ) 抽取程序在给定e r e 的驱动下，将数据源抽取到装载文件。抽取结束后 计算出各个字段的最大宽度并根据预抽取的数据库模式建表。最后将装载文件装 入关系数据库。 图2 4d e - w r a p p e r 框架结构 该工具功能强大，在实际的运用中取得了很好的效果，但却使用文本编辑器 输入e r e ，用命令行方式启动运行，对用户十分不友好，很有必要为该工具开 发一个g u i 。首先，由于实际数据源往往具有复杂的结构，所以构造描述数据源 结构的e r e 是一件繁重而复杂的工作，既要求用户熟练掌握正则表达式的语法， 又要求用户尽量避免由于人为疏忽所产生的语法和逻辑错误，所以使用g u l 支 持可视化d e 树构造，以克服手工书写e r e 时的困难是十分必要的。其次，由 于同一数据源在不同的抽取粒度下具有不同的e r e 描述，用户往往需要经过反 复试验才能确定具体选择哪一个e r e ，所以用户需要一种能够评价抽取结果的 工具以确定当前的e r e 是否满意。第三，对于一个在语法上正确的e r e ，可能 存在语义上的二义性，所以需要检测e r e 中存在的二义性，并指出二义性发生 的位置和原因。 2 3 元数据概述 2 3 1 元数据的定义 元数据( m e t a d a t a ) g g o o ，通常定义为描述数据的数据，旨在便利存取、管 生物数据抽取与更新若干问题研究e r e 切分二义性检测 理、共享和处理大量结构化和或非结构化的数据。在过去的几年里，元数据的 概念在现实中大量使用，如为了支持信息检索，或为了软件配置，或为了不同系 统之间的数据交互。对于不同应用领域，元数据有着不同的应用，但这些元数据 的存在有两个共同点。元数据对数据进行描述；元数据的存在是为了更有效地使 用数据，元数据是关于数据的结构数据。 2 3 2 元数据的作用 元数据的定义是“关于数据的数据”，比如传统数据库中的数据字典就是一 种元数据。近年来，随着计算机技术应用的广泛化，元数据得到人们越来越多的 关注，这是由多方面的需求决定的。 ( 1 ) 管理数据的需求。当系统数据量越来越大时，检索、使用这些数据的效 率就会降低，通过存储关于系统和数据的内容、组织、特性等细节信息( 这些即 为元数据) 可以帮助有效地进行管理，从而提高效率。 ( 2 ) 系统分布、互通和重用的要求。目前信息系统一个共同的趋势就是信息 共享，要实现异构系统中的信息共享，就需要描述数据语义、软件开发过程的元 数据，而且这些元数据必须标准化，以充分实现分布、互通和重用。 ( 3 ) 元数据重用、综合的需求。目前，很少有单一工具能满足大型商业应用 的需求，用户常常需要使用多种工具的组合，不同工具之间的数据交换的途径之 一就是通过标准的元数据。 元数据是关于数据的数据，是对“业务数据”本身及其运行环境的刻画和定 义的数据，因此元数据具有上述重要的功能。而且，现有企业不仅仅要处理好各 种应用数据，更需要着力从事的是如何建立和管理好自己的企业级的元数据信息 仓储。使之成为连接各种应用的纽带和衍生新应用的源泉。 2 3 3 元数据的分类 因为元数据有上述重要的作用，元数据也得到广泛的应用。对于元数据，从 不同的角度来观察，可以划分为不同的类别。 按照与特定领域是否相关，元数据可以分类为： ( 1 ) 与特定领域相关的元数据：描述特定领域内数据在此特定领域内的公共 属性。 生物数据抽取与更新若干问题研究e r e 切分二义性检测 ( 2 ) 与特定领域无关的元数据：描述所有数据的公共属性。 ( 3 ) 与模型相关的元数据：描述信息和信息建模过程的数据。该类型的元数 据又可分为两类： a 横向模型关联元数据：综合现有的两个或多个信息模型，例如两个不同 数据库之间的交互、从多个数据源中提取数据时，就需要这种横向模型元数据。 当不同的信息模型之间要进行互通时，需要模型各个层的关联描述，即横向模 型关联元数据。 b 纵向模型关联元数据：模型信息层与元信息层之间的关联元数据口不同 的层可以采用不同的模型，上层是下层的结构描述，上下层之间的对应关 联，即纵向模型关联元数据。 ( 4 ) 其他元数据：例如系统硬件、软件描述系统配置描述等。 按照元数据的应用场合，元数据可以分类为： ( 1 ) 数据元数据，又叫做信息系统元数据。信息系统使用元数据描述信息源， 以按照用户需求检索、存取和理解源信息。于是，元数据保证了在新的应用环境 中使用信息，支持了整个信息结构的演进。 ( 2 ) 过程元数据，又叫做软件结构元数据。是关于应用系统的信息，它帮助 用户查找、评估、存取和管理其数据。大的软件结构中包括描述各个组件接口、 功能和依赖关系的元数据，这些元数据保证了软件组件的灵活动态配置。 按照元数据的具体内容，元数据可以分类为： ( 1 ) 内容：识别、定义、描述基本数据元素，包括数据单元、合法值域等等。 ( 2 ) 结构：在相关范围内定义数据元素的逻辑概念集合。 ( 3 ) 表示：描述每一个值域( 多为技术相关的) 的物理存储结构。 ( 4 ) 文法：提供基础数据的族系和属性评估，它包括了所有与基础数据的收 集、处理和使用相关的信息。 2 3 4 元数据管理 元数据层次 从元数据的定义来看，元数据只是一个相对的概念 o m g 】【m d 9 9 】 【m r + 9 5 。元数据本身也可以有描述它的“元元数据”，因此从理论上说元数据 生物数据抽取与更新若干问题研究 e r e 切分= 义性检测 可以有多个抽象层次。每个上层的元数据都描述了其下层的元数据的内容。在通 常情况下，一个系统中的元数据至少应该分为四层： ( 1 ) 数据层( d a t a ) ：即系统中的用户信息，即实际数据。 ( 2 ) 元数据层( m e t a d m o ：该层为描述用户信息的元数据。 ( 3 ) 元模型层( m e mm o d e l ) ：该层定义了元数据的语法结构和语义，该层为概 念层，该层通常包括了特定的建模语言，例如u m l 。 ( 4 ) 元元模型层( m e t am e t am o d e l ) ：该层定义了元模型的语法结构和语义， 该层统一了不同的建模语言( 不同的建模语言代表了不同的方法学，例如面向对 象分析方法和实体联系分析方法) ，元元模型是自描述的。 元数据仓储 元数据被存储并保存在一个元数据仓储( m e t a d a t ar e p o s i t o r y ) 【0 9 0 0 d i n 0 0 中，元数据仓储通常是一个结构化的存储更新系统，通常基于数据库管理或者文 件系统实现。目前的元数据仓储的分布方式 m m + 9 9 可以分为以下三种方式： ( 1 ) 集中式：对于大多数的中等规模的组织而言，单一的元数据库就足够各 种团队所需的元数据，其基本概念是建立统一的元数据模型，用该模型定义和管 理各种元数据，并将所有元数据集中存储在中心元数据库中。所有工具和数据仓 库直接访问中心元数据库，而不局部存储和管理元数据。 ( 2 ) 分散式：由于不同的工具、软件组件和元数据库往往使用不同的数据模 型、不同的表示格式，集中管理几乎是不可能的。事实上，在确保元数据库可互 操作的前提下，通常采用分散管理。这种方法的目标是局部元数据库自治管理局 部元数据，建立统一的共享元数据模型来管理全局元数据，它是各局部元数据库 中元数据的子集。这是元数据管理的另一种极端情况。 ( 3 ) 邦联式：邦联方法结了前两种方法的优点。每个工具拥有自己的元数据 库，因而支持快速访问和自治，并提供与共享元数据库的交换接口，共享元数据 库管理所有共享的元数据。局部元数据库可以采用异构的表示形式，而共享的元 数据库必须采用统一的元数据表示形式，如基于标准的元数据模型或自定义模 型。邦联结构保护了元数据库的自治性和异构性。每个局部元数据库自己确定需 要导出哪些元数据到共享的元数据库中。 生物数据抽取与更新若干问题研究e r e 切分二义性检测 第3 章e r e 切分二义性检测 语法上正确的e r e 可能仍然存在语义上的二义性，即该e r e 与一个字符串 可能具有多种匹配形式。d e - w r a p p e r 中允许用户使用一些有益的二义性从而降 低e r e 建造时的工作量，而禁止用户使用会影响数据抽取结果正确性的二义性。 用户很难自己去区分这两种二义性，因此需要提供检查并定位e r e 二义性的方 法。本章首先描述了e r e 切分二义性问题，并给出e r e 切分二义性的定义。接 着基于自动机理论提出了一种e r e 切分二义性的检测方法，最后我们讨论了各 种切分二义性的处理方法。 3 1e r e 切分二义性问题 3 1 1r e 二义性 我们说一个r e 具有二义性f r s s g 7 1 ，是指该r e 与某个字符串存在多种 匹配方式。例如，给定正则表达式，口，和字符串 a x x x x x b ”，采用最短匹配的结 果是饥”，而采用最长匹配的结果则是 a x x a x x b ”。 对于r e 中的二义性问题，目前的处理方法有：返回所有可能的匹配； 拒绝含二义性的r e ；用一种二义性消除方法来猜测用户的匹配意图，挑选一 个默认的匹配。方法匹配结果将不唯一；方法事先对r e 进行二义性检查， 并要求用户修改含二义性的r e ，这对用户丽言是非常困难的；方法目前最为 流行，其= 义性消除方法又可细分为：等价改写、最长匹配和贪婪匹配等。等价 改写【k e 9 1 】【h a 9 9 的方法工作量太大，而且原r e 会变的非常复杂。最长匹配 【v a n 0 3 】【h p 0 1 】 t s y 0 2 是一种上下文相关的匹配方法，缺点在于在多支路的情 况下，算法复杂度太高。贪婪匹配是最长匹配方法的局部近似 h 0 0 3 ，是目前 比较流行的二义性消除方法。 3 1 2e r e 切分二义性 e r e 中的二义性与r e 的二义性略有不同，允许e r e 的某些二义性可以降 低用户书写正则表达式的工作量。例如，给定扩展正则表达式协印一，虽然 该e r e 具有二义性，但是由于其左右边界都是确定的，所以此时使用默认的贪 婪匹配就可以满足所需要的匹配情况。然而最长匹配或贪婪匹配却不一定总是满 1 4 生物数据抽取与更新若十问题研究e r e 切分二义性检测 足用户的匹配预期。为说明理由，在此先对e r e 作简单分析。 和算术表达式不同的是，e r e 中的圆括号对( 即组) 不仅是改变匹配优先 级的操作符，而且是刻画主字符串层次结构的分组符，匹配时每个组都要捕捉一 个子串( 即对象) 。因此e r e 中的组刻画了对象的层次结构，表达了用户对主字 符串的层次切分意图邓0 5 。基于上述理由，用户往往期望对象具有清晰的边 界，同时会用含有二义性的无圆括号e r e