What is the correct statistical sample size for 500000 database records and how did you determine it?

in the time its taken to ask this question and wait for answers you could have validated the half million records - as a DBA i'm having palpitations that you are happy to risk potentially invalid data in your database - why bother to keep the data if it isn't worth ensuring validity?