The importance of watermarking digital databases has increased by leaps and bounds due to the high vulnerability of digital assets to piracy attempts when they traverse through the internet. To deter piracy, we propose a robust watermarking scheme for relational databases containing categorical data that resolves ownership issues. We propose a three-level security strategy. Firstly, the watermark is itself made secure using playfair cryptographic algorithm. Secondly, the database is securely partitioned using a primary key independent hash partitioning technique. This step virtually reorders the tuples before embedding. Thirdly, we entail a secret key based embedding process to ensure security. Linear feedback shift registers are implemented to generate pseudorandom numbers which selects different watermark bit index for each partition. The process of embedding does not produce any distortion in the database. Hence it is suitable for databases with categorical attributes containing sensitive information that cannot tolerate perturbations. Each watermark bit is embedded multiple times into different partitions. This makes the scheme highly robust against various attacks. The technique is proved by experimentally, and by theoretical analysis to be extremely robust. Experimental results show that it is 400 per cent resilient to subset addition attack, 100 per cent resilient to subset alteration attack, and 96 per cent resilient to tuple deletion attack. We prove analytically the resilience of the proposed technique against invertibility and additive attacks.