rocknbil - 1:02 am on Jun 30, 2010 (gmt 0)
The mysql queries are executed each time the page is requested. PHP is not like a static page, only it's output is cached in the browser.
You'll only see a difference if your site is extremely busy, or the server goes down or slows down. I really can't say between the three which would be "faster," but most likely of all is that the difference will be marginal. Of course if you lose a connection to mysql, you lose your navigation.
I guess more of a consideration is the resources you're using. If your navigation gets set up once, and only modified every now and then, you'll be using less resources by writing out an include at the time you modify it. And I mean a static file, not a php file, just write out nav.html or nav.txt and include that via SSI for semi static pages or as a php include. Then if your site gets busy, that's one less hit on the mysql server, one less byte or two of memory PHP is using to load the nav.