Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-05-26
2001-07-31
Alam, Hosain T. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C705S051000, C707S793000, C709S235000, C709S247000, C711S163000, C713S001000, C713S152000, C713S323000
Reexamination Certificate
active
06269374
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to controlling data structure integrity and, more particularly, to calculating checksums for data structures.
2. Background of the Invention
Whenever information is stored and/or transmitted electronically, it is of great importance to control the integrity of the data structure that contains the information. Both during storage and transmission, the data structure is subject to potential influence of errors. The physical devices which store or transmit the information are subject to physical and mechanical failure which in turn can lead to the introduction of errors in the data structure, or potentially a total loss of the information in the data structure.
A particularly important area where the control of data integrity requires powerful means and methods in order to be a critical safeguard against errors is the massive data backups used by financial enterprises such as credit card companies, banks, etc. The vast number of transactions in a day necessitates frequent updating of large data structures, and corresponding data integrity control.
It is possible to control the integrity of the data structures by always keeping a duplicate of the information in the data structure stored in another device. The integrity of the data structure can then always be controlled by comparing the data structure to the ones stored in the duplicate device. Obviously, a great disadvantage of this method is the increased storage capacity that must be accessible instantly upon changing the data structure, and the additional time and computer capacity needed.
Checksums have become a common tool used in controlling the integrity of data structures. Checksums are used in a variety of different areas within information technology. Typically, checksums are used in the following way. An application which handles information in the form of data structures calculates a checksum for a particular data structure. The checksum is calculated using the data stored in the data structure, and thus becomes a mathematical “fingerprint” of the particular data in the data structure. Whenever the application needs to control and confirm the integrity of the data structure, the application calculates the checksum again, using the same method of calculating as was used previously, and then compares the newly calculated checksum with the original checksum which was stored in the data structure. If the integrity of the data structure is intact, the checksums will be identical. Any discrepancy between the two checksums is a clear indication that a data integrity problem has occurred in the data structure. It is noted that checksum calculation is typically “transparent” to users of the data structures, which means that the user is normally not aware of checksum calculations—they are performed without particular inputs or outputs via the user interfaces—unless a data integrity problem is detected, at which the user should be notified or alerted.
The checksum for a data structure must always be updated when modifications of the data in the data structure have taken place. Previously, the updating of the checksum has been carried out in the following way. Before any changes are made in an existing data structure, the application will control and confirm the integrity of the data structure by calculating a checksum and comparing it to a stored checksum, as described above. If the comparison indicates that the integrity is intact, the changes in the data structure can be made. When the data structure has been modified as desired, the application must update the checksum to reflect the data structure including the changed data. The application calculates a new checksum for the modified data structure and stores that checksum in the data structure.
If the modified data structure contains substantially as much information as the original data structure, the second calculation takes approximately as much time to perform as did the first calculation. This approximation is valid regardless of whether a small or large portion of the data were altered during the change and also regardless of whether the data structure includes only a few bytes or several gigabytes.
It can be seen that there is a need for a method and apparatus for updating checksums of data structures that does not recalculate checksum contributions from parts of the data structure that were not changed.
SUMMARY OF THE INVENTION
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a method and apparatus for updating checksums.
The present invention solves the above-described problems by providing a method of updating a checksum of a data structure wherein the checksum has an additive property. The method includes eliminating from a checksum a word value of a word that is to be modified, to form a current checksum. The current checksum is then updated with a modified word value of a modified word, to form an updated checksum.
An article of manufacture in accordance with the principles of the invention includes a computer readable medium having instructions for causing a computer to perform the method of invention.
A system in accordance with the principles of the present invention includes a computer readable and writeable medium comprising at least one data structure, and a processor which performs the method of the invention.
These and various other advantages and features of novelty which characterize the invention are pointed out with particularity in the claims annexed hereto and form a part hereof. However, for a better understanding of the invention, its advantages, and the objects obtained by its use, reference should be made to the drawings which form a further part hereof, and to accompanying descriptive matter, in which there are illustrated and described specific examples of an apparatus in accordance with the invention.
REFERENCES:
patent: 5022077 (1991-06-01), Bealkowski et al.
patent: 5111465 (1992-05-01), Edem et al.
patent: 5128995 (1992-07-01), Arnold et al.
patent: 5239640 (1993-08-01), Froemke et al.
patent: 5551043 (1996-08-01), Crump et al.
patent: 5659801 (1997-08-01), Kopsaftis
patent: 5666411 (1997-09-01), McCarthy
patent: 5682550 (1997-10-01), Brown et al.
patent: 5684944 (1997-11-01), Lubbers et al.
patent: 5701316 (1997-12-01), Alferness et al.
patent: 5768426 (1998-06-01), Rhoads
patent: 5778395 (1998-07-01), Whiting et al.
patent: 5806073 (1998-09-01), Piaton
patent: 5832235 (1998-11-01), Wilkes
patent: 5850562 (1998-12-01), Crump et al.
patent: 5978475 (1999-11-01), Schneier et al.
patent: 6052733 (2000-04-01), Mahalingam et al.
patent: 6094654 (2000-07-01), Van Huben et al.
patent: 6169992 (2001-01-01), Beall et al.
patent: 6185567 (2001-02-01), Ratnaraj et al.
patent: 6195664 (2001-02-01), Tolfa
patent: 8-339309 (1996-12-01), None
Bright, Jonathan D. et al., “Checking the Integrity of Trees”, Digest of Pepe, Twenty-Fifth International Symposium on Fault-Tolerant Computing, Jun. 27-30, 1995, FTCS-25, pp. 402-411.*
Drechsler, R., “Checking Integrity during Dynamic Reordering in Decision Diagrams”, Proceedings of the 25th EUROMICRO Conference, Sep. 8-10, 1999, vol. 1, pp. 360-367.*
McAuley, A. J., “Weighted Sum Codes for Error Detection and Their Comparison with Existing Codes”, IEEE/ACM Transactions On Networking, vol. 2, No. 1, Feb. 1994, pp. 16-22.*
IBM Technical Disclosure Bulletin, 37(11):469-471 (Nov. 1994).
Chen Chiahong
Hill Mark Edward
Alam Hosain T.
Alam Shahid
Altera Law Group LLC
International Business Machines - Corporation
LandOfFree
Method and apparatus for updating checksums of data structures does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for updating checksums of data structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for updating checksums of data structures will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2452496