Data Base Searching System

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.

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 comparison test.

Preferably the output signal is a simple logic level i.e. single digital bit. Preferably the logic circuit comprises a latch which is set if the comparative test is passed. Preferably the logic circuit comprises another latch which is set if the comparative test is failed at any bit position during the comparison.

The group of query signals may change not only according to the nature of the test being made and whether the current bit of the query data item is a 1 or a 0, but also according to the bit-position: in particular the final bit may require a different group of signals to the preceding bits.

Preferably however, the outputs from the plurality of passive logic circuits are connected to an aggregate circuit which is able to carry out one or more set operations, for example to determine which is the record or records of minimum value, or to determine which is the record or records of maximum value. The circuit is preferably also used to indicate the minimum value, or the maximum value.

Further in accordance with this invention there is provided an aggregate circuit for carrying out an aggregate function in a data base searching system, the aggregate circuit comprising a plurality of data inputs for simultaneously receiving respective items of data in serial manner, a first output for providing a predetermined signal, in respect of each individual bit position, when the bits of all data items received on said inputs have a first value at that bit position, and a second output for providing a second predetermined signal, in respect of each individual bit position, when the bits of all data items received on said inputs have a second value at that bit position.

The above-defined aggregate circuit may be used to perform a number of different aggregate functions yet is of a simple construction.

Embodiments of this invention will now be described by way of examples only and with reference to the accompanying drawings.

FIG. 1 is a schematic block diagram of a data base searching system in accordance with this invention;

FIG. 2 is a block diagram of one of the passive logic circuits of the system shown in FIG. 1;

FIG. 3 is a block diagram of an aggregate circuit of the system;

FIG. 4 is a block diagram of a cursor circuit chain of the system;

FIG. 5 is a block diagram of a read-out circuit of the system; and

FIG. 6 is a block diagram of a circuit which may be included in the system for counting the number of records which have passed a comparison function .

Referring to FIG. 1, a data base searching system in accordance with this invention comprises a memory M having a plurality of locations L for holding respective data items or records: each record comprises a plurality of bits typically divided into a number of fields. The system further comprises a plurality of passive logic circuits LC, one or more for each memory location L. One of the passive logic circuits LC is shown in FIG. 2 and will be described in detail below, but as shown in FIG. 1 each passive logic circuit LC has a DATA input for receiving the record from the respective memory location L in serial manner. The passive logic circuit LC further has four inputs connected to query lines PASS ENABLE, DATA ENABLE, DATA ENABLE and FAIL ENABLE respectively, two further inputs connected to respective lines CONJUNCT and DISJUNCT, and two result outputs PASSED and FAILED. The system further comprises a control element C having respective outputs connected to four query lines PASS ENABLE, DATA ENABLE, DATA ENABLE and FAIL ENABLE: these four query lines, together with the two lines CONJUNCT and DISJUNCT, are connected to all of the passive logic circuits LC in parallel. The control element C has a serial data input COMPARE for a data item with which the records in the locations L are to be compared, and an input OP for an operations code which determines the nature of the operation to be made e.g. a test for equality, inequality, greater than, less than, equal to or greater than, or equal to or less than, a minimum or maximum function, a read or write function, or an advance cursor function (each of which will be referred to later in this description).

In general, when a search is to be carried out, the nature of the comparison to be made (e.g. equality etc) is selected by means of the operations code applied to the input OP of the control element C. The data item being searched for is fed in serial manner to the COMPARE input of the control element C. The bit received at COMPARE and the code received at OP address a map or look-up table to supply signals (logic 1 or 0) on the four query lines, which depend upon the bit value received at COMPARE and the nature of the comparison test to be made: thus as the value of successive bits received at COMPARE changes, the logic signals on the four query lines change.

The passive logic circuits LC operate simultaneously but independently of each other, to compare the records contained in their respective memory locations L with the data item being searched: the nature of the comparison is as determined by the code applied to the input OP of the control element C (i.e. equality, inequality etc). The comparison is effected bit-by-bit as the data item being searched is fed in serial manner into the COMPARE input of control element C and simultaneously the individual records are fed in serial manner from their memory locations L and into the respective passive logic circuits LC.

Each passive logic circuit LC determines whether the record fed from its memory location L satisfies the selected comparison with the search data item. If the comparison is satisfied, the passive logic circuit LC issues a signal (logic 1) on its PASSED output; if the comparison is not satisfied, the passive logic circuit LC issues a signal (logic 1) on its FAILED output.

