Device for associative searching in a sequential data stream composed of data records

• US 4,598,385 A
• Filed: 05/17/1984
• Issued: 07/01/1986
• Est. Priority Date: 09/12/1980
• Status: Expired due to Fees

• Current Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Kessels, Jozef L. W., Vrielink, Hendrik, Schoenmakers, Wijnand J.
• Primary Examiner(s): Thomas, James D.
• Assistant Examiner(s): CLARK, DAVID
• Application Number:
  US06/611,911
• Time in Patent Office: 775 Days
• Field of Search: 364/200, 364/900
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A device for the processing of a data base consisting of a sequence of data records, having a reference memory (140) for a reference data record and a mask memory (142) for a mask data record. In reaction to the successively received data of a data record, these memories can be read in order to activate a comparison. There is provided an indicator element (160) which has a state "provisionally correct" and which is activated by a starting signal produced by the reception of a data record. If the comparison indicates that an impermissible relationship exists between the content of an element of the data record received and the corresponding element of the reference data record, the indicator element is set to the state "incorrect". The data record received is meanwhile stored in a data buffer (100,102). At the end of the reception, the state of the indicator element indicates whether or not the data record may be applied to a user. The data buffer may consist of two buffer sections, each for one complete data record, which alternately operate in a read mode and a write mode.

Claims

1. A data base processor for processing a sequence of data records each of up to a multibyte maximum length, said processor comprising:

a. a first input for at least byte-wide receiving the bytes of a data record from a background memory;

b. a one input, two output selector, fed by said first input for selectively connecting said first input to one of the selector outputs;

c. a two section data buffer, each of the two sections fed by an associated one of the two selector outputs and each section having storage capacity for storing a data record, said data buffer having a control element for selectively controlling the section connected to said first input in a write mode and the other section in a read mode;

d. a reference memory for storing a reference record and having a storage capacity equal to said multibyte maximum length;

e. a mask memory for storing a mask record and having a storage capacity equal to said multibyte maximum length;

f. an address generator for addressing in parallel said two sections, said reference memory and said mask memory with mutually equal addresses;

g. a first comparison element for bitwise and bytewide comparing, under control of an associated mask bit of the mask record read from the mask memory, a data bit received on said first input with an associated reference bit of the reference record read from the reference memory, said first comparison element having a first result output for outputting a mismatch bit upon detection of a mismatch condition;

h. a second comparison element for bitwise and bytewide comparing a plurality of data bits received on said first input with a plurality of multibit reference data in parallel, said second comparison element comprising selection means connected to said first input for selecting said plurality of data bits from a data record received, a membership memory (172) having an address input connected to an output of said selection means for receiving said plurality of data bits in parallel, said membership memory having a first data content on any location addressable by a d-ata byte equal to one of said multibit reference data, and a second data content on any other location, said first data content upon addressing giving a first "correct" signal;

i. a bistable indicator element having a set input for receiving a set signal which sets the bistable indicator element to a "provisionally correct" state upon transition from a data record in said sequence to a next successive record in said sequence, and a reset input connected to said result output to reset said bistable indicator element to an "incorrect" state upon reception of said mismatch bit;

j. interchange means connected to said control element for alternating said read and write modes between said two sections at least upon detecting said transition in combination with either the prevailing "provisionally correct" state indicating a match condition signal for the preceeding data record or upon detecting said first "correct" signal for the data record received in said data buffer most recently;

k. a two input, one output multiplexer fed by said two sections for selectively outputting a data record addressed by said address generator in a read operation under control of said first "correct" signal and said match condition signal.

2. A data base processor as claimed in claim 1, wherein said output multiplexer comprises a combinatorial circuit for combining said first "correct" signal and said match condition signal to generate therefrom a control signal for the multiplexer to output the data record addressed by said address generator in a read operation.

3. A data base processor for processing a sequence of data records each of up to a multibyte maximum length, said processor comprising:

a. a first input for at least byte-wide receiving the bytes of a data record from a background memory;

b. a one input, two output selector, fed by said first input for selectively connecting said first input to one of the selector outputs;

c. a two section data buffer, each of the two sections fed by an associated one of the two selector outputs and each section having storage capacity for storing a data record, said data buffer having a control element for selectively controlling the section connected to said first input in a write mode and the other section in a read mode;

