Apparatus, system, and method for determining the consistency of a database

An apparatus, system, and method are disclosed for determining the consistency of a database including indirect reference to data elements. There is provided an apparatus for determining consistency of a database. This database includes, in association with each data element, an indirect list element including a storage address of the associated or corresponding data element so that other data elements can reference that data element. This apparatus reads, from each data element, identification information of an indirect list element corresponding to that data element and generates a hash value. This apparatus further reads, from each data element, identification information of an indirect list element corresponding to a data element referenced by that data element and generates a hash value. On condition that these hash values are equivalent to each other, the apparatus determines that the database is consistent.

CROSS-REFERENCES TO RELATED APPLICATIONS

This application claims the right of priority under the Paris Convention to Japan Patent Application Number 2005-291155 entitled “APPARATUS AND METHOD FOR DETERMINING CONSISTENCY OF DATABASE” and filed on Oct. 4, 2005 for Tatsuyuki Shiomi, et al., which is incorporated herein by reference.

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to determining the consistency of a database and more particularly relates to determining the consistency of a database in which a data element is referenced indirectly.

2. Description of the Related Art

A hierarchical database system (for example, IBM IMS DL/I or IMS) manages data elements by means of a tree structure. In this database, a minimum unit of data is referred to as a data element and a data element located at the highest level of a tree structure is referred to as a root element. A root element has one or more dependent elements which, in turn, have further dependent elements. Specifically, each data element has one or more pointers designating storage addresses of dependent elements. A storage address of each data element may be designated by a relative byte address (RBA), which is an address value relative to a specific address of a partition recording a database.

Such a tree structure is usually formed in a single partition. However, when a large database is constructed, its tree structure may be formed in plural partitions by establishing an association or logical relationship between the partitions. One example of a database realizing this association is HALDB (IMS High Availability Large Database). The HALDB realizes the association by means of indirect list elements. See, for example, U.S. Pat. No. 5,933,820 and “The Complete IMS HALDB Guide: All You Need to Know to Manage HALDBS”, URL http://www.redbooks.ibm.com/redbooks/pdfs/sg246945.pdf.

A database can improve access efficiency by means of a reorganization operation such as compaction or defragmentation. Since this reorganization operation rerecords a plurality of dispersed data elements in continuous areas, storage addresses of data elements may be changed. A reorganization operation can be performed for each partition regardless of the logical relationship between the partitions. Therefore, in a database stored in a plurality of partitions, if dependency between data elements is designated by storage addresses, a tree structure before a reorganization operation cannot be appropriately maintained after the reorganization operation.

For this reason, according to HALDB, an indirect list element is recorded in a database in association with each data element, which includes a storage address of that data element so that other data elements can reference that data element. A referencing data element (hereinafter referred to as a source data element) has not only a storage address of a data element to be referenced (hereinafter referred to as a target data element) but also identification information of an indirect list element corresponding to the target data element so that the source data element can reference the target data element.

As a reorganization operation is performed in a partition to which a target data element belongs, a storage address in an indirect list element is updated to an appropriate storage address after the reorganization operation. By referencing the indirect list element, a storage address of a target data element included in a source data element can be updated to an appropriate value after the reorganization operation.

In a database reorganization operation, change of database definition, deletion of a data element, and/or change of partitioning may be performed in addition to change of a recording position of a data element. Thus, when a configuration of a database is changed, it is desirable to confirm whether dependency between data elements is appropriately maintained. This confirmation is realized by determining consistency of the database.

Two check types, i.e., a hash check and a full check are used to determine the consistency. In case of a hash check, a database management system (DBMS) reads, from each data element, an RBA of a data element to be referenced to generate a hash value. The DBMS also reads an RBA of each data element to generate a hash value. Then, the DBMS determines that the database is consistent on condition that the generated hash values are equivalent to each other.

If the hash values are not equivalent to each other, a full check is performed. The DBMS reads, from each data element, an RBA of a data element to be referenced, reads an RBA of each data element, and determines whether these are equivalent to each other. In this way, it is possible to appropriately determine not only whether the database is consistent but also inconsistent positions, if any. However, for a database adopting indirect list elements, no method has been proposed to effectively determine consistency of that database. From the foregoing discussion, it should be apparent that a need exists for an apparatus, system, and method to determine the consistency of a database. Beneficially, such an apparatus, system, and method would determine the consistency of a database that includes indirect list elements.

SUMMARY OF THE INVENTION

