Data dependent tests

I'm writing test for my "MySQL Requests Manager" and the problem is that some of the tests is dependent on the data that contained in the database. So if any other test will delete the required records or someone else will delete them, that means that test will fail even if they correct.

I'm thinking about two approaches here: 1. In the test itself backup all the needed data before, run the test and restore the data from backup. But this is much more error prone and "heavier", in my humble opinion. 2. Before running one of the tests or even all of them is to create whole new database with structure and required data (from previously made dump, i think). This involves only around of two 'global' actions: create database and dropping it. Of course, i need to have totally isolated MySQL user and database for this.

What you think and what can you recommend? How another programmers dealing with that kind of issue? Thank you in advance.