A qualitative and quantitative comparative study of VPK schemes for relational data watermarking

In relational data watermarking, several virtual primary key (VPK) schemes have been proposed to address threats such as primary key (PK) deletion. These schemes face significant challenges and are often evaluated under heterogeneous assumptions and criteria. This paper provides a systematic qualitative and quantitative evaluation of existing VPK schemes, as well as alternative solutions that avoid relying on PKs for watermark synchronization. We standardize notation and terminology, organize the design space according to VPK generation and management strategies, and compare major scheme families using consistent criteria covering duplication behavior, deletion resilience, attribute involvement, and computational overhead. The analysis highlights progress achieved, remaining limitations, and open research challenges. Finally, the paper distills practical selection guidelines for PK-unavailable data-sharing and processing pipelines and motivates future work on realistic threat models and reproducible benchmarks.