Corrupt Database

I just tried installing the WP updates on the weekend and got a message that the system was down for maintenance! When I got in next, pages, post and links seem to have disappeared. I contacted my web host to find out they did not do daily backups, but only random weekly ones. I had them restore the June 7th backup and discovered problems with it. They say the database is corrupt and they have no other backups. I can redo the links, pages and posts, but I need to know I am working on a firm foundation or how to get there! The other thing I need to know is a good backup program that will send me the backups.

Any ideas?