M-commerce applications have evolved out of e-commerce applications, riding on the rapid advancement in mobile communication technologies in the past decade. The diffusion of applications on the Internet into the mobile computing environment has taken an accelerating pace ever since. Virtually all e-commerce and m-commerce applications rely on the provision of information retrieval and processing capability. In this regard, database systems serve as the information source and repository for these applications, backed by efficient indexing mechanism. Bean (2003) gave a good report on supporting Web-based e-commerce with XML, which could be easily extended to m-commerce. An m-commerce framework, based on JINI/XML and a workflow engine, was also defined by Shih and Shim (2002). Customers can receive m-commerce services through the use of mobile devices, such as pocket PCs, PDAs, or even smart phones. These mobile devices together with their users are often modeled as mobile clients. Central to supporting m-commerce applications are three types of entities: mobile device, mobile communication, and database. In particular, we are more interested in providing efficient access mechanisms to mobile-client-enabled database servers, which are often called mobile databases. Mobile databases contain the core information to support the underlying m-commerce applications, while the use of mobile devices serves for the hardware platform, with mobile communication providing the necessary connection between mobile databases and mobile devices for interfacing with real users or customers.