This paper proposes an efficient authentication scheme with fault tolerance for database systems. The proposed scheme significantly reduces the total overhead by sharing an innovative checksum for the purposes of both locating the error position and serving as a digital signature. The proposed authentication scheme can check the data integrity of a record and ensure the non-repudiation of a record digitally signed by a sender. The proposed scheme is able to correct a single error within each record and is ideal for many database applications in which both authentication and fault tolerance are required.