If the comparison to be made is an equality comparison, it does not matter in what order the bits are compared. But if the comparison is a magnitude comparison, then the comparison must be in order from the most significant to the least significant bit.

The search procedure may consist of each record L in its entirety being compared with the search data item, or one or more selected fields of each record, or one more parts of selected fields of each record.

Optionally, the PASSED outputs of the passive logic circuits LC may all be connected to an OR gate P, an output signal from which therefore indicates if one or more of the records has passed the comparison made in the search. The FAILED outputs of the passive logic circuits LC are all connected to an aggregate circuit MM which will be described in detail below: the DATA from the respective memory locations L are also connected to respective inputs of the aggregate circuit MM.

The system may optionally comprise a tally circuit TC to which the PASSED outputs of all the passive logic circuits LC are connected. This tally circuit TC gives an output of the number of records which have passed the comparison made in the search: this output may be a serial or parallel or combined serial/parallel output. The tally circuit TC can be used to produce a count of selected records. By counting the number of 1's in the selected records at each bit of a numeric field, then shifting that count and accumulating it, the sum of the numeric field across all the selected records can be calculated; e.g. the total invoice values for invoices over a particular period.

FIG. 2 shows one of the passive logic circuits LC in detail. The DATA input and a DATA input are connected to respective AND gates AND-3 and AND-4: the DATA ENABLE and DATA ENABLE query lines are connected respectively to the second inputs to these gates. The outputs of gates AND-3 and AND-4 are connected via an OR gate OR-1 to AND gates AND-1 and AND-2. The query lines PASS ENABLE and FAILED ENABLE are connected to gates AND-1 and AND-2 respectively. Gates AND-1 and AND-2 have third inputs which are connected to the FAILED and PASSED outputs respectively. The outputs of AND-1 and AND-2 are connected to the SET inputs of PASSED and FAILED latches L1 and L2 respectively, which provide the PASSED and FAILED outputs of the logic circuit. The CONJUNCT and DISJUNCT inputs to the logic circuit are connected to the RESET inputs of the latches L1 and L2.

It will be noted that the latches L1 and L2 are cross-connected to render them mutually exclusive, i.e. if one latch is set then the other latch cannot become set. Both latches are reset at the start of a new query, over lines CONJUNCT and DISJUNCT, so placing the circuit in an initial or "UNKNOWN" condition.

When a comparative test being run is an equality test, then at each bit the logic circuit will fail the record L from the memory if its bit value is different from that of the COMPARE item. Thus if the COMPARE bit value is 1, the FAIL ENABLE and DATA ENABLE query lines are asserted, so that the circuit will FAIL if the DATA bit is 0. If the COMPARE bit value is 0, the FAIL ENABLE and DATA ENABLE query lines are asserted, so that the circuit will FAIL if the DATA bit is 1. At the end of the field (i.e. immediately after the least significant bit has been tested), the PASS ENABLE, DATA ENABLE and DATA ENABLE query lines are asserted, so that the logic circuit will be set to the PASSED condition if it has not already been set to the FAILED.

Similarly for an inequality test, if the COMPARE bit is 1, PASS ENABLE and DATA ENABLE are asserted and the circuit PASSES if the DATA bit is 0. If the COMPARE bit is 0, PASS ENABLE and DATA ENABLE are asserted and the circuit PASSES if the DATA bit is 1. At the end of the field, FAIL ENABLE, DATA ENABLE and DATA ENABLE are asserted, so that the circuit now FAILS if not already PASSED.

For the comparative test "greater than", if the COMPARE bit is 0, PASS ENABLE and DATA ENABLE are asserted, so that the circuit PASSES if the DATA bit is 1. If the COMPARE bit is 1, FAIL ENABLE and DATA ENABLE are asserted, so that the circuit FAILS if the DATA bit is 0. At the end of the field, FAIL ENABLE, DATA ENABLE and DATA ENABLE are asserted, so that the circuit FAILS if not already PASSED.

For the comparative test "greater than or equal to", if the COMPARE bit is 0, PASS ENABLE and DATA ENABLE are asserted, so that the circuit PASSES if the DATA bit is 1. If the COMPARE bit is 1, FAIL ENABLE and DATA ENABLE are asserted, so that the circuit FAILS if the DATA bit is 0. At the end of the field, PASS ENABLE, DATA ENABLE and DATA ENABLE are asserted, so that the circuit PASSES if not already FAILED.

