Among the challenges of multimedia and mobile computing, providing a mechanism for data retrieval in multimedia databases under wireless mobile environments is one of the most difficult issues (Shih, 2001). Up to now, the fundamental technologies that are specialized for wireless mobile, multimedia environments are not mature in object-oriented, object-relational, as well as relational databases (Hillborg, 2002; Ramakrishnan & Gehrke, 2003; Watson, 2004). An important issue is how to ensure quick query response for the users. If a user found out that the retrieved multimedia object is neither interesting nor useful after it is displayed, then the time and bandwidth used for transmitting the multimedia objects have already been wasted. In order to save precious time and expensive bandwidth, it could be a good idea to let users browse objects at an acceptable resolution without paying much attention to the details or at the limited device display capability. This article presents a novel concept to deal with this problem by making use the concept of quality of service (QoS) to achieve adaptive query processing. In general, traditional QoS management is defined as the necessary supervision and control to ensure that the desired quality of service properties are attained and sustained, which applies both to continuous media interactions and to discrete interactions (Chalmers & Sloman, 1999). QoS thus consists of a set of specific requirements for a particular service provided by a network to users. However, little work has been done in extending QoS principles to multimedia data management in wireless network environments.