Data processing: database and file management or data structures – Database design – Data structure types
Patent
1996-10-04
1999-09-14
Choules, Jack M.
Data processing: database and file management or data structures
Database design
Data structure types
G06F 1730
Patent
active
059537140
DESCRIPTION:
BRIEF SUMMARY
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a data base searching system and more particularly to a system which enables a data base to be interrogated at very high speed.
2. State of the Art
It has been proposed for data base searching systems to include a plurality of processing elements which simultaneously compare respective data records with a common data item being searched for. The processing elements of such systems include microprocessors and are therefore complex. Furthermore, communications sub-systems are required between the various processing elements, and an interrogations sub-system is required in order to interrogate the processing elements so that the results of the search procedure can be established.
Another system which has been proposed, called Content Addressable Memory, includes a comparator for each bit in the memory: this system can only provide equality comparisons and has fixed field and record sizes and more importantly is very expensive to produce because CAM memory cells are an order of magnitude larger than dynamic RAM.
SUMMARY OF THE INVENTION
In accordance with this invention there is provided a data base searching system which comprises a memory having a plurality of locations for respective items of data, a plurality of passive logic circuits, data lines connecting the memory to respective said passive logic circuits, and a control unit for receiving a query data item and in response thereto producing a group of query signals which are applied simultaneously to all the passive logic circuits in parallel to cause all the passive logic circuits simultaneously and independently of each other to compare the query data item, as represented by the group of query signals, with the data items held in the respective memory locations, each passive logic circuit providing an output indicating if its associated data item has passed a comparative test relative to the query data item.
This system is of relatively simple construction because the comparative tests are carried out in passive logic circuits rather than in microprocessor-based processing elements, and there is no requirement for communication or interrogations sub-systems.
In an embodiment to be described herein, the comparison function is carried out bit-by-bit as the stored data items are passed in serial manner to their respective passive logic circuits and the group of query signals change with changes in the successive bits of the query data item.
The comparison function may take any of several forms, e.g. equality, inequality, greater than, less than, greater than or equal to, less than or equal to.
The outputs from all of the passive logic circuits may be connected to an OR gate, the output of which therefore indicates if one or more of the stored data items, or records, has passed the comparative test being made.
The outputs from the passive logic circuits may be connected to a tally circuit which sums the passive logic circuits which have indicated passing the test.
Preferably a circuit is provided which enables any records which have passed the comparative test to be read out, one at a time, onto a common read-out line. The circuit identifies the first passive logic circuit in a chain which indicates a PASS, and gives that circuit a cursor which allows the associated record to be read out, whilst any others which have PASSED are prevented. Once this record has been read out, the cursor can be moved on to the next logic circuit in the chain which indicates a PASS.
Also in accordance with this invention there is provided a passive logic circuit for use in a data base searching system, the logic circuit having an input for receiving a data item, and inputs for receiving a group of query signals representing a query item of data against which the input data item is to be compared and also defining the type of comparison test to be employed, said logic circuit being arranged for carrying out the comparison test and providing an output signal indicating the result of the comparis
REFERENCES:
patent: 3984821 (1976-10-01), Locke
patent: 4823313 (1989-04-01), Kadota
patent: 4935719 (1990-06-01), McClure
patent: 4958104 (1990-09-01), Yasunda et al.
patent: 5444649 (1995-08-01), Nemirovsky
Parallel Search of Shift Registers, H.H. Ruzicka, IBM Technical Disclosure Bulletin, vol. 17, No. 3, Aug. 1974, pp. 807-808.
Content-Addressable Memory Uses 256-Byte `Superwords`, Sydney M. Lamb, Mini-Micro Systems, Oct. 1983, pp. 237-242.
Wallis, L. "Associative memory calls on the talents of systolic array chip", Electronic Design, pp. 217-226, Dec. 1984.
Choules Jack M.
Gallagher Thomas A.
Gordon David P.
Jacobson David S.
LandOfFree
Data base searching 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 Data base searching system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data base searching system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1520576