For the comparative test "less than", if the COMPARE bit is 0, FAIL ENABLE and DATA ENABLE are asserted, so that the circuit FAILS if the DATA bit is 1. If the COMPARE bit is 1, PASS ENABLE and DATA ENABLE are asserted, so that the circuit PASSES if the DATA bit is 0. At the end of the field, FAIL ENABLE, DATA ENABLE and DATA ENABLE are asserted, so that the circuit FAILS if not already PASSED.

For the comparative test "less than or equal to", if the COMPARE bit is 0, FAIL ENABLE and DATA ENABLE are asserted, so that the circuit FAILS if the DATA bit is 1. If the COMPARE bit is 1, PASS ENABLE and DATA ENABLE are asserted, so that the circuit PASSES if the DATA bit is 0. At the end of the field, PASS ENABLE, DATA ENABLE and DATA ENABLE are asserted, so that the circuit PASSES if not already FAILED.

The system may be required to test whether any record satisfies a comparison in one field and satisfies a comparison in another field. Or it may test whether any record satisfies a comparison in one field or a comparison in another field. In the first case, after a comparison has been made in the first field (or part of a field), the CONJUNCT line is activated to reset the latches L1 of those records which have passed (the latches L2 of those which have failed remaining set), before the required comparison is made in the other field (or part field). In the second case, after comparison has been made in the first field (or part field), the DISJUNCT line is activated to reset the latches L2 of those records which have failed (the latches L1 of those which passed on the first field remaining set).

FIG. 3 shows an aggregate circuit which may be used for carrying out a number of different aggregate functions, and may be used as the aggregate circuit MM of FIG. 1. The aggregate circuit is a passive logic circuit which comprises two AND gates AND-10 and AND-11 providing respective outputs the purpose of which will be described below. Also these outputs are connected to an OR gate OR-2 having an inverter INV-4 at its output. Each input to AND-11 is received from an OR gate OR-4, and each input to AND-10 is received from an OR gate OR-3. Each of the passive logic circuits LC of the system of FIG. 1 has its FAILED output connected to a respective gate OR-3 and to a respective gate OR-4: the DATA input to that logic circuit LC is also connected to OR-4 and the DATA input is connected to OR-3.

The aggregate circuit may be used to carry out a minimum or maximum search, in which it examines the bit positions of the respective records in sequence, masking out the records which fail at each bit position. Then if at a bit position being examined all unmasked records have a 1, a 1 output will be given by AND-11. If at the bit position being compared all unmasked records have a 0, a 1 output will be given by AND-10. If one or more of the unmasked records have a 1 and one or more have a 0 at the bit position being examined, then neither AND gate will give a 1 output and the DISSIMILAR output from INV-4 will be a 1.

Thus if it is desired to search for the record of maximum value, those with a 1 at the bit position being examined are to be kept and those with a 0 are to be failed: the signal on the DISSIMILAR line from INV-4 is included in the code applied to the OP input of control element C, and the mapping in control element C is such as to maintain a 1 on the DATA ENABLE query line: similarly FAIL ENABLE is asserted if a 1 appears on the DISSIMILAR output; the effect of this is to set the FAIL latch L2 of those logic circuits LC receiving a 0 on their DATA inputs (and therefore a 1 on their DATA inputs). In searching for the record or records with the minimum value, those with a 0 at the bit position being examined are to be kept and those with a 1 are to be failed: the control circuit C maintains a 1 on the DATA ENABLE query line; a 1 is placed on the FAIL ENABLE if a 1 appears on the DISSIMILAR output; the effect of this is to set the FAIL latch L2 of those processing elements receiving a 1 on their DATA inputs. After one bit position has been examined, the search moves on to examine the next bit position for those records which have not already failed, and so on. It will be appreciated that the code applied to the OP input of control element C includes the instruction to carry out a MINIMUM or MAXIMUM function.

The aggregate circuit of FIG. 3 also gives directly the minimum or maximum value, via its three outputs. For example when searching for a maximum, if at a given bit position gate AND-11 indicates that all unmasked records have a 1 at that position, or if the DISSIMILAR line indicates that one or more records have a 1 at that position, then clearly the maximum record has a 1 at that position; if instead gate AND-10 indicates that all records have a 0 at that position, then the maximum record must have a 0 at that position.

One important use of the aggregate circuit of FIG. 3 is to sort records into a required order, by means of successive minimum or maximum functions. Another important use is to group records sharing a common value in a particular field.

