JPH06348760A - Method for generation of key to store text in database - Google Patents

Abstract

PURPOSE: To generate a unique data access key. CONSTITUTION: A key is generated by the direct input of a text to a circulating redundancy check generator and used in an index to store or extract the text. It is checked whether a duplicate key exists in order to assure that the generated key is really unique. If a duplicate key is detected, the text corresponding to a newly generated key is compared with the text that is already stored in a data base. When these text strings are not equal to each other, they are stored in the index together with a CRC number. Then the count value of a sequence counter having its initial value '1' is increased, and the new keys are continuously generated until a unique key is detected or the relevant text is detected out of the data base.

Description

Detailed Description of the Invention

[0001]

FIELD OF THE INVENTION This invention relates to data processing systems, and more particularly to generating unique keys for accessing information in a database.

[0002]

BACKGROUND OF THE INVENTION Many applications have a unique identifier (ID) associated with a record that is inserted into a database.
Or you have a need for unique keys. Modern technology teaches that a unique key can be created from a cascade of strings of information loosely related to the records stored. For example, the unique key is date, time, domain name,
It is generated as a series of user names and library names. While such cascades have been successful in generating unique keys, the procedure has the disadvantage of creating very large keys, thus increasing the storage and processing requirements of the system.

Another problem with modern technology, especially when unique keys are used to index records in a database, is the natural problem between the text in the record and the unique key. Lack of relationships or direct relationships. The lack of direct relationship between text and keys results in the presence of duplicate records in the database, which increases storage and retrieval time for a particular record.

The conventional method utilizes a check polynomial (Cyclic Redundancy Check CRC16) as a Hashing generator to reduce the length of the keys attached to the record to provide the disk file address for the record. ing.
This method uses a hashing generator to reduce the long synonym sequences associated with other hashing procedures. Sequential numeric keys were created, which provided a reduction in the time required to store and retrieve data.
Each record has a unique numeric data length of 3 to 24 bytes.
Contains the key. The data key is compressed using a hashing generator from an original length of 3 to 24 bytes to a 2-byte index. This approach is aimed at creating an index table with as few duplicate entries as possible called synonyms. A 2-byte index is used, which requires an index table for 64K entries.
If the index is empty when storing a record,
That record becomes the first record of the string and the disc address of that record is placed in the index table. If the index entry is not empty, each record in the string is examined for erroneous duplicate keys. If no duplicate key is found, the record is saved and the synonym string pointer is updated. If the index entry is empty when reading the record, then the record does not exist. If the index entry is not empty, each record in the string is read and the search keys are compared. If the same key is found, the record is located, otherwise the record does not exist.

The above solution uses a cyclic redundancy check generator on the data keys to generate sequentially numbered keys, thus reducing the time required to store and retrieve records from the database. Was. However, this solution still suffers from the drawback of the prior art, namely that the index element has no natural or direct relationship to the text. The reason is,
This solution starts with a unique data key of 3 to 24 bytes and applies it to the CRC generator to produce a 2-byte index key. Original data
The key has no direct relationship to the text, and so does the CRC index as well. Moreover, this solution does not eliminate the storage of duplicate data and thus becomes inoperable when a unique key is not provided.

As a result, there is a technique for providing a procedure for generating a unique key that has a direct relationship to the text to be stored in the database so that duplicate text entries in the database can be eliminated. is necessary.

[0007]

SUMMARY OF THE INVENTION The present invention is directed to a method and apparatus for generating a unique identifier that is directly associated with text to be stored in a database.

[0008]

The "almost unique" key is derived directly from the text field. This key is generated by entering the text directly into the Cyclic Redundancy Check Generator. This generator generates a 4-byte CRC number based on the text. This 4-byte CRC number is cascaded with the contents of the sequence counter and is used as a key in an index placed in the database for storing and retrieving text. To ensure that the generated keys are truly unique, a check is made as to whether duplicate keys exist. When a duplicate key is found, the text for the newly generated key is compared to the text already stored in the database. If this text string is not equal to each other then it is stored in the index along with the CRC number and the initial value of 1 the sequence counter is incremented to find the unique key or the data
New keys are generated until the text is found in the base.

[0009]

1 is a pictorial representation of a data processing system 10 that may be used to implement the method and apparatus of the present invention. The data processing system 10 includes a processor 12 (including an internal central processing unit, read only memory, random access memory, etc., not shown but well known to those skilled in the art), in a manner well known to those skilled in the art. It includes a connected keyboard 14 and display monitor 16.

