Watermarking has been applied to protect relational databases from illegal copying and manipulation by attackers. Many watermarking schemes for relational database have been proposed, and these schemes both rely on the actual primary key. Therefore, the watermark cannot be embedded into relational database, if there is not existence of actual primary key. In this paper, we present a new reversible watermarking scheme for textual relational database without depending on the actual primary key. The proposed scheme constructs a virtual primary key from the content of some selected textual attributes. Based on the generated virtual primary key, the watermark is embedded into the textual relational database. Experimental results showed that the proposed scheme achieves strong robustness under a variety of possible attacks, e.g., sorting, deletion, modification, and addition attacks. In addition, in comparisons with three previous schemes, the proposed scheme was more secure and robust, as evidenced by our experimental results and robustness analysis.