@QuAzI, можно еще следующим образом сделать.
Если в запрос передаются вместо paramId и paramParent конкретные значения
INSERT INTO a
SELECT paramId, paramParent FROM a
WHERE a.id = paramParent
Если предполагаемого родителя не найдется (нет такого id, которое равно paramParent), то и никаких изменений не произойдет.
UPD:
Опять же, если есть возможность реализовать алгоритм с помощью хранимой процедуры, то можно в теле процедуры проверять наличие записей по условию с помощью SELECT EXISTS:
DELIMITER $
CREATE PROCEDURE myProc(id int, parent int)
BEGIN
IF (SELECT EXISTS(SELECT * FROM table1 WHERE table1.id = parent)) THEN
INSERT INTO table1 VALUES(id, parent);
END IF;
END $
Если необходимо, то остается только прикрутить проверку на равенство id и parent и проверку на существование id.
Другой вопрос - скорость я не измерял.