In a distributed mobile e-health care system, e-health service providers exchange data on the fly in response to user queries without any centralized control. Local databases in e-health service providers might be intercepted during the exchange of data and read by intruders; and malicious transactions may damage data that is highly confidential. In this case any centralized control for securing data cannot be assumed to protect confidential data. Therefore, securing health information from malicious attacks has become a major concern. Although prevention techniques are available, the history of system break-ins guarantees that there is no foolproof technique that totally eliminates security loopholes in a computer system. Hence, efficient damage assessment and recovery techniques are needed. Traditional methods require scanning the entire log from the point of attack to the end which is a slow procedure. In this paper, we present an efficient damage assessment and recovery algorithm to recover the database from malicious transactions. The algorithm is based on data dependency and uses a single matrix. The results of this work prove that our algorithm performs better than the other algorithms in both the damage assessment and the recovery stages.