DELETE de múltiples entradas en distintas tablas

[quimfv]

No se puede construir una sola query que haga lo que pides, se podría como bien sabes si dispusiéramos del ON DELETE CASCADE, solo con borrar las categorías se borraría todo lo demás....

La solución del stored, procedimiento almacenado, consiste en que programas una pequeña rutina que ejecute las querys una detrás de la otra para conseguir lo buscado, lo que te propone @gnzsoloyo es que antes de borrar guardes los datos en tablas temporales para poder recuperarlos si una de las querys falla, restaurando así la situación, como si dispusiéramos de TRANSACCIONES.

Se llama "procedimiento almacenado" por que se programa con lenguaje propio del servidor de bases de datos, tienes dos opciones aprender el lenguaje y programar el procedimiento, o usar un lenguaje externo para programar un procedimiento que haga lo mismo solo que no será stored (almacenado).