Searching for some of the data stored in the database is the easier way to detect a data leak. You can also search for events caused by the data leak (some transactions in a credit card, or some email receiving spam, for example).
To make this easier, you can:
- Add dummy records to the database. You can tag them (or not) as fake so the application doesn't use them. They can be created by the application or they can be entered manually. They can be a few or a lot.
- Watermark the records in the database. Adding or changing some data on some (or all) records (real or fake) regularly (for example, weekly), so that if you discover a record in the wild, you'll know when happened.
- For exporting operations (if your application includes export or backup functions or even full-listing reports) you can add fingerprints to the data. Those are one-time items (strings added to some columns, whole columns or whole records) added on-the-fly for that user only for that time only, so that you can discover a traitor (a legitimate user with access to the data who then leaked it).
For example, let's say your application creates a dummy record per-thousand of real records, and each record has an email address. Also, your application appends a fake surname to random records using a list of fake surnames (Obviously your application should ignore them when found at the expected string position). To simplify, let's say you have a bunch of domains with catch-all email accounts. Your application changes the email addresses of those dummy records monthly, using your domains. You monitor those email addresses and you do automated web searches to find the content of those dummy records. If you find the names and email addresses on the web or receive spam in any of those addresses, you'll know the data has been leaked.
(You should be really careful when using a search engine if you feed real customers/patient/whatever data, as you may be breaching some privacy laws, but if the data is fake, or real but yours then it's ok).
If you have enough resources, you can also request real credit/debit cards, include them in your dummy records and then monitor any activity on them.
This is for detecting a full data breach (the attacker have the whole database).
For smaller data leaks (from some employee getting some information from some records) the solution would be different. Adding the fingerprints to the data would be more useful.
Personally, I have implemented the fingerprinting for several applications (as there were multiple administrators, all having access to the whole database from the application), and adding dummy records to a couple of applications with customer data (however I don't do the monitoring, I hope my clients are doing it).