Relational database system having a network for transmitting colliding packets and a plurality of processors each storing a disjoint portion of database

• US 5,006,978 A
• Filed: 09/07/1988
• Issued: 04/09/1991
• Est. Priority Date: 04/01/1981
• Status: Expired due to Term

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Teradata Corporation
• Inventors: Neches, Philip M.
• Primary Examiner(s): Lee, Thomas C.
• Application Number:
  US07/241,301
• Time in Patent Office: 944 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 340/825.50, 340/825.52, 340/825.02, 370/85, 370/60, 370/94, 379/269, 371/8.1, 371/8.2, 371/10.1, 371/10.2
• US Class Current: 718/102
• CPC Class Codes: G06F 11/202 where processing functionality is redundant redundant communication control functionality G06F11/2005, redundant storage control functionality G06F11/2089
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 15/161 Computing infrastructure, e.g. computer clusters, blade chassis or hardware partitioning casings, cabinets, racks or drawers for data centers H05K5/00
• CPC Class Codes: G06F 15/17368 non hierarchical topologies
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: Y10S 707/99939 Privileged access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A multiprocessor system intercouples the processors with an active logic network having a plurality of priority determining nodes. Messages applied concurrently to the network in groups are sorted, using the data content of the messages, to a single or common priority message which is distributed to all the processors with a predetermined total network delay time. Losing messages are again retried concurrently in groups at a later time. Message routing is determined by local acceptance or rejection of messages at the processors, based upon destination data in the messages. All messages occupy places in a coherent priority scheme and are transferred in contending groups with prioritization on the network. Using data, status, control and response messages, and different multiprocessor modes, the system is particularly suited for configuration in a relational data base machine having capability for maintaining an extended data base and handling complex queries.

Claims

1. A relational data base machine for processing message packets comprising the combination of:

(a) a plurality of processors, each of the plurality of processors generating and receiving said message packets having a data content, each said message packet defining a task, each of the plurality of processors containing a portion of the relational data base;

(b) a multiple terminal active network having a plurality of bidirectional active nodes and merging at an apex node, each said active node including means responsive to the data content of said message packets for determining priority in simultaneous collisions between two competing said message packets;

(c) at least two like processors coupled to different terminals of the network, the like processors each including means responsive to the message packets for determining whether the task defined by the message packet is appropriate for that processor; and

(d) a plurality of secondary storages, each coupled to a different one of said processors and each having a disjoint primary subset of the relational data base and a different backup subset of the relational data base, the subsets being distributed in accordance with a predetermined pattern.

2. The invention as set forth in claim 1 above, wherein the active nodes each includes means for uninterrupted transmission of the one message packet having priority at that node, and means for relaying loss of priority to said processors losing in contention at that node and at nodes closer to the apex node.

3. The invention as set forth in claim 2 above, wherein the network comprises a pair of parallel network trees each coupled to all of the processors, such that the network redundancy and the data base redundancy, together with the distribution of the data subsets within the data base, provide security against loss of data and system downtime due to malfunction of individual units within the data base machine.

4. The invention as set forth in claim 1 above, wherein the processors generate processed message packets as to a given subtask differing in data content such that the message packet related to a primary subset receives priority over the message packet related to a backup subset if both are transmitted onto the network.

5. The invention as set forth in claim 4 above, wherein the processors provide destination identification in the message packets, and responses to received message packets, such that processors intercommunicate via the prioritizing network.

6. A processing system for data base management comprising the combination of:

(a) at least one processor providing information packets comprising subtasks related to a data base task;

(b) a number of microprocessor means, at least some of which comprise access module processors including storage means having;

(i) a primary data storage containing an exclusive disjoint fraction of the data base and providing processed information packets,

(ii) backup data storage containing disjoint fractions of the data base and no commonality with the primary data storage at the same storage means,

the microprocessor means including means responsive to the information packets themselves for determining whether a received information packet is relevant to the associated fraction of the data base, the means responsive to the information packets themselves comprising lookup table means responsive to the information packet;

(c) bidirectional active bus means comprising;

(i) an information packet selection network coupled to the individual microprocessor means, the active bus means including means for selecting multiple concurrent information packets flowing in an upstream direction and redirecting an ultimately selected packet in a downstream direction to the microprocessor means,