The apparatus to determine the consistency of a database in which an indirect list element is recorded for each data element, the indirect list element including a storage address of that data element in order to cause another data element to reference that data element, is provided with a plurality of modules configured to functionally execute the necessary steps of determining the consistency of a database. These modules in the described embodiments include a first reading unit configured to read identification information from each data element, the identification information identifying an indirect list element corresponding to that data element. The apparatus may also include a second reading unit configured to read identification information from each data element, the identification information identifying an indirect list element corresponding to a referenced data element. Further, the apparatus may include a first generating unit configured to generate a hash value of the identification information read from each data element by the first reading unit. The apparatus may also include a second generating unit configured to generate a hash value of the identification information read from each data element by the second reading unit. Additionally, the apparatus may include a determining unit configured to determine that the database is consistent in response to the hash value generated by the first generating unit being equivalent to the hash value generated by the second generating unit.

The apparatus, in one embodiment, is configured to include with each indirect list element a storage address of a data element corresponding to that indirect list element. The apparatus may further include a third reading unit configured to read a storage address of a data element from each indirect list element, the data element corresponding to the indirect list element. Additionally, the apparatus may include a third generating unit configured to generate a hash value based on the storage address read from each indirect list element by the third reading unit. The apparatus may also include a fourth generating unit configured to generate a hash value based on the storage address of each data element from which the first reading unit has read the identification information of the indirect list element, the determining unit determining that the database is consistent on further condition that the hash value generated by the third generating unit is equivalent to the hash value generated by the fourth generating unit.

The apparatus is further configured, in one embodiment, to include with each indirect list element a storage address of a data element corresponding to that indirect list element in association with identification information of that indirect list element. The apparatus may also include a third reading unit configured to read a storage address of a data element and identification information from each indirect list element, the storage address corresponding to the indirect list element. Additionally, the apparatus may include a third generating unit configured to generate a hash value based on the storage address and identification information read from each indirect list element by the third reading unit. The apparatus may also include a fourth generating unit configured to generate a hash value based on the identification information read from each data element by the first reading unit and the storage address of each data element from which the first reading unit has read the identification information, the determining unit determining that the database is consistent on further condition that the hash value generated by the third generating unit is equivalent to the hash value generated by the fourth generating unit.

In a further embodiment, the apparatus may be configured such that each data element further includes the number of referencing elements that is the number of other data elements referencing that data element, the first reading unit further reads the number of referencing elements from each data element in association with the identification information, and the first generating unit generates a hash value based on a value made by weighting the identification information read from each data element by the first reading unit with the number of referencing elements corresponding to that identification information.

In another embodiment, the apparatus is includes a first adjusting unit responsive to addition of a reference from a data element to another data element and determining that the database is consistent to add to the hash value generated by the first generating unit, a value made by multiplying identification information of an indirect list element corresponding to the referenced data element by an increment from the number of referencing elements included in the referenced data element before addition to the number of referencing elements included in the referenced data element after addition. The apparatus may also include a second adjusting unit configured to add to the hash value generated by the second generating unit identification information of an indirect list element for the referenced data element, which is added to the referencing data element.

The apparatus, in another embodiment, includes a third adjusting unit responsive to addition of a data element to the database and determining that the database is consistent to add to the hash value generated by the third generating unit a hash value based on identification information newly assigned to an indirect list element added in association with the data element and a storage address of the data element. The apparatus may also include a fourth adjusting unit configured to add a hash value to the hash value generated by the fourth generating unit based on identification information of an indirect list element corresponding to the added data element, which is included in the added data element, and a storage address of the added data element.

In a further embodiment, the apparatus is configured such that control information is recorded in the database in association with each of a plurality of indirect list elements, the control information indicating whether that indirect list element is invalid. The apparatus may also be configured such that the third reading unit reads a storage address of a data element and identification information from each of the plurality of indirect list elements from which an indirect list element corresponding to the control information indicating invalidity is excluded, the data element corresponding to that indirect list element.

In another embodiment, the apparatus may include a reorganization unit configured to reorganize the database by changing a storage address of a data element and a reorganization controlling unit configured to record the number of reorganization operations performed on the reorganized database and record the number of the reorganization operations performed on data elements corresponding to indirect list elements as the control information in with the associated indirect list element. The third reading unit may be configured to determine that an indirect list element is invalid in response to the number of reorganization operations recorded in association with the indirect list element is smaller than the number of reorganization operations associated with the database.

