As long as the host in question has cpanel or any other type of interface that includes MySQL, then I'm sure it wouldn't be a problem. Almost all hosting providers include at least an integrated SQL interface.
Virtual hosting is the process of hosting multiple domains on single server. Thus, Most of the host supports MySQL database. You can select according to your requirements. There exists different type of host for request routing such as IP address, so which suits you best that can be highly recommendable to you.