d. a reference memory for storing a reference record and having a storage capacity equal to said multibyte maximum length;

e. a mask memory for storing a mask record and having a storage capacity equal to said multibyte maximum length;

f. an address generator for addressing in parallel said two sections, said reference memory and said mask memory with mutually equal addresses;

g. a first comparison element for bitwise and bytewide comparing, under control of an associated mask bit of the mask record read from the mask memory, a data bit received on said first input with an associated reference bit of the reference record read from the reference memory, said first comparison element having a first result output for outputting a mismatch bit for upon detection of a mismatch condition;

h. an extract generator comprising a second mask memory which is addressed in parallel with said buffer sections, said second mask memory having a first data content on any location corresponding to an element of a data record to be extracted, and a second data content on any other location;

i. a bistable indicator element having a set input for receiving a set signal which sets the bistable indicator element to a "provisionally correct" state upon transition from a data record in said sequence to a next successive record in said sequence, and a reset input connected to said result output to reset said bistable indicator element to an "incorrect" state upon reception of said mismatch bit;

j. interchange means connected to said control element for alternating said read and write modes between said two sections at least upon detecting said transition in combination with the prevailing "provisionally correct" state indicating a match condition signal for the preceeding data record;

k. a two input, one output multiplexer fed by said two sections for selectively outputting the contents of a data record addressed by said address generator in a read operation under control of said match condition signal and under condition of said second mask memory outputting a said first data content.

4. A data base processor as claimed in claim 3, wherein said second mask memory has the same capacity as each of said buffer sections for containing said first or second data content for each data bit, and wherein said output multiplexer comprises a series/parallel converter, whose series input is activated by said first data content to receive a data bit to be extracted and whose parallel output constitutes the output of said data base processor.

5. A data base processor for processing a sequence of data records each of up to a multibyte maximum length, said processor comprising:

a. a first input for at least byte-wide receiving the bytes of a data record from a background memory;

b. a one input, two output selector, fed by said first input for selectively connecting said first input to one of the selector outputs;

c. a two section data buffer, each of the two sections fed by an associated one of the two selector outputs and each section having storage capacity for storing a data record, said data buffer having a control element for selectively controlling the section connected to said first input in a write mode and the other section in a read mode;

d. a reference memory for storing a reference record and having a storage capacity equal to said multibyte maximum length;

e. a mask memory for storing a mask record and having a storage capacity equal to said multibyte maximum length;

f. an address generator for addressing in parallel said two sections, said reference memory and said mask memory with mutually equal addresses;

g. a first comparison element for bitwise and bytewide comparing, under control of an associated mask bit of the mask record read from the mask memory, a data bit received on said first input with an associated reference bit of the reference record read from the reference memory, said first comparison element having a first result output for outputting a mismatch bit upon detection of a mismatch condition;

h. a second comparison element for bitwise and bytewide comparing a plurality of data bits received on said first input with a plurality of multibit reference data in parallel, said second comparison element comprising selection means connected to said first input for selecting said plurality of data bits from a data record received, a membership memory (172) having an address input connected to an output of said selection means for receiving said plurality of data bits in parallel, said membership memory having a first data content on any location addressable by a data byte equal to one of said multibit reference data, and a second data content on any other location, said first data content upon addressing giving a first "correct" signal;

i. a bistable indicator element having a set input for receiving a set signal which sets the bistable indicator element to a "provisionally correct" state upon transition from a data record in said sequence to a next successive record in said sequence, and a reset input connected to said result output to reset said bistable indicator element to an "incorrect" state upon reception of said mismatch bit;

j. interchange means connected to said control element for alternating said read and write modes between said two sections at least upon detecting said transition in combination with either the prevailing "provisionally correct" state indicating a match condition signal for the preceding data record or upon detecting said first "correct" signal for the data record received in said data buffer most recently;

k. a two input, one output multiplexer fed by said two sections for selectively outputting a data record addressed by said address generator in a read operation under control of said first "correct" signal and said match condition signal;

l. means for a projection among a series of n types of data record each record of type j having two mutually exclusive data fields B(j), the sequence of data fields constituting a notional composite data record, said projection implying the generation of a link between data fields B(0) and B(n), wherein there is provided;

a first projection memory (370) having its address input connected to an output of said output multiplexer for successively receiving the contents of data fields B(1), B(3) . . . as successive respective addresses and a data input connected to the output of said output multiplexer for receiving the contents of data field B(0); and

