With the increase of dirty data, data cleaning turns into a crux of data analysis. The accuracy limitation of the existing integrity constraints-based cleaning approaches results from insufficient rules. In this paper, we present a novel hybrid data cleaning framework on top of Markov logic networks (MLNs), termed as <inline-formula><tex-math notation="LaTeX">${\sf MLNClean}$</tex-math><alternatives><mml:math><mml:mi mathvariant="sans-serif">MLNClean</mml:mi></mml:math><inline-graphic xlink:href="gao-ieq1-3012472.gif"/></alternatives></inline-formula>, which is capable of learning instantiated rules to supplement the insufficient integrity constraints. <inline-formula><tex-math notation="LaTeX">${\sf MLNClean}$</tex-math><alternatives><mml:math><mml:mi mathvariant="sans-serif">MLNClean</mml:mi></mml:math><inline-graphic xlink:href="gao-ieq2-3012472.gif"/></alternatives></inline-formula> consists of two steps, i.e., <italic>pre-processing</italic> and <italic>two-stage data cleaning</italic>. In the pre-processing step, <inline-formula><tex-math notation="LaTeX">${\sf MLNClean}$</tex-math><alternatives><mml:math><mml:mi mathvariant="sans-serif">MLNClean</mml:mi></mml:math><inline-graphic xlink:href="gao-ieq3-3012472.gif"/></alternatives></inline-formula> first infers a set of probable instantiated rules according to MLNs and then builds a two-layer MLN index structure to generate multiple data versions and facilitate the cleaning process. In the two-stage data cleaning step, <inline-formula><tex-math notation="LaTeX">${\sf MLNClean}$</tex-math><alternatives><mml:math><mml:mi mathvariant="sans-serif">MLNClean</mml:mi></mml:math><inline-graphic xlink:href="gao-ieq4-3012472.gif"/></alternatives></inline-formula> first presents a concept of <italic>reliability score</italic> to clean errors within each data version separately, and afterward eliminates the conflict values among different data version using a novel concept of <italic>fusion score</italic>. Considerable experimental results on both real and synthetic scenarios demonstrate the effectiveness of <inline-formula><tex-math notation="LaTeX">${\sf MLNClean}$</tex-math><alternatives><mml:math><mml:mi mathvariant="sans-serif">MLNClean</mml:mi></mml:math><inline-graphic xlink:href="gao-ieq5-3012472.gif"/></alternatives></inline-formula> in practice.