With advanced information techniques, organizations want to make their database public for different purposes. It is important to do some data transformations that pre- vent private information to be revealed before publishing the database. In this paper, we introduce a combined ap- proach to enhance the privacy of the databases to be re- leased. The combination of two existing techniques, k- anonymity and randomization, provides better privacy pro- tection than only applying one of two approaches and still reserves certain data utility. The experiments on real-world dataset show that our privacy breach prevention algorithm enhances the privacy with small cost increase compared to the k-anonymity approach.