The pragmatic answer is to just ask the data subject what they would like to have erased.
The GDPR's right to erasure DOES NOT requires that you “delete all their records in [your] database”. Compared to other GDPR rights, it has a quite limited scope. It is necessary that one ground for erasure in Art 17(1) applies, and none of the exceptions in Art 17(3) apply. For example, you are allowed to retain any data that you need to fulfill a legal obligation (exception in Art 17(3)(b)), such as an obligation to keep financial records for a number of years.
In the case of providing course completion certificates, I would assume that your legal basis for providing this service is a contract with the data subject. Contracts directly with the data subject can serve as a legal basis for processing per Art 6(1)(b). It doesn't matter if the contract was paid (consideration is not a necessary element of a contract in civil law systems).
As long as this contract is in force, there are no Art 17(1) grounds for erasure. But if the contract is terminated, Art 17(1)(a) would apply: “the personal data are no longer necessary in relation to the purposes for which they were collected or otherwise processed”. So the data subject could release you from your contractual obligation to provide the certificate verification service, and then require you to delete any personal data in connection with that service.
In the unlikely case that you are using a different legal basis for hosting the certificate service:
||grounds for deletion
|Art 6(1)(a) consent
||Art 17(1)(b): consent can always be withdrawn
|Art 6(1)(b) contract
||yes (see discussion)
||when the contract is terminated
|Art 6(1)(c) legal obligation
||per legal requirements
|Art 6(1)(d) vital interests
|Art 6(1)(e) public interest
||per legal requirements
|Art 6(1)(f) legitimate interest
||Art 17(1)(c): objection to further processing per Art 21(2)
For all of these legal bases, it is the case that once the legal basis expires, then Art 17(1)(a) provides grounds for erasure. In fact, proactive erasure (without waiting for a data subject request) may be required in line with the Art 5(1)(b) purpose limitation and Art 5(1)(e) storage limitation principles. To quickly summarize all Art 17(1) grounds for deletion:
- Art 17(1)(a): data is no longer necessary
- Art 17(1)(b): consent withdrawn (only if Art 6(1)(a) consent was used as legal basis)
- Art 17(1)(c): objection to further processing (only if Art 6(1)(f) legitimate interest was used as legal basis)
- Art 17(1)(d): unlawful processing always merits erasure
- Art 17(1)(e): erasure is required by law
- Art 17(1)(f): special right to erasure for children
Note that it is, in principle, possible to provide certificates without storing personal data. This could make it unnecessary to think about data subject rights like erasure. For example, you could provide a certificate to users. The certificate contains personal data, and you do not store a copy of the certificate. But you could use cryptographic signatures to prevent forgery of the certificate. The signature can be verified without having to store personal data. If you are familiar with web development, the same technique is used for JWT tokens: the data in the token is signed by a secret key so that it can be verified whether a token (and the data in the token) was created validly, without having to store a copy of the data in the token. Limitations of this approach are well-known, such as making it difficult or impossible to revoke certificates.
In practice, such data-minimization techniques are overkill. The GDPR only requires appropriate security measures. If you have a legal basis (such as a contractual obligation with the data subject) then it is perfectly fine to store a certificate with personal data in your service. The GDPR obligations stemming from such a processing activity are not particularly onerous.