This paper presents a new watermarking method for protecting non-numerical databases. The proposed watermarking system allows the data owner to define a similarity function in order to reduce the distortion caused by watermark embedding while, at the same time, reducing the number of element modifications needed by the embedding process. A mathematical analysis is provided to justify the robustness of the mark against different types of malicious attacks. The usefulness of this extensible and robust method is illustrated by describing some application domains and examples.