CAJ | 학술논문

在实际应用中,为不一致的XML文档计算最优修复意义重大.但求解最优修复是一个NP完全问题,特别是在XML文档同时违反函数依赖约束和主键约束时.提出一个基于代价模型的、可以在多项式时间内完成的启发式修复求解算法.该算法首先借助索引表,在一遍扫描原始XML文档的情况下寻找不一致数据集,然后为每一类约束的不一致数据集构造候选修复,同时计算其修复代价,最后启发式地求解一个代价最小的修复方案.实验结果表明,该算法的时间复杂度不超过冲突类的3次方,即便是在不一致数据量很大,噪声比例很大以及涉及多类语义约束时,也能较快地完成修复.
재실제응용중,위불일치적XML문당계산최우수복의의중대.단구해최우수복시일개NP완전문제,특별시재XML문당동시위반함수의뢰약속화주건약속시.제출일개기우대개모형적、가이재다항식시간내완성적계발식수복구해산법.해산법수선차조색인표,재일편소묘원시XML문당적정황하심조불일치수거집,연후위매일류약속적불일치수거집구조후선수복,동시계산기수복대개,최후계발식지구해일개대개최소적수복방안.실험결과표명,해산법적시간복잡도불초과충돌류적3차방,즉편시재불일치수거량흔대,조성비례흔대이급섭급다류어의약속시,야능교쾌지완성수복.