The apparatus, in another embodiment, includes a third adjusting unit responsive to deletion of a data element from the database and invalidation of an indirect list element corresponding to the deleted data element and determining that the database is consistent to subtract from the hash value generated by the third generating unit a hash value based on a storage address of the data element included in the invalidated indirect list element and identification information of the invalidated indirect list element. The apparatus may further include a fourth adjusting unit configured to subtract from the hash value generated by the fourth generating unit a hash value based on identification information included in the deleted data element and the storage address of the data element, the determining unit determining that the consistency is maintained on condition that the hash value changed by the third adjusting unit is equivalent to the hash value changed by the fourth adjusting unit.

In another embodiment, the apparatus includes a first adjusting unit responsive to deletion of a data element from the database and invalidation of an indirect list element corresponding to the deleted data element and determining that the database is consistent to subtract from the hash value generated by the first generating unit identification information of the invalidated indirect list element and a second adjusting unit responsive to change of a reference from a data element to another data element to subtract from the hash value generated by the second generating unit identification information included in the data element before change and add to the subtracted hash value identification information recorded in the data element after change. The determining unit may determine that the consistency is maintained on condition that the hash value changed by the first adjusting unit is equivalent to the hash value changed by the second adjusting unit.

A method of the present invention is also presented for determining, by an information processing apparatus, consistency of a database in which an indirect list element is recorded for each data element, the indirect list element including a storage address of that data element in order to make another data elements reference that data element. The method in the disclosed embodiments substantially includes the steps necessary to carry out the functions presented above with respect to the operation of the described apparatus and system. In one embodiment, the method includes reading from each data element identification information of an indirect list element corresponding to that data element, reading from each data element identification information of an indirect list element corresponding to a referenced data element, generating a first hash value of the identification information read from each data element corresponding to that data element, generating a second hash value of the identification information read from each data element corresponding to the referenced data element, and determining that the database is consistent in response to the first hash value being equivalent to the second hash value.

A computer program product of the present invention is also presented comprising a computer readable medium having computer usable program code programmed for determining consistency of a database in which an indirect list element is recorded for each data element, the indirect list element including a storage address of that data element in order to make another data element reference that data element. The computer program product in the disclosed embodiments substantially causes a computer to perform the steps necessary to carry out the functions presented above with respect to the operation of the described apparatus and method. In one embodiment, the operations of the computer program product include a first reading unit configured to read identification information of an indirect list element from each data element, the indirect list element corresponding to that data element; a second reading unit configured to read identification information of an indirect list element from each data element, the indirect list element corresponding to a referenced data element; a first generating unit configured to generate a hash value of the identification information read from each data element by the first reading unit; a second generating unit configured to generate a hash value of the identification information read from each data element by the second reading unit; and a determining unit configured to determine that the database is consistent in response to the hash value generated by the first generating unit being equivalent to the hash value generated by the second generating unit.

DETAILED DESCRIPTION OF THE INVENTION

Reference to a signal bearing medium may take any form capable of generating a signal, causing a signal to be generated, or causing execution of a program of machine-readable instructions on a digital processing apparatus. A signal bearing medium may be embodied by a transmission line, a compact disk, digital-video disk, a magnetic tape, a Bernoulli drive, a magnetic disk, a punch card, flash memory, integrated circuits, or other digital processing apparatus memory device.

FIG. 1is a schematic block diagram illustrating one embodiment of a database management apparatus10. The database management apparatus10accesses a database20and determines consistency of the database20. Specifically, the database management apparatus10may include an access unit15, a reorganization unit18, a consistency determining unit30, and a maintenance determining unit40. The access unit15accesses the database20in response to a request from a user or according to a preset schedule. The reorganization unit18reorganizes the database20by changing storage addresses of data elements in the database20. This reorganization causes a plurality of data elements to be arranged in continuous areas in the database20. Thus, efficiency of access to the database20can be improved.

The consistency determining unit30, in one embodiment, determines consistency of the database20and outputs a result of the determination when the database20is reorganized. The maintenance determining unit40determines whether the consistency of the database20is maintained when the database20is updated in a state where the consistency determining unit30has determined that the database20is consistent. The database management apparatus10according to the present embodiment can appropriately determine the consistency of the database20even if the database20consists of a plurality of partitions and each of the partitions may be separately reorganized.

