Rsa97

Переходите в дереве от Adjacency LIst к Nested Set или Materialized Path.
И тот и другой вариант позволяют быстро выбрать все дочерние узлы дерева на полную глубину.

Делать всё в транзакции. Сначала заносить данные, при этом контролировать на возникновение циклов. Затем рекурсивно пересчитывать атрибут empty для всех записей. И только после этого завершать транзакцию.