I'm not a database expert, but concurrent delete from table doesn't sound like something what should cause deadlock, it this simple situation. So its seems to me that the problem is more in database schema (for example oracle db is acquiring full table lock instead of row lock when there is missing index on FK).