Per tutte le tue esigenze dovresti prendere questa struttura
CREATE TABLE `menus` (
`id` int(11) unsigned NOT NULL AUTO_INCREMENT,
`parent_id` int(11) unsigned DEFAULT NULL,
`label` varchar(255) NOT NULL DEFAULT '',
PRIMARY KEY (`id`),
KEY `fk_parent_menu` (`parent_id`),
CONSTRAINT `fk_parent_menu` FOREIGN KEY (`parent_id`)
REFERENCES `menus` (`id`) ON DELETE CASCADE ON UPDATE CASCADE
);
La demo mostra l'inserimento e l'eliminazione di un nodo padre
La parte magica per tutti i bambini viene eseguita da ON DELETE CASCADE