Electrical computers and digital processing systems: memory – Address formation – Using table
Reexamination Certificate
1999-05-07
2002-07-02
Nguyen, Than (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Using table
C711S170000, C711S171000, C711S172000, C711S173000, C711S200000, C711S215000, C711S216000, C711S217000
Reexamination Certificate
active
06415375
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to the field of information storage and retrieval, and particularly to the storage and reading of data with computers and also particularly to data management in that it provides data storage and retrieval at high speeds, high ratios of data to storage capacity and greatly reduced maintenance time.
2. Description of Related Art
Conventional information storage systems are subject to numerous practical constraints such as contiguity in the physical location of blocks and the requirement that storage blocks be created in advance. Moreover, in most systems random access requires the creation of indices, which take a long time to generate, and the structure of these systems makes them prone to deadlock since the indices are updated and the range of exclusion broadened when the referent information is modified. Although direct access systems do not use indices, these systems relate record keys with storage locations by means of special programs known as randomizing routines. In practice they do not allow for sequential access and exhibit low storage efficiency when compared with methods that use indices.
SUMMARY OF THE INVENTION
Since conventional information storage and retrieval systems presumed their data would be stored on magnetic disk, in certain respects their shortcomings are unavoidable. On the other hand, the price of semiconductors has fallen remarkably and conditions for using semiconductors as memory devices are falling into place. Semiconductors do not necessitate physical movement or rotation and enable high-speed storage and reading even if addresses are not contiguous. The construction of a memory device taking advantage of these properties and comprising semiconductors alone or semiconductors and random access memory media would enable high-speed storage and retrieval processing. A semiconductor may be used as the primary memory device or may be provided to the invention as an external memory device. Storing information sequentially in blocks, using overflow blocks for storage when the insertion of information causes an overflow, using location tables or alternate-key blocks that manage storage blocks rather than using indices, and performing retrievals from these location tables or alternate-key blocks enables high-speed storage and reading, improves the efficiency of information storage and minimizes the occurrence of deadlock.
Location tables and alternate-key tables are introduced in place of indices. Records are not stored independently; rather, multiple records are stored in a single block.
FIG. 4
illustrates the structure of a block. The FROM and TO segments in
FIG. 4
represent the minimum key value and maximum key value of the block, respectively, but neither is absolutely necessary and the invention may be implemented with either one alone. When using long records, a single record may be matched to a single block, and a format in which a single record is stored over two or more blocks (spanned records) is also possible. All primary blocks in a single file and all overflow blocks in a single file are of equal lengths, facilitating region management. Storage in blocks allows block detection by means of fixed-length operations even when variable-length records are stored because the block units are of a fixed length. The location table secures the required contiguous region in advance. A single record (entry) in a location table manages a single primary block in the data record storage region. Although it is also possible to implement methods of managing multiple primary blocks, since primary blocks may be of any given size it is simpler not to manage multiple blocks if the implementation allows modification of the size of blocks. Blocks are classified into primary blocks and overflow blocks, and only the primary blocks are managed in the location table. Records are stored first of all in primary blocks. If storage in a block is rendered impossible due to insertion of a record, a single overflow block is allocated to that block. If that overflow block is not sufficient for storage, one more overflow block is allocated. Overflow blocks are managed as dependent blocks of their primary block; they are not managed in the location table but only by pointing from the primary block.
Since overflow blocks are not managed in the location table, records are not inserted into the location table, the time it takes to re-write the location table is minimized and re-writing of the location table is a single record. Therefore, the range of any exclusion that may occur is radically minimized and the possibility of a deadlock is greatly reduced.
A deadlock occurs when two different tasks on a single computer perform exclusion operations on two or more identical resources in different sequences but does not occur if the sequence of exclusion is identical, and narrower ranges of exclusion reduce the probability of deadlock. Conventional indices are made up of multiple levels. When a record is accessed and a record's key is modified when an index is updated, the index is also modified. When this affects the lowest-level index alone, the exclusion range is restricted, but in some cases this may affect higher-level indices. Since exclusion affects a range of multiple records and it takes a great deal of time to update the indices in such cases, exclusion takes up long periods of time and is a cause of multiple instances of deadlock.
OBJECTS AND ADVANTAGES
Accordingly, several objects and advantages of the invention are:
(a) To provide high-speed random access by using primary keys and alternate keys;
(b) To provide high-speed sequential read and write operations;
(c) To provide minimal modification caused by updating, modification and deletion of data, short processing time, and high-speed storage by using location tables and alternate-key blocks instead of indices;
(d) To provide creation (generation) of location tables and alternate-key blocks in shorter times than are required for the creation of indices;
(e) To eliminate the necessity of creating blocks in advance;
(f) To provide the ability to add blocks until no physical space remains on a storage medium;
(g) To provide record-compression capabilities deriving from the capability of handling variable-length records and record insertion (though in most cases compressed records cannot be updated);
(h) To provide the capability of using multiple alternate keys; and
(i) To provide greatly reduced database maintenance time.
REFERENCES:
patent: 5561793 (1996-10-01), Bennett et al.
patent: 5826076 (1998-10-01), Bradley et al.
patent: 5991776 (1999-11-01), Bennett et al.
Annex Systems, Inc.
Berkowitz Marvin C.
Nath Gary M.
Nath & Associates PLLC
Nguyen Than
LandOfFree
Information storage and retrieval system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Information storage and retrieval system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Information storage and retrieval system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2823199