基于代价模型的不一致XML数据修复启发式计算

• 作者: 吴爱华 汪卫 王先胜 谈子敬
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 不一致性 不一致数据 修复 一致的查询回答 XML数据清洗 不完整数据库
• 年，卷（期）: 2009,（4）
• 所属期刊栏目: 数据库技术
• 页码范围: 918-929
• 页数: 12页
• 分类号: TP311
• 字数: 11978字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2009.03225

摘要

在实际应用中,为不一致的XML文档计算最优修复意义重大.但求解最优修复是一个NP完全问题,特别是在XML文档同时违反函数依赖约束和主键约束时.提出一个基于代价模型的、可以在多项式时间内完成的启发式修复求解算法.该算法首先借助索引表,在一遍扫描原始XML文档的情况下寻找不一致数据集,然后为每一类约束的不一致数据集构造候选修复,同时计算其修复代价,最后启发式地求解一个代价最小的修复方案.实验结果表明,该算法的时间复杂度不超过冲突类的3次方,即便是在不一致数据量很大,噪声比例很大以及涉及多类语义约束时,也能较快地完成修复.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谈子敬	复旦大学计算机信息与技术系	15	229	6.0	15.0
2	吴爱华	复旦大学计算机信息与技术系	25	91	6.0	8.0
4	汪卫	复旦大学计算机信息与技术系	100	1152	16.0	29.0
7	王先胜	复旦大学计算机信息与技术系	1	6	1.0	1.0