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

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

A Cost-Based Heuristic Algorithm for Repairing Inconsistent XML Document

Computing a repair for inconsistent XML documents is significant in applications. But getting an optimum repair is a NP complete problem, especially when XML documents violate both the function dependence and the key constraints. This paper proposes a cost-based heuristic algorithm, which can find a repair with the lowest cost in polynomial time. It first scans the original XML documents once to get the inconsistent data. Then it computes the general candidate repairs for each inconsistent data, and gets a whole document repair heuristicallybased on its cost. The experimental evaluation show that even when XML documents are large, with high percent of dirty elements, and against many different constraints, the algorithm can still run in less than O(n3) w.r.t. the size of inconsistent elements.