Query processor for parallel processing in homogenous and heterogenous databases

• US 5,590,319 A
• Filed: 12/15/1993
• Issued: 12/31/1996
• Est. Priority Date: 12/15/1993
• Status: Expired due to Term

• Current Assignee: Information Builders (iWay Software Company)
• Original Assignee: Information Builders (iWay Software Company)
• Inventors: Cohen, Gerald D., Stout, Ralph L., Edson, Jay H.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US08/167,764
• Time in Patent Office: 1,112 Days
• Field of Search: 395/600, 395/200, 364/401, 364/419, 364/900
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A query processor for parallel processing translates an input query which references data stored in one or more homogenous or heterogenous databases into a plurality of parallel output queries each of which is directed to a single one of the databases or a partition thereof. A runner combines the results of each of the output queries and integrates them into a single coherent answer set.

Claims

1. A query processor for parallel processing of first signals indicative of an input query referencing information stored in one or more databases each of which is accessible through an independent database engine, said input query specifying conditions for an answer set of said information, comprising,

translator means for analyzing said first signals and transforming them into second signals representing queries each of which is directed to one or more base tables,

splitter means for receiving said second signals and producing therefrom third signals corresponding to a plurality of separate queries capable of being executed independently and in parallel, each of said separate queries being compatible with one of said database engines, and

runner means for applying said third signals simultaneously to respective ones of said database engines, receiving, in response thereto, fourth signals generated by each of said database engines which correspond to answer sets for the separate queries, and, producing fifth signals representing an answer set for said input query.

2. A query processor in accordance with claim 1, wherein said translator means further comprises lexical analysis means for transforming said first signals into fifth signals representing the sequence of tokens or words comprising the input query, said translator means further processing said fifth signals to produce said second signals.

3. A query processor in accordance with claim 2, wherein said translator means further comprises parser means for receiving said fifth signals and producing therefrom, sixth signals corresponding to an abstract syntax tree depicting the input query, said translator means further processing said sixth signals to produce said second signals.

4. A query processor in accordance with claim 3, further comprising meta-data means for generating seventh signals indicative of the structures of the database engines and the data accessible by them, wherein said translator means further comprises semantic analyzer means for comparing said sixth signals and said seventh signals, and producing therefrom eighth signals indicative of said input query only if the structures of the database engines and the data accessible by them are compatible with the input query, said translator means further processing said eighth signals to produce said second signals.

5. A query processor in accordance with claim 4, wherein said translator means further comprises normalizer means for receiving said eighth signals and producing therefrom, ninth signals corresponding to said input query cast in terms of base tables and without references to views, said translator means further processing said ninth signals to produce said second signals.

6. A query processor in accordance with claim 5, wherein said translator means further comprises planner means for receiving said ninth signals and producing in response thereto, tenth signals corresponding to one of a plurality of methods for recasting the input query as a family of related, but independently processable, queries, said translator means further processing said tenth signals to produce said second signals.

7. A query processor in accordance with claim 1, further comprising code generator means operatively connected to said splitter means for converting said third signals to correspond to text understood by said database engines.

8. A method of processing an input query referencing information stored in one or more databases each of which is accessible through an independent database engine, said input query specifying conditions for an answer subset of said information which is divisible into a plurality of component subsets, comprising,

producing input query signals representative of said input query,

producing database structure signals indicative of the structures of each one of said one or more databases,

combining said input query signals and said database structure signals to produce a plurality of output query signals representing output queries each of which references the data in one of said databases or a partition thereof, and applying, in parallel, each of said output query signals only to the respective database or partition thereof referenced by its corresponding represented output query.

9. A method in accordance with claim 8, further comprising receiving component answer signals from each of said databases or partitions thereof and combining the component answer signals to produce a resultant answer signal.

10. A method in accordance with claim 9, further comprising comparing said input query signals with said database structure signals and determining whether said output query signals are to be produced, as a function of said comparison.

11. A method in accordance with claim 8 wherein said input query signals, and database structure signals represent respective trees having nodes, and further comprising producing signals indicative of tree representations of said output query signals.

12. A method in accordance with claim 11, further comprising normalizing said input query signals by removing references to views.

13. A method in accordance with claim 12, further comprising converting said signals indicative of trees representing said output queries to signals indicative of text.