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