Method of data structure extraction for computer systems operating under the ANSI-92 SQL2 outer join protocol

• US 5,625,812 A
• Filed: 11/14/1994
• Issued: 04/29/1997
• Est. Priority Date: 11/14/1994
• Status: Expired due to Term

• Current Assignee: Michael M. David
• Original Assignee: Michael M. David
• Inventors: David, Michael M.
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US08/339,454
• Time in Patent Office: 897 Days
• Field of Search: 395/600, 395/700, 395/650, 395/500
• US Class Current: 713/185
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: Y10S 707/954 Relational
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A method for determining data structure by analyzing an outer join protocol statement used to access the data by sequentially parsing, identifying and storing each token on a push-pop stack. These steps are repeated until a join condition token is identified. The top three data are popped from the push-pop stack and represent a right database root structural node token, a join type token (left or right), and a left database structural root node token. The right and left node structures represented by the popped root node data are linked into one structure using the join type specification and the structural node points specified by the current join condition token. A root node datum representative of the resulting node structure is pushed back onto the push-pop stack. When all tokens have been processed, the node data represented by the resulting root node on the push-pop stack is ordered in accordance with the contained hierarchial data.

Claims

1. A computer system using the ANSI-92 SQL2 outer join protocol for manipulating data contained in the computer system to create and store a resultant database having a known hierarchial data structure represented by an outer join protocol statement, the computer system comprising:

a) a central processing unit coupled with a first memory storage means containing at least a first normalized, relational database, each database in said first storage means including a plurality of data having a known hierarchial data structure capable of being represented in a protocol equivalent to ANSI-92 SQL2 outer join grammar, said central processing unit operating in accord with a programmed set of instructions having a protocol equivalent to ANSI-92 SQL2 outer join grammar;

b) second memory means coupled to said central processing unit having a push-pop stack area and a storage area for nodes;

c) said first memory means further containing a set of instructions for controlling said central processing unit to execute the following steps;

(i) parsing the outer join protocol statement into a plurality of tokens for execution by said central processing unit in accord with the grammar, syntax and semantics, of ANSI-92 SQL2 outer join protocol for controlling the actions of said central processing unit;

(ii) parsing sequentially said tokens from the outer join statement to identify if the token being parsed is a table name, join type (left or right), or a join condition;

(iii) pushing a new root structural node datum with table name onto said push-pop stack in said second memory means as a data item if the token being parsed is identified as a table name;

(iv) pushing a join type datum representative of a left or right join type token onto said push-pop stack in said second memory means as a data item, if the token being parsed is identified as a left or right join type token respectively;

(v) repeating steps (ii) to (iv) until the token being parsed is identified as a join condition token;

(vi) popping the top three data items from said push-pop stack in said second memory means representing a right database root structural node token, a join type token (left or right), and a left database structural root node token;

(vii) linking the right and left node structures represented by the popped root node data into one structure at the structural node points specified by the current join condition token where the lowest level table referenced from said join condition in left and right structures are the link node points and the popped join type (right or left) specifies which substructure assumes the higher level position of the combined structure;

(viii) pushing a root node datum representative of the resulting node structure back onto said push-pop stack in the second memory means;

(ix) repeating steps (ii) through (viii) until all tokens from the outer join statement have been processed; and

,

(x) ordering the node data represented by the resulting root node on said push-pop stack in the second memory means in accordance with the hierarchial data structure and storing the ordered node data in said first memory means.

2. The method of claim 1 further including:

a display terminal connected to said central processing unit for displaying the ordered node data in said first memory means.

3. The method of claim 1 further including:

a printer connected to said central processing unit for printing the ordered node data in said first memory means.

4. In a computer system having a central processing unit coupled with a memory storage means containing at least a first normalized, relational database, each database in said storage means including a plurality of data having a known hierarchial data structure capable of being represented in a protocol equivalent to ANSI-92 SQL2 outer join grammar, the central processing unit operating in accord with a programmed set of instructions having a protocol equivalent to ANSI-92 SQL2 outer join grammar, a method of controlling the central processing unit by using the outer join ANSI-92 SQL2 outer join protocol to create and store a resultant database in the memory means having a known hierarchial data structure represented by an outer join protocol statement, comprising the steps of:

(a) allocating a push-pop stack area in the memory storage means;

