In this paper, we present a new robust and reversible watermarking approach for the protection of relational databases. Our approach is based on the idea of difference expansion and utilizes genetic algorithm (GA) to improve watermark capacity and reduce distortion. The proposed approach is reversible and therefore, distortion introduced after watermark insertion can be fully restored. Using GA, different attributes are explored to meet the optimal criteria rather than selecting less effective attributes for watermark insertion. Checking only the distortion tolerance of two attributes for a selected tuple may not be useful for watermark capacity and distortion therefore, distortion tolerance of different attributes are explored. Distortion caused by difference expansion can help an attacker to predict watermarked attribute. Thus, we have incorporated tuple and attribute-wise distortion in the fitness function of GA, making it tough for an attacker to predict watermarked attribute. From experimental analysis, it is concluded that the proposed technique provides improved capacity and reduced distortion compared to existing approaches. Problem of false positives and change in attribute order at detection side is also resolved. Additionally, the proposed technique is resilient against a wide range of attacks such as addition, deletion, sorting, bit flipping, tuple-wise-multifaceted, attribute-wise-multifaceted, and additive attacks.