In this paper, we present an efficient failure recovery scheme for mobile database applications based on movement-based checkpointing and logging. Current approaches take checkpoints periodically without regard to the mobility behavior of mobile users. Our movement-based checkpointing scheme takes a checkpoint only after a threshold of mobility handoffs has been exceeded. The optimal threshold is governed by the failure rate, log arrival rate, and the mobility rate of the mobile host. This allows the tuning of the checkpointing rate on a per-user basis. We identify the optimal movement threshold which will minimize the recovery cost per failure as a function of the mobile node's mobility rate, failure rate and log arrival rate. We derive the mobile database application recoverability, i.e., the probability that the recovery can be done by a specified recovery time deadline. Numeric data are presented to demonstrate the feasibility of our approach with its applicability given.