(b) parsing the outer join protocol statement into a plurality of tokens for execution by the central processing unit in accord with the grammar, syntax and semantics, of ANSI-92 SQL2 outer join protocol for controlling the actions of the central processing unit;

(c) parsing sequentially said tokens from the outer join statement to identify if the token being parsed is a table name, join type (left or right), or a join condition;

(d) pushing a new root structural node datum with table name onto the push-pop stack as a data item if the token being parsed is identified as a table name;

(e) pushing a join type datum representative of a left or right join type token onto the push-pop stack as a data item, if the token being parsed is identified as a left or right join type token respectively;

(f) repeating steps (c) to (e) until the token being parsed is identified as a join condition token;

(g) popping the top three data items from the push-pop stack representing a right database root structural node token, a join type token (left or right), and a left database structural root node token;

(h) linking the right and left node structures represented by the popped root node data into one structure at the structural node points specified by the current join condition token where the lowest level table referenced from said join condition in left and right structures are the link node points and the popped join type (right or left) specifies which substructure assumes the higher level position of the combined structure;

(i) pushing a root node datum representative of the resulting node structure back onto the push-pop stack in the memory means;

(j) repeating steps (c) through (i) until all tokens from the outer join statement have been processed; and

,

(k) ordering the node data represented by the resulting root node on the push-pop stack in the memory means in accordance with the hierarchial data structure and storing the ordered node data in the memory means.

5. The method of claim 4 further including the step of:

displaying the ordered node data in the memory means on a display terminal.

6. The method of claim 4 further including the step of:

printing the ordered node data in the memory means on a printer.

7. The method of claim 4 wherein said step of parsing the ANSI-92 SQL2 outer join protocol statement into a plurality of tokens further includes the step of:

storing said plurality of tokens in the memory means.

8. In a computer system having a central processing unit coupled with a memory storage means containing at least a first normalized, relational database, each database in said storage means including a plurality of data having a known hierarchial data structure capable of being represented in a protocol equivalent to ANSI-92 SQL2 outer join grammar, the central processing unit operating in accord with a programmed set of instructions having a protocol equivalent to ANSI-92 SQL2 outer join grammar, a method of controlling the central processing unit by using the outer join ANSI-92 SQL2 outer join protocol to create and store a resultant database in the memory means having a known hierarchial data structure represented by an outer join protocol statement, comprising the steps of:

(a) allocating a push-pop stack area in the memory storage means;

(b) parsing sequentially said tokens from the outer join statement to identify if the token being parsed is a table name, join type (left or right), or a join condition;

(c) pushing a new root structural node datum with table name onto the push-pop stack as a data item if the token being parsed is identified as a table name;

(d) pushing a join type datum representative of a left or right join type token onto the push-pop stack as a data item, if the token being parsed is identified as a left or right join type token respectively;

(e) repeating steps (b) to (d) until the token being parsed is identified as a join condition token;

(f) popping the top three data items from the push-pop stack representing a right database root structural node token, a join type token (left or right), and a left database structural root node token;

(g) linking the right and left node structures represented by the popped root node data into one structure at the structural node points specified by the current join condition token where the lowest level table referenced from said join condition in left and right structures are the link node points and the popped join type (right or left) specifies which substructure assumes the higher level position of the combined structure;

(h) pushing a root node datum representative of the resulting node structure back onto the push-pop stack in the memory means;

(i) repeating steps (b) through (h) until all tokens from the outer join statement have been processed; and

,

(j) ordering the node data represented by the resulting root node on the push-pop stack in the memory means in accordance with the hierarchial data structure and storing the ordered node data in the memory means.

9. The method of claim 8 further including the step of:

parsing the outer join protocol statement into a plurality of tokens for execution by the central processing unit in accord with the grammar, syntax and semantics, of ANSI-92 SQL2 outer join protocol for controlling the actions of the central processing unit.

10. The method of claim 8 further including the step of:

displaying the ordered node data in the memory means on a display terminal.

11. The method of claim 8 further including the step of:

printing the ordered node data in the memory means on a printer.

12. The method of claim 8 wherein said step of parsing the ANSI-92 SQL2 outer join protocol statement into a plurality of tokens further includes the step of:

storing said plurality of tokens in the memory means.