FIG. 2illustrates one embodiment of a data structure of a database20. The database20may have a plurality of partitions, e.g., a partition200-1and a partition200-2. The partition200-1includes attribute information210-1, a data recording section220-1, and a reference recording section260-1. The attribute information210-1includes identification information (ID) of the partition. The attribute information210-1further includes the number of reorganization operations performed in the partition200-1which indicates how many times the partition200-1has been reorganized. For example, the ID of the partition200-1is one, and the number of reorganization operations performed in the partition200-1is four. Also, the partition200-2includes attribute information210-2, a data recording section220-2, and a reference recording section260-2. The attribute information210-2includes identification information (ID) of the partition. The attribute information210-2further includes the number of reorganization operations performed in the partition200-2which indicates how many times the partition200-2has been reorganized. For example, the ID of the partition200-2is two, and the number of reorganization operations performed in the partition200-2is five.

The data recording section220-1, in one embodiment, records a plurality of data elements one of which is shown as a data element230-1. The reference recording section260-1records an indirect list element270-1including a storage address of the data element230-1in association with the data element230-1so that the data element230-1can be referenced by another data element.

In one embodiment, the data element230-1includes a prefix240-1and a data portion250-1. The prefix240-1includes the number of referencing elements that is the number of other data elements referencing the data element230-1. If the number of referencing elements is greater than one, one data element230-1is referenced by a plurality of other data elements. The number of referencing elements may be represented by any information identifying the number of referencing elements other than an actual numeric value thereof. InFIG. 2, information identifying the number of referencing elements is shown with an abbreviation “SC”. This SC indicates a type of a data element. The number of referencing elements may be determined by the SC or may be different for each data element even if SC is the same. In the latter case, there is a field for holding the number of referencing elements for each data element in addition to the SC.

The prefix240-1, in one embodiment, includes identification information of an indirect list element corresponding to a data element referenced by the data element230-1. This identification information is referred to, for example, as ILK (Indirect List Key). In the example ofFIG. 2, referenced by the data element230-1is a data element230-2. The reference recording section260-2records an indirect list element270-2in association with the data element230-2. Therefore, the prefix240-1includes identification information of the indirect list element270-2corresponding to a data element referenced by the data element230-1.

The prefix240-1further may include a storage address of a data element referenced by the data element230-1. This storage address is referred to as RBA (Relative Byte Address) indicating a relative position from a specific base address in the partition200-2. For this reason, once a storage address of the data element230-2is changed by the reorganization of the partition200-2, the storage address of the data element230-2recorded in the prefix240-1becomes incorrect. The prefix240-1further may include identification information (ILK: Indirect List Key) of the indirect list element270-1corresponding to the data element230-1.

A storage address (RBA) of the data element230-1corresponding to the indirect list element270-1may be recorded in the indirect list element270-1in association with identification information (ILK) of the indirect list element270-1. When the data element230-1is referenced by another data element, the access unit15specifies the indirect list element270-1by this identification information (ILK) and reads a storage address (RBA) in the indirect list element270-1to specify the data element230-1. The indirect list element270-1includes identification information (ID) of the partition200-1in which the data element230-1corresponding to the indirect list element270-1is recorded and the number of reorganization operations by which the data element230-1has been reorganized. The number of reorganization operations is incremented by one whenever the data element230-1is reorganized by the reorganization unit18.

Even if the data element230-1becomes invalid due to a deletion/update operation on the database20, the data element230-1and the indirect list element270-1corresponding thereto may remain in the database20without being deleted. In this case, since the data element230-1is not involved in the reorganization, the number of reorganization operations included in the indirect list element270-1is not increased even if the reorganization is performed. That is, while the number of reorganization operations recorded in the attribute information210-1is four, the number of reorganization operations included in the indirect list element270-1has a value less than four.

The number of reorganization operations, in one embodiment, serves as control information indicating whether the indirect list element270-1is invalid. That is, a third reading unit350described below determines that an indirect list element is invalid on condition that the number of reorganization operations recorded in association with the indirect list element is smaller than the number of reorganization operations associated with the database20. In the example ofFIG. 2, “four” is recorded in the indirect list element270-1as the number of reorganization operations as well as in the attribute information210-1, resulting in the equivalent number. Therefore, the third reading unit350may determine that the indirect list element270-1is valid. On the other hand, “three” is recorded in an indirect list element272as the number of reorganization operations, which is different from the number of reorganization operations recorded in the attribute information210-1. For this reason, the third reading unit350determines that the indirect list element272is invalid.

The data recording section220-2, in one embodiment, records a plurality of data elements one of which is the data element230-2. The reference recording section260-2records the indirect list element270-2in association with the data element230-2, in which a storage address of the data element230-2is recorded so that the data element230-2can be referenced by another data element. The data element230-2includes a prefix240-2and a data portion250-2. The prefix240-2includes the number of elements referencing the data element230-2. The prefix240-2further includes identification information (ILK) of an indirect list element corresponding to a data element referenced by the data element230-2, and a storage address of a data element referenced by the data element230-2.

