The key dependencies are (a) within qa_posts between a post and its parent (as specified by parentid), (b) between a post and its votes in qa_uservotes, (c) between a post and its index entries in qa_titlewords, qa_contentwords, qa_tagwords (from 1.4 dev preview), qa_posttags.
All these dependencies should be taken care of by foreign keys - (b) and (c) with automatic cascading on delete, and (a) by a constraint on removal. So just ensure that before you delete a post, you delete any posts for which it is the parent.
After doing this, click all the 'recalculate/reindex' buttons on the 'Stats' page of the Admin panel, so that all counts, etc..., in the database are updated.
BTW, you might find it easier just to use the high-level functions in qa-app-posts.php, introduced in 1.4 beta 1, which take care of everything for you.