(论文)价模型的不一致XML数据修复启发式计算

I S S N 1 0 0 0 9 8 2 5 。C O D E N R U X U E W J o u r n a l o f S o f t w a r e ，V 0 1 2 0 ，N o 4 ，A p r i l2 0 0 9 ，P P 9 1 8 - 9 2 9 d o i ：1 0 3 7 2 4 S P _ J 1 0 0 1 2 0 0 9 0 3 2 2 5 0b yI n s t i t u t eo f S o f t w a r e t h eC h i n e s e A c a d e m yo f S c i e n c e s A l lr i g h t sr e s e r v e d 基于代价模型的不一致X M L 数据修复启发式计算宰 吴爱华L 2 ，王先胜1 ，谈子敬l + ，汪卫1 1 ( 复旦大学计算机信息与技术系，上海2 0 0 0 7 2 ) 2 ( 上海海事大学计算机科学系，上海2 0 0 1 3 5 ) E m a i l ：j O S i s c a s a c e n h t t p ：w w w j o s o r g c n T e 岍弧：+ 8 6 1 0 6 2 5 6 2 5 6 3 AC o s t B a s e dH e u r i s t i c A l g o r i t h m f o rR e p a i r i n gI n c o n s i s t e n tX M LD o c u m e n t W UA i H u a L 2 ，W A N GX i a n S h e n 9 1 ，T A N Z i J i n 9 1 + ，W A N G W e i l 1 ( D e p a r t m e n to fC o m p u t e r I n f o r m a t i o n T e c h n o l o g y ，F u d a n U n i v e r s i t y 。S h a n g h a i 2 0 0 0 7 2 ，C h i n a ) 2 ( D e p a r t m e n to f C o m p u t e rS c i e n c e ，S h a n g h a i M a r i t i m e U n i v e r s i t y ，S h a n g h a i2 0 0 1 3 5 ，C h i n a ) + C o r r e s p o n d i n ga u t h o r ：E m a i l ：z j t a n f u d a n e d u c n W u A I t ，W a n g X S ，T a nZ J ，W a n gW A c o s t - b a s e d h e u r i s t i c a l g o r i t h m f o r r e p a i r i n g I n c o n s i s t e n tX M L d o c u m e n t J o u r n a l o f S o f t w a r e ，2 0 0 9 ，2 0 ( 4 ) ：9 1 8 - 9 2 9 h t t p ：w w w j o s o r g c n l 0 0 0 9 8 2 5 3 2 2 5 h t m A b s t r a c t ：C o m p u t i n g a r e p a i r f o r i n c o n s i s t e n tX M Ld o c u m e n t si ss i g n i f i c a n ti n a p p l i c a t i o n s B u t g e e i n g a n o p t i m u mr e p a i r i saN P c o m p l e t ep r o b l e m e s p e c i a l l y w h e nX M Ld o c u m e n t sv i o l a t e b o t ht h e f u n c t i o n d e p e n d e n c e a n dt h ek e yc o n s t r a i n t s T h i s p a p e rp r o p o s e s ac o s t - b a s e dh e u r i s t i c a l g o r i t h m ，w h i c h C a nf i n da r e p a i r w i t ht h e l o w e s tc o s ti np o l y n o m i a lt i m e I tf i r s tS C a n St h eo r i g i n a lX M L d o c u m e n t so n c et og e tt h ei n c o n s i s t e n td a t a T h e ni t c o m p u t e s t h e g e n e r a l c a n d i d a t er e p a i r sf o re a c hi n c o n s i s t e n t d a t a ，a n dg e t saw h o l e d o c u m e n t r e p a i r h e u r i s t i c a l l y b a s e d o ni t sc o s t T h e e x p e r i m e n t a l e v a l u a t i o ns h o wt h a te v e nw h e nX M Ld o c u m e n t sa r e l a r g e ，w i t hh i g h p e r c e n t o f d i r t ye l e m e n t s ，a n da g a i n s t m a n y d i f f e r e n tc o n s t r a i n t s ，t h e a l g o r i t h m C a l ls t i l lr u ni nl e s st h a n O ( n ) w r t t h e s i z e o f i n c o n s i s t e n te l e m e n t s K e yw o r d s ：i n c o n s i s t e n c y ；i n c o n s i s t e n td a t a ；r e p a i r ；c o n s i s t e n t a n s w e r ；X M Ld a t ac l e a n i n g ；i n c o m p l e t e d a t a b a s e 摘要：在实际应用中，为不一致的X M L 文档计算最优修复意义重大但求解最优修复是一个N P 完全问题，特别 是在X M L 文档同时违反函数依赖约束和主键约束时提出一个基于代价模型的、可以在多项式时间内完成的启发 式修复求解算法该算法首先借助索引表，在一遍扫描原始X M L 文档的情况下寻找不一致数据集，然后为每一类约 束的不一致数据集构造候选修复，同时计算其修复代价，最后启发式地求解一个代价最小的修复方案实验结果表 明，该算法的时间复杂度不超过冲突类的3 次方即使是在不一致数据量很大，噪声比例很大以及涉及多类语义约 束时也能较快地完成修复 关键词：不一致性；不一致数据；修复；一致的查询回答；X M L 数据清洗；不完整数据库 中图法分类号：T P 3 l l文献标识码：A 数据完整性约束是准确数据必须遵循的准则，也是数据的语义所在但在实际应用中，因各种原因，数据常 违反其完整性约束，如错误操作、多数据源合并等在X M L 下该问题尤为突出因为：( 1 ) 数据本身的问题，作为 S u p p o r t e d b y t h e N a t i o n a l N a t u r a l S c i e n c eF o u n d a t i o n o f C h i n a u n d e r G r a n t N o 6 0 6 0 3 0 4 3 ( 国家自然科学基金) R e c e i v e d 2 0 0 7 0 8 - 2 2 ；A c c e p t e d 2 0 0 7 l l 0 2 吴爱华等：基于代价模型的不一致X M L 数据修复启发式计算 9 1 9 一种半结构化数据，X M L 的数据模型复杂，语法灵活，特别是W 3 C 缺乏X M L 约束方面的严格规范；( 2 ) X M L 广 泛应用于数据交换和数据集成，而这类应用环境下，即便单数据源都一致，但当多数据源合并时，仍常发生数据 冲突因此，不一致X M L 文档的修复意义更为重大 例1 ：设图l 中的X M L 数据是两数据源合并的结果，实线部分来自A ，虚线部分来自召描述的是某港机公司 承接的项目，p r o j e c t 表示项目，p r o j e c t N a m e 能够标识一个p r o j e c t ，为完成某p r o j e c t ，须采购若干零部件 ( p a r t ) ，p a m l D 标识p a r t ，每个p a r t 具有来源( s o u r c e ) 、颜色( c o l o r ) 和安装日期( d a t e ) 等属性而s o u r c e 又包含供应商 名( c o m N a m e ) 和该部件的售价( p r i c e ) 根据图1 所示的约束，该X M L 数据中存在以下不一致的数据： ( 1 ) 存在两个名字都叫D a l i a n P o r t 的p r o j e c t ； ( 2 ) S P P C 公司生产的同一个零部件在实线子树中为r e d ，但在虚线子树中却为g r e e n ； ( 3 ) S P P C 公司提供的1 0 号零件，在实线中价格为10 0 0 ，但在虚线中却为15 0 0 ； ( 4 ) 实线子树中，1 1 号零件在2 0 0 6 5 1 安装； ( 5 ) 虚线子树中，1 0 号零件的安装日期为空 R e l a t e dc o n s t r a i n t s ： c l ：I n t h e w h o l ed o c u m e n t ，p r o j e c t N a m e i d e n t i f y ap r o j e c t ( e | p r o j e c t s p r o j e c t ，( p r o j e c t N a m e ) ) ( x 1 ，k 】= 靖l I 2 ) i c 2 ：I nap r o j e c t 。p a r t l Di d e n t i f yap a r t ( p r o j e c t $ p r o j e c t , p a r t s p a r t ，( p a r t l D ) ) ( x 1 ， x H j x d = x 9 i c 3 ：I n t h e w h o l e d o c u m e n t ，c o m N a m e d e t e r m i n ec o l o r o f p a r t ( A l lp a r t so f s a m ec o m p a n y i so f s a m ec o l o r ) ( e , p r o j e c t s p r o j e c t i p a r t s p a r t ( s o u r c e c o m N a m e c o l o r ) ) ( x , y 1 ， x , Y 2 j y l = Y 2 ) 科：I nt h e w h o l e d o c u m e n t p a r t l D a n d c o m N a m ed e t e r m i n e p r i c eo fp a r ( P ，叫e c 衄加，可e c 咖a r t s p a r t ，( p a r t l D , s o u r c e c o m N a m e , s o u r c e p r i c e ) ) ( 【0 力| ，l 】，【O ，力J 蝴= 们= ) ) i c 5 ：I n s t a l l d a t ec a nn o tb e N U L L ，a n d N o p a r t c a l lb e i n s t a l l e d o n 2 0 0 6 - 5 1 ( e , p r o j e c t s p r o j e c t p a r t s p a r t ，( 如地) ) ( h 】= 拟f _ 2 0 0 6 - 5 一I ) ( e 妒r o j e c t s p r o j e c t p a r t s p a r t ，( d a t e ) ) ( x l j x ! = N U t L ) F i g l A ni n c o n s i s t e n tX M Ls e c t i o n 图l 一个不一致的X M L 数据片段 在图1 这样的不一致数据源上提交查询，回答可能包含不正确信息，因此必须修复不一致数据源根据文献 1 】，修复是没有违反完整性约束且和原数据距离极小的数据不一致数据的修复在数量上巨大，求解其所有修复 是一个m a x N P 2 】难问题时间消耗在指数级而在实际应用中，求解所有修复和求解最优修复的意义基本一样虽 然后者也是一个N P 完全问题( 参见第2 节) ，但可以使用启发式算法寻求到多项式时间内的解 每一类约束都有其独特的修复特征，如：主键约束要求违反它的子树在主键上取不一样的值；而函数依赖约 束的修复，则内在地要求将所有语义上违反了同一个函数依赖的子树的目标节点置等若数据只违反一类约束， 则寻找多项式时间内的修复方法也不是一件难事但在实际应用中，数据的不一致性是综合的只考虑一类约束 或逐个修复不一致数据，都可能给出错误修复因为一条记录的变动可能影响其他记录，导致新的冲突产生这 两类做法意义都不大好的修复算法应该能够考虑到同一节点违反多约束的情况而各类约束中，内在矛盾的是 J o u r n a l o fS o f t w a r e 软件学报V 0 1 2 0 , N o 4 ，A p r i l2 0 0 9 置等和置不等两类约束，置等类约束要求所有违反同一约束实例的子树都必须在目标节点上取相同值而置不 等类约束则要求所有违反同一约束实例的子树在目标节点上取不同值总之，好的修复方案应具有如下特点： ( 1 ) 能够适用尽可能多的常用约束类型；( 2 ) 能够在多项式时间内完成；( 3 ) 能够综合考虑所有不致数据的修 复，不会带来新的不一致；( 4 ) 能够修复规模大和错误率高的X M L 文档；( 5 ) 准确率高 本文综合考虑了多类约束，包括：( 1 ) 域约束；( 2 ) 根据其他节点的取值来限定某个节点的取值；( 3 ) 函数依 赖；( 4 ) 主键约束涵盖了实际应用中的大部分约束设计了一种基于代价模型的启发式算法，能够在多项式时间 内寻找不一致的X M L 文档的一个最优修复本文的贡献在于： 提出了适合X M L 文档修复的基于代价模犁的启发式算法，能够在多项式时间内寻找整个X M L 文档的 修复实验证明，这种方法确实能够缩短时间； 提出了适合X M L 的代价模型，因为其树状特性，X M L 的代价模型比关系数据的代价模型要更复杂，本 文充分考虑了X M L 的特性，给出了节点修改、节点删除、节点插入、子树删除和子树插入的代价模型， 而且在代价模型中还考虑到操作类别、距离和可信度3 个要素： 能够同时解决置等和置不等约束，在扩大问题范围之后，仍能取得较好的时间性能； 扩展了冲突类的概念和冲突类索引表，并给出使用冲突类索引表检索X M L 文档中冲突类的算法，它能 在一次遍历下，检索出X M L 中所有的不一致数据，这使得本文能够处理大型X M L 文档 1 相关工作 关于数据一致性问题，关系数据库和数据交换领域已展开了广泛的研究，包括f 】- - 6 1 ，但X M L 领域尚处在起步 阶段一致信息一般通过下面两种方法得到：( 1 ) 修复，即寻找与原文档距离最小的一致数据；( 2 ) 一致的查询回 答，即找出能够在所有修复中出现的公共回答本文使用的是第1 种方法 本文借鉴了关系领域中的基本概念和方法：将文献【1 】提出的修复概念延伸到X M L 领域；将文献【7 】提出的 主键索引表修改并应用到X M L 领域；借鉴并丰富了文献【4 ，5 】在关系数据清洗中提出的基于代价模型的启发式 算法文献【4 】针对的是函数依赖和包含依赖，其代价模型要素包括数据源可信度和目标属性的字符编辑距离提 出了平衡类的概念，以归结所有应共享同一目标值的属性算法的基本思路是，先扩展平衡类，再根据代价选择 最优目标值文献【5 】针对的是数值类非主属性的修复，以目标属性的数值距离为基本代价，并提出了覆盖代价的 概念其基本思路是，找出所有相互矛盾的数据集( 约束违反集) ，寻找一个能够解决矛盾且距离原值最小的目标 值来修复约束违反集，同时计算其覆盖代价，根据它，启发式地计算整体最优解但X M L 的结构、约束、查询和 修改操作远比关系数据库要复杂，这些方法不能直接应用到X M L 领域如：R e p a i r 概念需重新修改以适应树状 结构；文献【4 ，5 】的代价模型对树状结构不适用；修复计算方法不能直接应用到X M L 领域本文将平衡类和约束 违反集的概念扩展为适合X M L 的冲突类，重新定义了适合X M L 且考虑多修复操作的代价模型，给出了适合 X M L 的冲突类修复的计算标准 就X M L 领域而言已有相关工作可以归纳为： 第l 类，不一致X M L 文档修复的整体框架比如文献 8 】，它通过构造所有修复，再求交集来得到一致数据， 复杂度高，耗时大尽管两者考虑的约束模型类似，但本文求的是最优修复而不是所有修复，效率更高 第2 类，X M L 数据集成和变换中的语义约束保持和查询结果一致问题文献 9 】研究的是如何将遵循原 D T D ( d o c u m e n t t y p ed e f i n i t i o n ) 的X M L 文档重构为遵循目标D T D 的X M L 文档，并如何进行相应的查询改写 文献 1 0 】讨论了X M L 数据集成中如何保证函数依赖的一致其应用背景和研究目的都和本文的不尽相同 第3 类，某类约束的X M L 数据一致性文献 1 l 】讨论了一组函数依赖上的不一致数据的修复问题，主要使用 的操作是节点修改文献 7 】着重于X M L 键值重复的修复本文的约束类型更宽泛，但其困难也更大文献【1 2 】解 决的是违反D T D 的不一致X M L 数据的修复问题，而不考虑X M L 上的完整性约束。这和本文的工作有所不同 与已有X M L 修复工作相比，从约束类型上说，本文能够综合修复多类型约束从修复操作上说，前人工作只 支持节点删除和节点插入两种，本文支持删除、修改和插入，并引入操作系数，以优先某种操作 吴爱华等：基于代价模型的不一致X M L 数据修复启发式计算 2 系统模型和代价模型 9 2 1 X M L 文档上的约束包括结构方面的约束( 由D T D 或x M LS c h e m a 定义) 和语义方面的约束( 由X M L 语义 约束表示) ，本文处理的是后者本文的修复对象是无D T D 或X M LS c h e m a 的X M L 文档至于如何保证X M L 文 档上不存在违反其D T D 或S c h e m a 的数据，文献【1 2 】对其进行了研究另外，本文假设所处理的X M L 文档已被先 序编号，系统也已按( 起始标号，结束标号) 为X M L 文档建了索引本文允许节点修改、子树( 节点) 的删除和插入 3 种操作这里，我们约定删除以节点n 为根的子树的操作，记作d e l e t e ( n ) 。在节点n 下面插入一个根节点标签为 t a g 的子树，记为i n s e r t ( n ，t a g ) ，而将子树，1 修复为子树t 2 ，则记作r e p a i r ( t 1 ，t 2 ) 定义2 1 给定一个X M L 模式D ，D 上的语义约束是这样的一个二元组俾l 冀2 ，( Q 1 ，Q 2 ，幺) ) ( 蜀, X 2 ，k j 逻辑表达式) ，其中皿1 皿2 ，9 ( 1 幽) 是路径表达式【”1 皿l 是约束的作用范围皿2 是目标节点，易( 1 f 如) 是约束节 点石，X 2 ， j 逻辑表达式是约束条件，逻辑表达式的每一个关系表达式都形如u O w ，其中，纳置谓词，l ，是变 量或包含变量的表达式，而W 是常量、变最或包含变量的表达式整个约束表示在R 】范围内，所有的R 2 节点上， 如果Q ，Q 2 ，g 满足蜀尚，山，就必须要使得条件为真 X M L 语义约束总是与其作用范围联系在一起。是一个相对概念 定义2 2 形如职1 皿2 ，( Q l ，Q 。) ) ( 【C 墨，忑，一1 ) 1 1 【( 而，。，k 一1 ) 2 】= 妙l 可2 ) 的约束称为置等约束 图l 的约束i c 3 ，i c 4 就是这类约束，它们内在要求找出所有具有相同的Q i ( 1 y ，那么皿C l 修改 工，使得x y ；R C 2 修改Y ，使得x y 皿C 3 删除x 所在的子树；R c 4 插入子树，使得该子树在约束节点上的取值满足约束 无论哪一种，修复的数量4 ；( 3 ) 一维多元约束，基本思想和一维二元的类似，是限定每一元变量的取值，使得约 束能够得以满足假设有k 个变量工I J 2 ，J I ，那么修复有：R C l 修改第羽f ”或“”且W 1 W 2 ，则合并后的限制条件是x a w l 如果区间合并中出现 矛盾，则摒弃该模糊修复如果所有模糊修复都被否定，那么整个文档不能修复根据候选修复的产生方法，节点 值修改的候选修复可能是：a ) N A = x ( x O w l ) 或b ) N 1 4 可O 曰1 ) & & 2 一可O 口咖1 ) M 一= x ( x a w l ) 两个a ) 形式的候 选修复合并，结果仍然是a ) 形式的候选修复；a ) 形式的候选修复和b ) 形式的候选修复合并，结果仍是b ) 形式的，但 相关节点约束已被合并后的节点约束所代替；两个b ) 形式的候选修复R C l 和尺c 2 合并，结果仍是b ) 形式的，是 R C l & & R c 2 ，且R C 】和R c 2 中相同节点的约束已合并精确修复以后，某个节点的取值约束是确定的或具有一定 的取值范围 T a b l e3F i r s tr o u n do ft h eg r e e d y c o m p u t e o fF i g 1 表3 图1 的启发式计算初图 4 4 算法的复杂度 根据前面的分析，设冲突类的个数为删，约束平均涉及的约束节点个数为七，则候选修复的个数最多为m ( k 2 + 2 k ) 一般情况下，k 的值不会太大，因此可以认为k 2 + 2 k 是一个整数常量K 取得最坏值的情况是，当所有的约 束都是置等类约束，且约束节点的个数为时，根据启发式算法，计算所有候选修复的时间代价为r e N , 为所初 始化数组a 并计算代价w t 的时间消耗最坏在( m ) 2 而后的循环过程中，因为共需覆盖朋个冲突类，所以循环 的趟数用，而候选修复可能覆盖多冲突类，故每次循环需比较的R C 样本空间都比上次少a 值修改也只针对部 分样本，整个循环后需重新计算a ( m x N 行、所列) ，代价是m 2 修改a 的同时就能修改代价w t ，也能决定是否 删除该样本，但还需一遍遍历R C 集，找出代价最小的元素，并拿它和F R e p a i r 堆栈中的其他“ 比较假设F R e p a i r 是爱华等：基于代价模型的 一致几数据修复启度式计算 和R C 中的元素个数始终取最大值m 和m x l V , 则时间代价为m x m x N + m x m 因此，整个算法的时问复杂度为m x N + ( x 2 + 一x - 2 1 ) ，也就是( + 1 ) 2 m 十帅m ，在冲突类个数的平方缓但如果某节点只涉及一个冲突类，那么 它的候选修复就无须与其他r c 比较，且F R e p a w 中的元素是不断增加的，而R c 中的元素不断减少，所以实验的 时间比这里分析的要少 5 实验 实验环境实验使用的计算机的配置如下：I n t e l C o r e 218 G H Z 6 6 7 M H Z 的2 G 内存；1 6 0 G , S M B 缓存的硬盘 操作系统为W i n d o w s X P + S P 2 程序使用c # 编写 我们在真实数据和人造数据上都进行了实验 噪声实验数据中人为加入的错误数据称为噪声噪声比例是错误节点占总节点数的比重实验对人造数据 加入比例不同的噪卢以测试性能而对真实数据，则没有人为添加噪声数据，而是构建若干约束，以致原文档中 一定包含违反它们的不一致数据并以此来a I 试性能 实验数据真实数据来自h t t p ：d b l F n l 叫d e ，x m I 的d b l p I b h t x m l ，文档大小为7 3 4 M B ，实验自定义了4 条 约束( 参见下文) ，对该文档进行修复，修复的过程中没有考虑D T D 造数据则班例I 的数据模式为模式，使用 X M L G e n e r a t o r 分别生成大小不一的X M L 文档，且在数据中加入不同比例的噪声数据，然后根据例l 的5 条约 束进行修复实验首先生成丁噪声比例在3 的5 娄规模不同的数据，其大小分别为1 2 5 K B ，4 9 5 K B ， 1 1 6 8 M B ，4 6 0 4 M B 和1 1 9 8 7 M B ；然后又生成噪声比例不一、大小相似的数据见表4 T a b l e 4O n e g r o u p o f t h e e x p e f i m 即t a l d a t a 表4 宴驰数据配置之一 s i z eo f X M L ( K B ) J4 9 54 9 5 4 9 4 4 9 34 9 1 坠业i 业i 虫曼坐生L j i ! 生生 冲突樊规约算法性蘸我们使用两组实验来衡量冲突类规约算法的时蚓性能：第l 组实验测试了噪声比例 在3 的大小规模不间的5 个X M L 文档上，使用例1 的6 个约束进行冲突类规约的时间消耗，第2 组实验0 测 试丁5 0 0 K 左右的X M L 文档，5 个噪声比例上，使用例1 的6 个约束进行冲楚类规约的时间消耗结果如图2 、 圉3 所示 F i g2 T i m e f o rc o n f l i c t c l a s s w h e n n o i s e i s3 图2 噪声比例为3 时的冲突类规约时间 F i g 3T i m e f o r c o n f l i c tc l a s s f o r5 f 1 0 K B X M L 固35 0 0 K B 左右的原文档的冲突类规约时间 实验结果表明，冲突粪规约所需时问受原文档大小影响更丈，而受噪声比例的影响更小这是因为冲突类规 约耗时在于一遍扫描原X M L 文档、后来的冲突类索引表排序和一遍扫描其中，扫描原文档是最耗时的同样的 噪声比例下，X M L 文档越大，扫描它的时间越长，生成的冲突类索引表的表项越多，对冲突类索引表的排序和扫 描耗时越大，整个耗时也就越= 当然，同样的X M L 文档下，噪卢比例越 ，冲突类会越多，对排序后的冲突粪索引 表处理的时间越长，但原文档的扫描时间不变，忡突粪索引表的表项也不变因为冲突类索引表的表项取决十与 约柬路径匹配的路径数量，所以正如图3 所示，间样丈小的X M L 文档，不同噪声比例下，其冲突类的规约时间差 J o u r n a l o fS o f t w a r e 软件学报V 0 1 2 0 ，N o 4 ，A p r i l2 0 0 9 别也不大 启发式算法的性能为了验证X M L 修复的时间性能，我们也在上述两组数据的基础上分别进行了实验，结 果如图4 、图5 所示实验结果表明，启发式算法的时间消耗与原X M L 文档及噪声比例都有很大的关系事实上， 启发式算法的时间主要与候选修复的多少有关，而候选修复的多少则取决于冲突类的数量和约束的类别同样 噪声比例下，原文档和不一致节点数量基本成正比从图4 可以看出，时间消耗确实在不一致节点的立方以内，如 5 0 0 K 的X M L 文档耗时是1 0 0 K 的6 2 倍，在平方以内；而5 M 的耗时是1 M 的1 0 8 倍，也在平方以内只有1 M 的耗时在5 0 0 K 的耗时的立方以外，这是因为添加噪声数据时，1 M 的噪声节点都是主键约束和函数依赖约束节 点，其候选修复比其他类别的多很多因此，虽然噪声节点是5 0 0 K 的2 倍，但候选修复是其1 0 倍，耗时在立方以 外而同样的X M L 文档，噪声比例增加1 倍，冲突类可能增加2 倍甚至更多因此，图5 中除了3 的时间消耗在 1 的2 7 倍以内，其他耗时都在立方以外但噪声比例和冲突类之间的增长关系受噪声分布和约束类别的影响， 难以给出统一的公式启发式算法的时间消耗基本上在候选修复的平方级别 F i g 4 T i m ef o rr e p a i r c o m p u t ew h e n n o i s e i s3 图4 噪声比例为3 时的修复计算时间 F i g 5 T i m e f o rr e p a i rc o m p u t ew h e n X M L a b o u t5 0 0 K B 图55 0 0 K B 左右的原文档的修复计算时间 真实数据上的结果我们在真实数据上也做了上述3 方面实验，实验中的4 条约束为： ( 1 ) 一个d b l p b h t 内，c i t e 的k e y 能够唯一决定该c i t e ，O P ( d b l p b h t ，c i t e ，( 七钞) ) ( k 1 I x 2 】= 拟11 可2 ) ； ( 2 ) 整个文档范围内f o o t e r 的n a m e 不能为空，B P ( e , d b l p b h t f o o t e r ，( 玎口m P ) ) ( M = 瓤! - 阮工) ； ( 3 ) 整个文档范围内，k e y 值相同的c i t e 具有相同的s t y l e ，即( e , d b l p b h t c i t e ，( k e y ， s 耖跆) ) ( h l 】B 加】j y I = Y 2 ) ； ( 4 ) 整个文档范围内，b h t 的k e y 能够唯一决定该b h t ，n P ( d b l p b h t ，( I i 叫) ) ( 扛I I x 2 】= 瓤l ! 可2 ) 在这4 条约束下，不一致节点有近5 万个，而实验结果( 见表5 ) 表明，其时间消耗仍能接受 T a b l e5 R e p a i r c o m p u t i n g p e r f o r m a n c e o fd b l p _ b h t x m l 表5 面加b h t x m l 上的修复性能 ! i 坐! ! ! ! ! ! ! ! i 垡! ! 箜! ! ! 堡P ! ! ! g f 韭! ! 堡! 坐! ! ! 卫! ! ! ! ! ! g ! 塑! ! 婴【盟 6 总结和未来工作展望 求解不一致X M L 文档修复的复杂度大、耗时高，但在实际应用中又非常必要本文提出一种启发式算法， 可在多项式时间内找到X M L 文档的一个修复具体来说，本文的贡献在于： 提出了适合X M L 文档修复的基于代价模犁的启发式算法： 提出了适合X M L 的代价模型，给出了节点修改、节点删除、节点插入、子树删除和子树插入的代价 公式： 能够同时解决置等和置不等约束： 扩展了冲突类的概念和冲突类索引表，并给出了使用冲突类表检索X M L 文档中所有冲突类的算法 吴爱华等：基于代价模型的不一致X M L 数据修复启发式计算 实验结果表明本文的启发式计算方法确实有效 如何在X M L 的完整性约束和结构性约束( 比如D T D ) 下展开修复求解，是我们下一步工作之一 R e f e r e n c e s ： 【l 】A r e n a sM ，B e r t o s s iL E ，C h o m i c k i J C o n s i s t e n t q u e r y a n s w e l “ Si ni n c o n s i s t e n td a t a b a s e s I n ：P r o c o ft h e 1 8 t hA C M S y m p 0 1 1 P O D S P h i l a d e l p h i a ：A C M ，1 9 9 9 6 8 7 9 【2 】 【3 】 【4 】 【5 】 【6 】 【7 】 【8 】 【9 】 1 0 】 B e r t o a s i L 。B r a v oL ，F r a n c o n iE ，L o p a t e n k oA C o m p l e x i t y a n da p p r o x i m a t i o no ff i x i n gn u m e r i c a la t t r i b u t e s i n d a t a b a s e su n d e r i n t e g r i t yc o n s t r a i n t s I n ：P r o c o f t h e l O t h I n t lS y m p O nD a t a b a s e P r o g r a m m i n gL a n g u a g e s L N C S3 7 7 4 ，S p r i n g e r - V e r l a g ，2 0 0 5 2 6 2 - 2 7 8 A n d r i t s o s P 。F u x m a nA ，M i l l e r R J C l e a na n s w e r so v e rd i r t yd a t a b a s e s ：A p r o b a b i l i s t i ca p p r o a c h I n ：P r o c o f t h e 2 2 n dI n t l C o n f o nD a t aE n g i n e e r i n g ( I C D E 2 0 0 6 ) A t l a n t a ：I E E EC o m p u t e rS o c i e t y ，2 0 0 6 3 0 B o h a n n o nP ，F a nW F ，F l a s t e rM Ac o s t - b a s e dm o d e la n de f f e c t i v eh e u r i s t i cf o rr e p a i r i n gc o n s t r a i n t s b yv a l u em o d i f i c a t i o n I n ： P r o c o f t h eA C MS I G M O DI n t l C o n o n M a n a g e m e n t o f D a t a B a l t i m o r e ：A C M 2 0 0 5 1 4 3 - 1 5 4 L o p a t e n k oA ，B e r t o s s iL C o m p l e x i t y o fc o n s i s t e n tq u e r ya n s w e r i n gi nd a t a b a s e su n d e r c a r d i n a l i t y - b a s e d a n d i n c r e m e n t a lr e p a i r s e m a n t i c s I n ：P r o c o f t h e ll t hI n t lC o n f o f D a t a b a s e T h e o r y L N C S4 3 5 3 ，B a r c e l o n a ：S p r i n g e r - V e r l a g ，2 0 0 7 1 7 9 - 1 9 3 L o p a t e n k oA ，B r a v o L E f f i c i e n ta p p r o x i m a t i o n a l g o r i t h m s f o rr e p a i r i n gi n c o n s i s t e n td a t a b a s e s I n ：P r o c o f t h e2 3 r d I n t l C o n f o n D a t aE n g i n e e r i n g ( I C D E 2 0 0 7 ) I s t a n b u l ：I E E EC o m p u t e rS o c i e t y ，2 0 0 7 2 1 6 - 2 2 5 C h e nY ，D a v i d s o nS B ，Z h e n gY F X K v a l i d a t o r ：Ac o n s t r a i n tv a l i d a t o rf o rX M L I n ：P r o c o ft h e 2 0 0 2A C MC I K MI n t l C o n f 0 1 1 I n f o r m a t i o na n dK n o w l e d g e M a n a g e m e n t M c L e a n ：A C M 2 0 0 2 4 4 6 4 5 2 T a nZ J ，Z h a n g 7 _ 3 ，W a n gW ，S h iB L C o n s i s t e n t d a t af o r i n c o n s i s t e n t X M Ld o c u m e n t I n f o r m a t i o n S o f t w a r e T e c h n o l o g y ，2 0 0 7 ， 4 9 ( 9 - 1 0 ) ：9 4 7 - 9 5 9 A r e n a sM ，L i b k i nL X M L