The prefix240-2, in one embodiment, further includes identification information (ILK) of the indirect list element270-2corresponding to the data element230-2. The indirect list element270-2may include a storage address (RBA) of the data element230-2corresponding to the indirect list element270-2in association with the identification information (ILK) of the indirect list element270-2. A reference by the data element230-1to the data element230-2causes the access unit15to first specify the indirect list element270-2by means of this identification information (ILK). Then, the access unit15specifies the data element230-2by reading the storage address (RBA) in the indirect list element270-2. In this way, it is possible to appropriately reference the data element230-2even if the storage address (RBA) of the data element230-2included in the data element230-1is incorrect.

FIG. 3shows one embodiment of a functional configuration of the consistency determining unit30. The consistency determining unit30may include a reorganization controlling unit300, a first reading unit310, a second reading unit320, a first generating unit330, a second generating unit340, a third reading unit350, a third generating unit360, a fourth generating unit370, and a determining unit380. The reorganization controlling unit300records the number of reorganization operations performed in association with the reorganized database20. Specifically, the reorganization controlling unit300, in one embodiment, increments by one the number of reorganization operations recorded in the attribute information210-1on condition that the partition200-1in the database20has been reorganized.

The reorganization controlling unit300, in one embodiment, records the number of reorganization operations as control information in association with an indirect list element corresponding to a data element involved in the reorganization. Specifically, the reorganization controlling unit300may record the updated number of reorganization operations in the indirect list element270-1on condition that the partition200-1has been reorganized. The reference recording section260-1may retain an indirect list element without deleting it, which has been invalidated due to deletion of a corresponding data element. In this case, the reorganization controlling unit300does not update the number of reorganization operations for the indirect list element invalidated. Therefore, even if the partition200-1has been reorganized, the original number of reorganization operations remains. In this way, it is possible to appropriately distinguish between valid and invalid indirect list elements.

The first reading unit310, in one embodiment, reads, from each data element, identification information of an indirect list element corresponding to that data element when the database20is reorganized. For example, the first reading unit310may read an ILK of the indirect list element270-2corresponding to the data element230-2from the data element230-2. The first reading unit310may further read the number of referencing elements from each data element in association with the identification information of its indirect list element.

In one embodiment, the second reading unit320reads, from each data element, identification information of an indirect list element corresponding to a data element referenced by that data element when the database20is reorganized. For example, the second reading unit320may read an ILK of the indirect list element270-2corresponding to the data element230-2referenced by the data element230-1from the data element230-1.

The first generating unit330, in one embodiment, generates a hash value of the identification information read from each data element by the first reading unit310. Specifically, the first generating unit330may compute a hash value based on a value made by weighting the identification information read from each data element by the first reading unit310with the number of referencing elements corresponding to the identification information. As an example of the computing process, the first generating unit330first multiplies the number of referencing elements of the identification information by each of the read identification information. For example, if identification information is 0x0200 and the number of referencing elements is four, the first generating unit330computes 0x0800 made by multiplying 0x0200 by four. Then, the first generating unit330obtains a hash value by summing the computed values for the respective data elements. A hash value computed in this manner becomes a first hash value.

In one embodiment, the second generating unit340computes a hash value of the identification information read from each data element by the second reading unit320. The second generating unit340may generate a hash value by summing the identification information under a predetermined modulo. This hash value becomes a second hash value. The third reading unit350may read, from each of the indirect list elements, a storage address of a data element corresponding to that indirect list element and identification information (ILK) of that indirect list element, to the exclusion of any indirect list element corresponding to the control information indicating invalidity.

The third generating unit360, in one embodiment, generates a hash value based on a set of the storage address and identification information (ILK) read from each indirect list element by the third reading unit350. This hash value becomes a third hash value. The fourth generating unit370may generate a hash value based on a set of the identification information read from each data element by the first reading unit310and the storage address of each data element from which the first reading unit310reads the identification information. This hash value becomes a fourth hash value.

The determining unit380, in one embodiment, determines whether the first hash value generated from the first generating unit330is equivalent to the second hash value generated from the second generating unit340. The determining unit380may further determine whether the third hash value generated from the third generating unit360is equivalent to the fourth hash value generated from the fourth generating unit370. The determining unit380may determine that the database20is consistent on condition that both determinations are affirmative.