The processor 12 is adapted to receive a removable storage medium such as a diskette 13 containing application programs, data or other software. The data processing system 10
It will be apparent to those skilled in the art that it can be configured using any suitable computer such as a personal computer or a workstation coupled to a host computer. One example of a data processing system that may be used to implement the method and apparatus of the present invention is the IBM Personal System / 2 (PS) manufactured by IBM Corporation.
/ 2).

Referring now to FIG. 2, a prior art approach to generating a unique identifier is shown. Many applications have a need for unique identifiers associated with records inserted into the database. This key is used as an index to store and retrieve records from the database.

With specific reference to FIG. 2, the conventional technique for generating a unique key is performed by cascading related information. For example, date 42, time 44, domain name 4 to locate record / text 50
6, and the username 48 can be cascaded. As will be appreciated by those skilled in the art, such cascading often produces long unique keys, which increases system storage and processing requirements. In addition, the generated key is another problem that exists in nominating the application that inserts the record into the database, namely that the index element has no natural or direct relationship to the text. The question to say is unquestioned. Therefore, there is the problem of creating duplicate text items in the database, which increases the storage capacity required, reduces the probability of hitting cache memory, and increases search time. The device and method of the present invention directly addresses and eliminates all of these problems.

The present invention inputs a text string to be stored in a database directly into a cyclic redundancy check generator (CRC) for CRC number or code generation. A conceptual illustration showing how the invention may be implemented is shown in FIG. The text string 52 (comprising the text to be stored in the database) is C
Input to RC generator 54, which produces CRC number 56. This newly generated CRC number or code 56 is cascaded with the contents of the sequence counter and is used as an index to store the text string 52 in the database.

4-byte CRC is generated by 2-byte CRC
It will be appreciated by those skilled in the art that it increases the likelihood of not producing a similar CRC for dissimilar text strings compared to. Also, 4 bytes can represent 4 billion unique combinations, while 2 bytes are 6
It will also be appreciated by those skilled in the art that only 4000 combinations can be represented. Therefore, a large CRC is a CR similar to a dissimilar text string.
Reduce the likelihood of producing C. The likelihood that any new CRC will not overlap with existing strings of different values depends on the size of the database. For example, for a database with 1 million entries, a 4-byte CRC
Using an index, the probability that a new unique string will yield a key that already exists in the database is 42.
It is 1/94. Since it is unlikely, but there is still the possibility that two different strings will generate the same key, steps must be taken to detect when this has occurred. Obviously, the data base designer can choose the size of the index based on the needs of the particular application and increase or decrease the index size as needed.

Referring to FIG. 4, there is shown a conceptual block diagram of a technique for storing text in a database using the present invention. Application CPU (Central Processing Unit) 60 has the ability to execute programs that perform specific data processing activities (eg, payroll applications, airline reservations, network applications). Data base CPU 64
Is connected to the application CPU 60 and is used to store and retrieve text from a database store 66. The CRC generator 62 is connected to the application CPU 60 and generates a CRC number, which is cascaded with the sequence number and is used as a key in the index to retrieve the text from the database store 66. For those skilled in the art, the functions performed by different CPUs may be combined to create a single C
It will be clear that it may be placed in the PU.

The present invention uses the content or text value of the item to be stored in the database to generate the key. The key or index for a data item is created as a composite of the entire data item so that a unique key (for the data that produced the key by the composite) is generated. This key is used to quickly check for duplicate data in the database. A small example of this concept is shown in vote A.

