Как составить запрос на удаление строк из двух таблиц в MySQL?
Как вариант:
START TRANSACTION;
delete from gift_certificate_to_tag_relation where gift_certificate_id = 1;
delete from gift_certificate where id = 1;
COMMIT;

MySQL fiddle
В свойствах внешнего ключа установите ON DELETE CASCADE. После этого дочерние записи будут удаляться автоматически при удалении родительской.