不整合なデータベースを修復するための効率的な近似アルゴリズム

私たちは、整合性制約のセットに関して不整合なデータベースを数値値の更新によって修復する問題を考察します。特に、数値的な組み込み述語を持つ否定整合性制約に集中します。現在まで、この文脈での研究は計算複雑性分析に集中しています。本論文では、データベースの修復を得るための効率的な近似アルゴリズムに焦点を当て、データベースのサイズに関してO(n log n)で動作するアルゴリズムを提示します。実験評価の結果、大規模なデータベースにおいても、正確な問題が計算上困難であるにもかかわらず、データベースの近似修復を効率的に計算できることを示しています。最後に、タプル削除の最小数によって得られたデータベースの修復にも私たちの結果が適用できることを示します。