Hola Escoffie
Para evitar esos problemas, y mantener la integridad de la base de datos, se usan las constraints.
No conozco mySQL (uso Oracle) pero estoy seguro que deben existir las constraints.
Tenés que crear una clave primaria en puesto (id) y luego habilitar una constraint referential desde empleado(puestoId) a Puesto(Id).
De ese modo la base no te permitirá borrar un puesto mientras exitan empleados asignados al mismo, ni asignar un empleado a un puesto inexistente.
Espero que te sea de utilidad
