The SQLite databases on Android are Auto-vacuum enabled by default, so the yields of recovered data directly from the database file itself can be a little disappointing in a lot of circumstances. That being said, if you can obtain an image of the flash chip (either by using a tool like Cellebrite if the device is supported, rooting and netcat/dd-ing or JTAGing) the possibility of getting deleted records back is far higher; indeed we've had a lot of success working this way (using Epilog to do the recovery).
The SQLite file format is very well documented and there are some really good resources out there discussing how this can be abused to recover deleted records for example Richard Drinkwater's write up of the record structure. I've also recently written up some information about the Write Ahead Log (a SQLite journalling system now in wide use) and how you can use it to recover additional data (and what pitfalls you may encounter if you don't understand how it works).
Hope that's of use to you.