Table A Text of Items in CRC Database X'0F3B '' Austin is the capital of Texas. 'X'22E5''Go ahead ... Make my day.'X'64AA'' Austin is the capital of Tejas. 'X'6CC7''Now is the time for all good men to come together.' As shown in Table A, the text from each data record is folded into a 2-byte hexadecimal number. The 2-byte hexadecimal number is generated by inputting data record 52 (FIG. 3) directly to CRC generator 54 to generate CRC number 56 in a manner well known to those skilled in the art. 16 of these 2 bytes
The radix is cascaded with the contents of the sequence counter and is used as a key in the index to store or retrieve records from the database. Now,
For example, a new text string ('Now is the firs
Given that t day of the rest of your life. 'was given for storage in the database, this procedure would be taken. First, the text string 5 is generated to generate the CRC number 56 based on the text string 52.
2 (FIG. 3) is input to the CRC generator 54. Text string'Nowis the first day of the rest of y
The CRC number for our life. 'is X'8A54'. The data is CR, provided the key is unique.
The database is defined as being sorted by C number and sequence number and stored in the database. It will be understood by those skilled in the art that if records are stored in the database using this definition, the checks will automatically be made to ensure that the conditions are met. Therefore, to see if there is a match, see Table A.
A simple binary search is performed on the CRC number of the cascade key shown in. The 2-byte hexadecimal number (X'8A54 ') is compared to other index entries to see if there are duplicate entries in the database. The use of key fields for comparison minimizes the size of the data that is matched and compared, which allows the CPU
Consumption and memory usage are reduced. In addition to this, this procedure increases and enhances the effectiveness of the cache.

The above discussion for generating a 2-byte hexadecimal number is taken for simplicity and clarity of description, which is the preferred embodiment of the present invention.
It will be apparent to those skilled in the art that it can be easily extended to generate a byte CRC index key. Further, it will be apparent to those skilled in the art that the present invention is not limited to using a CRC generator to generate the initial index key. Any method or procedure is applicable to the present invention as long as it produces numbers over a range and always produces the same number for the same input text string.

FIG. 5 shows a flow diagram for generating a unique key using the cyclic redundancy check generator for generating a key according to the present invention. The procedure begins at block 70 and proceeds to block 72 where a nearly unique key is generated by inputting a text string into the CRC generator. At block 74, C
A sequence counter is assigned to the almost unique key generated by the RC generator. The sequence counter is incremented by 1 at block 76 to
A unique key is created by cascading the contents of the counter to this almost unique key. At block 78, an attempt is made to store this unique key in the index and the text string in the database. At block 80, it is checked if the attempt to store the unique key was successful. If yes, the flow ends at block 84. If no, block 82 checks to see if the text string in the database matches the text string that is trying to be inserted. If yes, the text strings are duplicates and the flow ends at block 84 to avoid storing duplicate texts. If no, flow returns to block 76 where the sequence counter is incremented by one and the above procedure is repeated until either a key-text match is found or a unique key-text is stored in the database. . It will be appreciated by those skilled in the art that the present invention has the ability to generate unique keys for text strings of any length, including fixed and variable length text strings.

In summary, the present invention provides a method and apparatus for generating a unique key that can be used as an index for records stored in a database. More importantly, the keys and indexes have a natural or direct relationship with the stored records.
The present invention uses a CRC generator to generate a CRC number which is cascaded with the contents of the sequence counter to generate a unique key based on a text string which is not stored in the database. To do. Generating a key using the present invention allows the key to be used to check the uniqueness of text in a database. Although the key generated by the present invention is not unique under all conditions, the present invention achieves a truly unique key by including a sequence counter. This sequence counter is usually one.
The sequence counter is used to generate a truly unique key when the number of CRCs generated from the text string is found to be equal to the number of CRCs already stored in the database. This is done as follows. First, a check is made to see if the newly generated key is in fact a duplicate by comparing the newly generated key with the keys already stored in the index. If the newly generated key is equal to the key already stored in the index, then a check is made as to whether it came from the same text string. If the text strings are not the same, the sequence counter is incremented and the database check is repeated with the new sequence number. The present invention uses non-unique text strings as C
Allows having data that is easily indexed based on RC key comparison. The greatest benefit to the user is the elimination of duplicate text data, which results in a more efficient application and database.

[0021]

The effect of the present invention is the elimination of duplicate text data, which results in a more efficient application and database.

[Brief description of drawings]

FIG. 1 is an external view of a data processing system in which the present invention can be implemented.

FIG. 2 is a diagram showing generation of a unique key that is performed in the related art.

FIG. 3 is a conceptual diagram of an apparatus used to generate a unique key using the present invention.

FIG. 4 is a conceptual diagram showing a technique for generating a unique key and selecting it in a database using the present invention.

FIG. 5 is a flow diagram illustrating a procedure for generating a unique key using the present invention and using it to store a text string in a database.

[Explanation of symbols]

 16: Display monitor 14: Keyboard

Front Page Continuation (72) Inventor Dale Bee String Fellow Junia No. 2509, Clear Spring Drive, North Abing, Texas, USA

Claims (5)

[Claims] 1. A method for generating an identifier used in an index for accessing a text string stored in a database, the method comprising: generating the identifier based on the text string; Inputting to the cyclic redundancy check generator; associating the identifier with the text string; storing the identifier with the text string; a key used to store the text in a database consisting of: How to generate. 2. The method of claim 1, wherein the associating step comprises adding a sequence field to the identifier before storing the identifier in the index. 3. A method for generating a key used in an index for accessing a text string stored in a database, the index having a plurality of keys previously stored therein. , Providing the key as a function of the text string, comparing the key to each of a plurality of keys previously stored in the index, and A method of generating a key used to store text in a database comprising adding a sequence field to said key when equal to one of the keys. 4. Retrieving a previously stored text string associated with one of a plurality of previously stored keys found to be equal to the given key, and the given key 4. The method of claim 3, further comprising the step of comparing a text string associated with to the read text string to see if they are the same. 5. The method of claim 4, wherein the step of checking for identity includes discarding the given key when the text strings are identical.