Я думаю, что вы можете сделать выборку и выбрать, какую запись вы хотите удалить из этой выборки, что-то вроде
DELETE FROM target WHERE target_table.id IN (
SELECT target_table.id INNER JOIN relation_table ON relation_table.target_table_id = target_table.id
)
где подвыбор, используя INNER JOIN
, вернет записи с отношениями =)
надеюсь, это поможет! =)