FIG. 4illustrates one embodiment of a functional configuration of the maintenance determining unit40. The maintenance determining unit40may include an update log recording unit400, a first adjusting unit410, a second adjusting unit420, a third adjusting unit430, and a fourth adjusting unit440. In response to the database20being updated by the access unit15, the update log recording unit400may record an update log. The first adjusting unit410, in one embodiment, determines whether any of the data elements is deleted from the database20and an indirect list element corresponding to that data element is invalidated, in a state where the determining unit380has determined that the database20is consistent. The first adjusting unit410may further determine whether a reference from a data element to another data element has been added, in a state where the determining unit380has determined that the database20is consistent. These determinations may be performed by referring to the update log recording unit400.

If any of the data elements has been deleted from the database20and an indirect list element corresponding to that data element has been invalidated, the first adjusting unit410, in one embodiment, changes the first hash value generated by the first generating unit330. Specifically, the first adjusting unit410may subtract identification information of the invalidated indirect list element from the first hash value. It is desirable to weight a value of the identification information to be subtracted with the number of referencing elements corresponding to the identification information. Also, if a reference from a data element to another data element has been added, the first adjusting unit410may change the first hash value.

In one embodiment, the second adjusting unit420determines whether a reference from a data element to another data element has been changed or added, based on the update log recording unit400. If a reference from a data element to another data element has been changed or added, the second adjusting unit420may change the second hash value generated by the second generating unit340. For example, the second adjusting unit420subtracts identification information recorded in the data element before a change from the second hash value and adds identification information recorded in the data element after a change to the subtracted hash value.

The third adjusting unit430, in one embodiment, determines whether any of the data elements is deleted from the database20and an indirect list element corresponding to that data element is invalidated, in a state where the determining unit380has determined that the database is consistent. The third adjusting unit430may further determine whether a data element has been added to the database20. The third adjusting unit430may change the third hash value generated by the third generating unit360on condition that any of the data elements has been deleted from the database20and an indirect list element corresponding to that data element has been invalidated or on condition that a data element has been added. For example, the third adjusting unit430subtracts a hash value based on a set of a storage address of the data element recorded in the invalidated indirect list element and identification information of the invalidated indirect list element from the third hash value.

The fourth adjusting unit440, in one embodiment, changes the fourth hash value generated by the fourth generating unit370on condition that any of the data elements has been deleted from the database and an indirect list element corresponding to that data element has been invalidated or on condition that a data element has been added. For example, the fourth adjusting unit440subtracts a hash value based on a set of identification information recorded in the deleted data element and a storage address of the data element from the fourth hash value.

In one embodiment, the determining unit380receives the changed hash values, and compares the first hash value changed by the first adjusting unit410with the second hash value changed by the second adjusting unit420. The determining unit380may further compare the third hash value changed by the third adjusting unit430with the fourth hash value changed by the fourth adjusting unit440. The determining unit380may determine that the consistency of the database20is maintained on condition that the first hash value is equivalent to the second hash value and the third hash value is equivalent to the fourth hash value.

FIG. 5illustrates a flowchart of one embodiment of a process by which the consistency determining unit30determines consistency of the database20.FIG. 6shows a flowchart of one embodiment of a process following the process ofFIG. 5. Once the reorganization of the database20has been completed, the consistency determining unit30may perform the following process. First, the first reading unit310reads S500, from each data element, identification information of an indirect list element corresponding to that data element. The first reading unit310further reads the number of referencing elements which reference the indirect list element, in association with the identification information. Next, the second reading unit320reads S510, from each data element, identification information of an indirect list element corresponding to a data element referenced by that data element.

Then, the first generating unit330computes S520a hash value of the identification information read from each data element by the first reading unit310. Upon generating this hash value, the first generating unit330weights each of the identification information with the corresponding number of referencing elements (for example, it multiplies the identification information by the number of referencing elements.) This hash value is referred to as a first hash value. The second generating unit340computes S530a hash value of the identification information of the indirect list elements read by the second reading unit320. This hash value is referred to as a second hash value. The determining unit380determines S540whether the first hash value generated by the first generating unit330is equivalent to the second hash value generated by the second generating unit340.

On condition that these hash values are not equivalent to each other (S540: NO), the determining unit380determines S550that the database20is not consistent. In this case, the consistency determining unit30may perform a full check on the database20to detect any inconsistent point. On condition that these hash values are equivalent to each other (S540: YES), the third reading unit350reads S600, from each of the indirect list elements, a storage address of a data element corresponding to that indirect list element and identification information (ILK) of that indirect list element.

