This paper describes QEF a query evaluation framework designed to support complex applications on the grid. QEF has been extended to support querying within a number of different applications, including supporting scientific visualization and implementing a web service semantic search engine. Application requests take a form of a workflow in which tasks are represented as algebraic operators and specific data types are enveloped into a common tuple structure. The implemented system is automatically deployed into schedule grid nodes and autonomously manages query evaluation according to grid environment conditions. The generality of our approach has been tested with a number of applications leading to a full grid web service implementation available at http://codims.epfl.ch