Also shown in FIG. 3 is an AND gate AND-12 receiving the outputs of the two gates AND-10 and AND-11. If all data records fail the comparison function being carried out, then AND-10 and AND-11 will give a 1 output, and AND-12 will also give a 1 output, indicating that no data records have passed the comparison (NONE FOUND). Equally, if a 0 appears on the output of AND-12, this indicates that one or more records have passed the comparison: this is preferably used instead of OR gate P of FIG. 1.

Referring to FIG. 4, the data base searching system further comprises a chain of cursor circuits C1, C2 . . . , one for each passive logic circuit LC. Each cursor circuit comprises an OR gate OR-6 having an input connected to the PASSED output of the respective passive logic circuits LC, and an input connected to the output of the OR gate of the previous cursor circuit in the chain (or in the case of the first cursor circuit C1, to a DISABLE input. Each cursor circuit further comprises an AND gate AND-20, having one input connected to receive the PASSED output and another input connected to the output of the previous cursor circuit (or to the DISABLE line) via an inverter INV-6.

In order to activate the cursor circuit chain, a 0 is placed on the DISABLE line. If the first passive logic circuit LC does not indicate PASSED, then this 0 is passed on through the OR gate OR-6 to the next cursor circuit in the chain, and so on until the first cursor circuit is reached which has a PASSED signal from its respective passive logic circuit LC: at this circuit in the chain, the AND gate AND-20 will now produce a 1 output, showing that this passive logic circuit LC has the cursor. Subsequent cursor circuits in the chain are prevented from giving a similar indication because the OR gate OR-6 of the circuit with the cursor gives a 1 output at this time. The cursor output is used so that data from the record associated with the respective passive logic circuit LC can be read out, as will be described below. Once the data from this record has been read out, the PASS latch of that passive logic circuit is reset and its FAILED latch is set, and that cursor circuit passes a 0 to the adjacent circuit in the chain, so that the next passive logic circuit with a PASSED indication can be given the cursor for its associated data to be read out in similar fashion.

FIG. 5 shows the read-out circuit. DATA lines from the respective memory locations are connected to a common read-out line ROL via respective gates C1, C2 . . . which are controlled by the cursor outputs from the respective cursor circuits of FIG. 4. So if cursor circuit C2 has the cursor, this will be applied to read-out gate G2 for data to be read-out from the memory location along the common read-out line ROL. When the cursor has subsequently moved on to a later circuit in the cursor chain, the corresponding gate in the chain of read-out gates G1, G2 . . . will be activated for the corresponding data to be read out.

Referring again to FIG. 4, the chain of cursor circuits will operate in the same manner as described above, if the FAILED output of the respective passive logic circuit LC is applied to each gate G1, G2 . . . instead of the corresponding PASSED output. This then enables an arrangement to be used for counting the number of records which have passed the comparison function carried out in the search, as a preferred alternative to including the tally circuit S of FIG. 1. Thus, referring to FIG. 6, a series of AND gates AND-21 may be provided, one for each passive logic circuit LC: a line CAL from the control element C is connected to one input of each gate AND-21, and the CURSOR output from the corresponding cursor circuit e.g. C1; the output of each gate AND-21 is connected to the SET input of the FAILED latch L2 in the respective passive logic circuit LC. Now when a pulse is applied to the line CAL from the control element C, at the cursor circuit which currently holds the cursor, the corresponding gate AND-21 will give an output to set its associated FAILED latch L2 and reset the corresponding PASS latch L1: this effectively removes the input signal (FAILED) from corresponding cursor circuit, so passing the cursor to the next cursor circuit in the chain which has a 1 (FAILED) on its input. By applying successive pulses on the line CAL, the cursor is passed along the chain of cursor circuits in steps, until it reaches the end: the number of pulses which must be applied to achieve this equals the number of cursor circuits having a 1 on their inputs (indicating NOT FAILED) and therefore the number of data records which have PASSED the comparison test.

The system preferably includes arrangements for writing or re-writing data into memory. The write procedure may be in the form read-modify-write, or maskable write: in either case data may be written to the records for all PASSED passive logic elements simultaneously, or to the record for the passive logic element holding the cursor, or to the records which have not PASSED.

It will be appreciated that the memory and passive logic elements may be integrated on a single semiconductor chip, which may additionally include any one or more of the following: the control circuit C, the PASS OR gate P of FIG. 1, the tally circuit TC, the cursor circuit, the read circuit and the write circuit.