This paper proposes a systematic approach to integrate database security (including database encryption and authentication) and fault tolerance so that the total overheads can be significantly reduced. An improved database encryption scheme with a consideration of fault tolerance are also presented and analyzed. The authentication and fault tolerance are realized by carefully designed checksums using redundant residue number systems (RRNS). The proposed authentication approach can not only check the data integrity of a record, but also ensure the data origin of a record in database systems. The integrated approach is able to correct a single error within each record. The proposed approach is ideal for many database applications in which both authentication and fault tolerance are required.