Then, the third generating unit360computes S610a hash value based on a set of the storage address and identification information (ILK) read from each indirect list element by the third reading unit350. This hash value is referred to as a third hash value. The fourth generating unit370computes S620a hash value based on a set of the identification information read from each data element by the first reading unit310and the storage address of each data element from which the first reading unit310reads the identification information. This hash value is referred to as a fourth hash value.

The determining unit380determines S630whether the third hash value generated by the third generating unit360is equivalent to the fourth hash value generated by the fourth generating unit370. On condition that these hash values are not equivalent to each other (S630: NO), the determining unit380determines S670that the database20is not consistent. On condition that these hash values are equivalent to each other, the determining unit380determines S640consistency of other portions. For example, the determining unit380may perform the following consistency determination.

The determining unit380computes, based on the contents of each data element included in the database20, the sum of the number of data elements referenced by these data elements. The determining unit380further computes the sum of the number of valid indirect list elements included in the database20. On condition that these sums have the equivalent value, the determining unit380determines that the database20is consistent.

The determining unit380further computes the sum of the number of storage addresses of referenced data elements included in each data element in the database20. The determining unit380further computes the sum of the number of referencing elements included in each data element in the database20. Then, on condition that these sums have the equivalent value, the determining unit380determines that the database20is consistent.

If the above sums have the equivalent values, respectively, (S650: YES), the determining unit380determines S660that the database20is consistent. If any one of them is different (S650: NO), the determining unit380determines S670that the database20is not consistent.

FIG. 7shows a flowchart of one embodiment of a process by which the maintenance determining unit40determines whether the consistency of the database20is maintained.FIG. 8shows a flowchart of one embodiment of a process following the process ofFIG. 7. In a state where the determining unit380has determined that the database20is consistent, the maintenance determining unit40may determine S700whether any of the data elements is deleted from the database20and an indirect list element corresponding to that data element is invalidated. If a data element is deleted, the first adjusting unit410changes S710identification information of the invalidated indirect list element from the hash value generated by the first generating unit330by subtracting.

Here, “subtract” means an inverse operation to that for computing a hash value. For example, when the sum of identification information is used as a hash value, the first adjusting unit410subtracts identification information of an invalidated indirect list element from the hash value. As another example, when exclusive OR of identification information is used as a hash value, since an inverse operation to an exclusive OR operation is also an exclusive OR operation, the first adjusting unit410calculates a changed hash value by performing an exclusive OR operation on a hash value before change and a hash value of the invalidated indirect list element.

The third adjusting unit430changes S720a hash value based on a set of a storage address of a data element included in the invalidated indirect list element and identification information of the invalidated indirect list element from the hash value generated by the third generating unit360by subtracting. The fourth adjusting unit440changes S730a hash value based on a set of identification information included in the deleted data element and a storage address of the data element from the hash value generated by the fourth generating unit370by subtracting.

Subsequently, the maintenance determining unit40determines S800whether a reference from any of the data elements to another data element has been changed. If the reference has been changed (S800: YES), the second adjusting unit420subtracts S810identification information included in that data element before change from the second hash value generated by the second generating unit340. Then, the second adjusting unit420adds S820identification information recorded in that data element after change to the second hash value after the subtraction. Here, similarly to “subtract”, “add” also means an operation for computing a hash value which is not limited to a simple addition.

Subsequently, the maintenance determining unit40determines S830whether a reference from any of the data elements to another data element has been added. If the reference has been added (S830: YES), the first adjusting unit410changes S840the first hash value. Specifically, the first adjusting unit410first obtains an increment from the number of referencing elements included in the referenced data element before addition to the number of referencing elements included in the referenced data element after addition. For example, if only one reference has been added to this data element, this increment is one. Then, the first adjusting unit410adds a value made by multiplying identification information of an indirect list element corresponding to the referenced data element by the increment to the first hash value.

Next, the second adjusting unit420adds S850identification information of an indirect list element corresponding to the referenced data element which is added to the referencing data element, to the second hash value. Here, a reference is added not only when an existing data element newly references another existing data element but also when a new data element is added, resulting in addition of a new reference. When a referenced data element is added in concurrence with addition of a reference, the number of referencing elements included in the data element before addition is considered as zero. If a data element is newly added, a process shown inFIG. 9is subsequently performed.

FIG. 9illustrates a flowchart of one embodiment of a process following the process ofFIG. 8. In a state where the determining unit380has determined that the database20is consistent, the maintenance determining unit40determines S900whether a data element has been added to the database20. If a data element has been added to the database20(S900: YES), the third adjusting unit430changes S910the third hash value. Specifically, the third adjusting unit430obtains a hash value based on a storage address (RBA) of the data element and identification information (ILK) newly assigned to an indirect list element which is added in association with the data element.

