Since you want it done "on the fly" (without having to send multiple requests back to the server saying "whatdoIdonow?"), it will have to be done on the client, in Javascript.
It's a bit much to explain in detail how to make one here, but there are a number of such dynamically-repopulated cascading menus available on sites devoted to Javascript coding.
What you would need to do when you get one is to modify it so that, wherever it defines the contents of the various menus, you insert the PHP code that writes out what the contents should be (as specified in the database). Since Javascript embedded in a page is just as much ordinary text as the HTML, PHP will write one as happily as it writes the other. The intention being that when the page is finally sent to the browser, the Javascript contains exactly the contents needed for the menus to do what you want them to do.
If the database contents don't change often, you might consider keeping this Javascript in a seperate .js file, which needs to be updated only when the contents of the database do change. Just to save the server a bit of work.