a second projection memory (372) having its address input connected to the output of said output multiplexer for successively receiving the contents of data fields B(2), B(4) . . . as successive respective addresses;

wherein a data output of the first projection memory is connected to a data input of the second projection memory and a data input of the second projection memory is connected to a data input of the first projection memory, said data processor having means for in a first projection step receiving a first type of record and writing the content of data field B(0) of a record of said first type in the first projection memory addressed by the content of data field B(1) of the last mentioned record, for in a second projection step receiving a second type of record, reading the content of data field B(0) in the first projection memory addressed by the content of data field B(1) of a record of said second type and writing the content of data field B(0) read out in the second projection memory addressed by the content of data field B(2) of the last mentioned record, for in a third projection step receiving a third type of record, reading the content of data field B(0) in the second projection memory addressed by the content of data field B(2) of a record of said third type and writing the content of data field B(0) then read out in the first projection memory addressed by the content of data field B(3) of the last mentioned record.

6. A data base processor for processing a sequence of data records each of up to a multibyte maximum length, said processor comprising:

a. a first input for at least byte-wide receiving the bytes of a data record from a background memory;

b. a one input, two output selector, fed by said first input for selectively connecting said first input to one of the selector outputs;

c. a two section data buffer, each of the two sections fed by an associated one of the two selector outputs and each section having storage capacity for storing a data record, said data buffer having a control element for selectively controlling the section connected to said first input in a write mode and the other section in a read mode;

d. a reference memory for storing a reference record and having a storage capacity equal to said multibyte maximum length;

e. a mask memory for storing a mask record and having a storage capacity equal to said multibyte maximum length;

f. an address generator for addressing in parallel said two sections, said reference memory and said mask memory with mutually equal addresses;

g. a first comparison element for bitwise and bytewide comparing, under control of an associated mask bit of the mask record read from the mask memory, a data bit received on said first input with an associated reference bit of the reference record read from the reference memory, said first comparison element having a first result output for outputting a mismatch bit for upon detection of a mismatch condition;

h. an extract generator comprising a second mask memory which is addressed in parallel with said buffer sections, said second mask memory having a first data content on any location corresponding to an element of a data record to be extracted, and a second data content on any other location;

i. a bistable indicator element having a set input for receiving a set signal which sets the bistable indicator element to a "provisionally correct" state upon transition from a data record in said sequence to a next successive record in said sequence, and a reset input connected to said result output to reset said bistable indicator element to an "incorrect" state upon reception of said mismatch bit;

j. interchange means connected to said control element for alternating said read and write modes between said two sections at least upon detecting said transition in combination with the prevailing "provisionally correct" state indicating a match condition signal for the preceding data record;

k. a two input, one output multiplexer fed by said two sections for selectively outputting the contents of a data record addressed by said address generator in a read operation under control of said match condition signal and under condition of said second mask memory outputting a said first data content;

means for a projection among a series of n types of data records, each record of type j having two mutually exclusive data fields B(j), the sequence of data fields constituting a notional composite data record, said projection implying the generation of a link between data fields B(0) and B(n), wherein there is provided;

a first projection memory (370) having its address input connected to an output of said output multiplexer for successively receiving the contents of data fields B(1), B(3) . . . as successive respective addresses and a data input connected to the output of said output multiplexer for receiving the contents of data field B(0); and

a second projection memory (372) having its address input connected to the output of said output multiplexer for successively receiving the contents of data fields B(2), B(4) . . . as successive respective addresses;

wherein a data output of the first projection memory is connected to a data input of the second projection memory and a data input of the second projection memory is connected to a data input of the first projection memory, said data processor having means for in a first projection step receiving a first type of record and writing the content of data field B(0) of a record of said first type in the first projection memory addressed by the content of data field B(1) of the last mentioned record, for in a second projection step receiving a second type of record, reading the content of data field B(0) in the first projection memory addressed by the content of data field B(1) of a record of said second type and writing the content of data field B(0) read out in the second projection memory addressed by the content of data field B(2) of the last mentioned record, for in a third projection step receiving a third type of record, reading the content of data field B(0) in the second projection memory addressed by the content of data field B(2) of a record of said third type and writing the content of data field B(0) then read out in the first projection memory addressed by the content of data field B(3) of the last mentioned record.