(ii) a plurality of intercoupled active node means, each active node having a first and second downstream port and an upstream port, the upstream port being connected to a downstream port of a successive upstream node, each including means for determining priority between information packets moving in the upstream direction,

(iii) a redundant structure of node means and interconnections providing alternate branching inputs to each of the microprocessor means; and

(d) interface microprocessor means coupled to the processor and to the divergent end of the active bus means to transfer information packets to and from the processor, whereby the system can pace the rates of operation of the processor, the active bus means and the microprocessor means, wherein the processor includes a channel data base machine and the interface processor means includes a channel interface coupled to the processor bus and a separate interface coupled to the active bus means.

7. The invention as set forth in claim 6 above, wherein the microprocessor means provide processed information packets appropriate to the primary and backup data portions of the data base to which they are assigned, the processed information packets containing merge criteria such that the active bus means gives priority to the primary data against competing backup data.

8. A data base management system for a digital computer system generating a plurality of requests pertaining to a data file, comprising:

a plurality of processors, each including a relational data storage having a primary disjoin portion of the data base, and a backup portion comprising subparts of each of a number of the primary portions at the other processors;

interface means coupled to the digital computer system for responding to a request from the digital computer system by generating an information packet containing a relational characterization;

the processors each containing means responsive to the relational characterizations for processing only those information packets related to its portion of the data base to generate responsive packets; and

network means coupling the interface means to the processors for prioritizing competing and colliding information packets and for delivering the prioritized information packets concurrently to the processors whereby data base manipulation is effected by each said processor independently of the status of other said processors.

9. The invention as set forth in claim 8 above, wherein the network means intercouples all said processors and includes means for delivering the prioritized information packets from any one of said interface means of said processors to all said interface means and said processors at a predetermined delay regardless of the origination and destination points.

10. The invention as set forth in claim 9 above, wherein the processors include means responsive to received said information packets for revising local portions of the data base, whereby inter-processor communications via the network means are used to maintain the integrity of the data file.

11. The invention as set forth in claim 10 above, wherein the information packets contain priority determining sequences, and wherein the processors include means for repeatedly regenerating a packet at successive time intervals until it has been delivered.

12. The invention as set forth in claim 11 above, wherein the processors each includes table lookup means responsive to the relational characterizations for identifying the packets intended for that processor.

13. The invention as set forth in claim 12 above, wherein the table lookup means comprises random access memory means responsive to the relational characterizations for the primary and backup files for that processor, and wherein the network means comprises bidirectional bus means having a plurality of active nodes.

14. A data base management system comprising:

at least one host computer system for executing application programs and generating information packets for the system, the host computer requiring access to different ones of a number of data base files;

an active bidirectional communications network having a plurality of decisional Y node circuits defining a tree having a plurality of branches at its divergent end, each of the Y node circuits including means for prioritizing competing and colliding information packets applied thereto;

a number of access module processors coupled to some of the branches of the communications network;

a number of secondary data storages distributed among the different access module processors and each having at least a unique subset of the data base file, the associated access module processor including means responding to receiving one of said information packets to recognize the presence of an appropriate data subset and to generate a processed information packet using the associated secondary data storage;

a number of interface processors coupled to others of the branches of the communications network and each coupled to at least one of a plurality of main frame computers for responding to the content of said information packets to provide data in the information packets identifying data base subsets, and to control interfacing with said at least one of said main frame computers; and

wherein the access module processors and the interface processors each includes means for coupling competing information packets concurrently to the network, whereby tasks are performed on a priority basis but without extensive overhead functions being required.

15. A system as set forth in claim 14 above, wherein the decisional Y node circuits are arranged with redundant circuits and interconnections defining two independent networks.

16. A system as set forth in claim 15 above, wherein each said data storage includes at least a portion of a subset of the data base file redundant to the contents of other said data storages.

17. A system as set forth in claim 16 above, wherein the Y node circuits comprise circuit means for transferring the information packets moving in a downstream direction on the communications network, and for concurrently giving priority to one of two information packets moving in an upstream direction in accordance with a predetermined rule related to the data content within the information packets.