Protecting database integrity has become a matter of increasing importance nowadays as accessing information is getting easier. Therefore, database watermarking approach to protect the integrity become an active research area. Most of the existing relational database watermarking techniques embed a generated watermark in the database. Zero watermarking is employed in the proposed technique by storing the watermark generated from the database in another medium independent from the database. In order to make the method robust to column replacement attacks, cell values are split into overlapping pairs and column number is added to pairs. The histogram of pairs is used as the watermark because any change in either a cell value or column replacement would affect the histogram. Experimental results indicate robustness to column replacement attack as well as improved processing time compared to other works reported in the literature.