Abstract: Today cloud computing infrastructure is largely being deployed in healthcare to access various healthcare services easily over the Internet on an as needed basis. The main advantage of healthcare cloud is that it can be used as a tool for patients, medical professionals and insurance providers, to query and coordinate among medical departments, organizations and other healthcare related hubs. Although healthcare cloud services can enable better medication process with high responsiveness, but the privacy and other requirements of the patients need to be ensured in the process. Patients medical data may be required by the medical professionals, hospitals, diagnostic centers for analysis and diagnosis. However, data privacy and service quality cannot be compromised. In other words, there may exist various service providers corresponding to a specific healthcare service. The main challenge is to find the appropriate providers that comply best with patients requirement. In this paper, we propose a query based optimal medication framework to support the patients healthcare service accessibility comprehensively with considerable response time. The framework accepts related healthcare queries in natural language through a comprehensive user-interface and then processes the input query through a first order logic based evaluation engine and finds all possible services satisfying the requirements. First order logic is used for modeling of user requirements and queries. The query evaluation engine is built using zChaff, a Boolean logic satisfiability solver. The efficacy and usability of the framework is evaluated with initial case studies on synthetic and real life healthcare cloud.