A Logical Formalisation of the Fellegi-Holt Method of Data Cleaning

Abstract

The Fellegi-Holt method automatically "corrects" data that fail some predefined requirements. Computer implementations of the method were used in many national statistics agencies but are less used now because they are slow. We recast the method in prepositional logic, and show that many of its results are well-known results in prepositional logic. In particular we show that the Fellegi-Holt method of "edit generation" is essentially the same as a technique for automating logical deduction called resolution. Since modern implementations of resolution are capable of handling large problems efficiently, they might lead to more efficient implementations of the Fellegi-Holt method.