The indirect list element corresponding to the added data element may not be generated promptly. Even so, identification information (ILK) to be newly assigned to the indirect list element generated later is determined when the data element is added, and is recorded in the data element. The third adjusting unit430changes S910the third hash value by using this identification information.

Next, the fourth adjusting unit440adds S920a hash value based on the identification information (ILK) of the indirect list element corresponding to the added data element, which is included in that data element, and a storage address of the added data element to the fourth hash value. The determining unit380determines S930whether the first hash value changed by the first adjusting unit410is equivalent to the second hash value changed by the second adjusting unit420. The determining unit380further determines S930whether the third hash value changed by the third adjusting unit430is equivalent to the fourth hash value changed by the fourth adjusting unit440. On condition that both determinations are affirmative (S930: YES), the determining unit380determines S940that the consistency of the database20is maintained. On the other hand, if either of the determinations is negative (S930: NO), the determining unit380determines S950that the consistency of the database20is not maintained.

FIG. 10illustrates one embodiment of a hardware configuration of an information processing apparatus1000functioning as the database management system10. The information processing apparatus1000may be a mainframe computer, which may include a main storage1002, at least one central processing unit1004, a storage controller1006, a channel subsystem1008, at least one control unit1010, and at least one I/O device1012ato1012d.

The main storage1002, in one embodiment, stores data and programs input from the I/O devices1012ato1012d. When addressed by the central processing unit1004or the channel subsystem1008, the main storage1002may send data stored at the specified address to the central processing unit1004or the channel subsystem1008.

In one embodiment, the central processing unit1004controls the whole of the information processing apparatus1000, and runs at least one operating system1005. The operating system1005may control program execution and input/output processing in the information processing apparatus1000. For example, the operating system1005may control the execution of other programs operating on the central processing unit1004, or may control data transfer to or from the I/O devices1012ato1012d.

The storage controller1006, in one embodiment, is connected to the central processing unit1004via a bus1014which may be either bidirectional or unidirectional. The storage controller1006is also connected to the main storage1002via a bus1016, and to the channel subsystem1008via a bus1018. The storage controller1006may temporarily store (or queue) an access request received from the central processing unit1004or the channel subsystem1008, and send the access request to the main storage1002at an appropriate time.

In one embodiment, the channel subsystem1008is connected to each of the control units1010via a data transfer path1020. The channel subsystem1008may control data transfer between the I/O devices1012ato1012dand the main storage1002. The channel subsystem1008may transfer data to the I/O devices1012ato1012dvia at least one channel pass1022. Each channel pass1022may have a channel1024provided in the channel subsystem1008, at least one control unit1010and the data transfer path1020. Here, the data transfer path1020may be a serial link based on, e.g., ESCON (Enterprise Systems Connection Architecture). Alternatively, the data transfer path1020may be a parallel OEMI, or may be a fiber channel.

The control unit1010, in one embodiment, controls at least one of the I/O devices1012ato1012d. For example, the control unit1010may control data transfer timing in each of the I/O devices1012ato1012d. The control unit1010may be connected to at least one of the I/O devices1012ato1012dvia a bus1026. As an example, the control unit1010can access up to 256 I/O devices.

In one embodiment, the I/O devices1012ato1012dmay transfer data to or receive data from the main storage1002via the control unit1010, the channel subsystem1008, and the storage controller1006. Here, the I/O device1012ais specifically a magnetic tape drive, and the I/O device1012dis a hard disk drive. Alternatively or additionally, the I/O devices1012ato1012dmay be a display, a keyboard, a printer, a communication device, various sensors, and/or other storage devices. As an example, at least one of the I/O devices1012ato1012dmay be connected to the database20to access the database20.

In one embodiment, a program according to the present invention may be stored in the main storage1002from the I/O device1012a(tape drive) via the channel subsystem1008. Operations performed by the information processing apparatus1000according to the stored program are described above for the database management system10with reference toFIGS. 1 to 9.

The program described above may be stored on an external storage medium other than the tape drive in one embodiment. A storage medium may be an optical recording medium such as a DVD or a PD, a magneto-optical recording medium such as an MD, a at semiconductor memory such as an IC card, or any other suitable medium in addition to a flexible disk or a CD-ROM. Alternatively, a storage device such as a hard disk or a RAM provided in a server system connected to a private communication network or the Internet may be used as the recording medium to provide a program to the information processing apparatus1000via the network.