Jak rekursywnie usuwać elementy z tabeli?

Z tym modelem jest to niemożliwe

1. Zamiast roota użyj NULL, więc możesz użyć klucza obcego InnoDB + Cascade Delete.
2. Zamiast używać string parent_key, użyj identyfikatora (np. sun =1, moon =2 )

Innym sposobem jest zmiana modelu danych, dzięki czemu możesz łatwo wybrać dowolne potomstwo elementu - zobacz na przykład http://www.sitepoint.com/hierarchical-data-database-2/