Patent US5875334A successfully refreshed from Google Patents.
US5875334A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System, method, and program for extending a SQL compiler for handling control statements packaged with SQL query statements
Assignee: International Business Machines Corp
•
Filing: 1995-10-27
•
Granted: 1999-02-23
•
Expires: 2015-10-27
Abstract
Abstract This invention provides an integrated compiler for compiling SQL3 control statements having procedural, i.e., control, information packaged together with query, i.e., non-procedural, statements. A query extractor contained within the parser extracts the query statement from the control statement leaving a control skeleton. The query statement is processed as usual through a query compiler for generating executable plans with the exception that the name resolution function for resolving variables is modified for looking up local variables. This modification takes into account the mapping of local and host variables to create a unification of local and host variables. The control skeleton is processed through a control analyzer which generates a representation of the control flow and a scope and symbol table. The control analyzer also unifies the local and host variables. A plan synthesizer then takes as input the control flow information, symbol tables, and individual executable plans for the query statements and generates a meta-plan comprising a merger of a top level plan for the control skeleton and sub-plans representing the executable plans of the query statement. Therefore, this invention provides a uniform way of treating local and host variables, provides an efficient way of performing bind-in/bind-out processes, creates a single execution plan requiring only a single run-time interpreter, and requires minimum enhancements to existing SQL2 compilers. In addition, this invention enables the application of global optimization techniques for optimizing both the control aspects and query aspects of the original control statement.
Inventors
- 👤 Jyh-Herng Chow
- 👤 You-Chin (Gene) Fuh
- 👤 Nelson Mendonca Mattos
- 👤 Brian T. Tran
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 10:55
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443; G06F16/00; G06F16/20; G06F16/24; G06F16/242; G06F16/2433; G06F16/2443; G06F16/245; G06F16/2452; G06F16/24524; G06F8/42; G06F8/427; G06F8/43; G06F8/433
Claims Analysis
Total Claims: 65
Claim 1
Independent Claim
136 words
A system for compiling a database language statement having a procedural part packaged together with at least one declarative part, the system comprising: a query extractor for separating the procedural part from the declarative part whereby the procedural part, separated from the declarative part, is a control skeleton; an integrated compiler having a query compiler and a control analyzer wherein said control analyzer is specialized for compiling the procedural part; the query compiler compiling the at least one declarative part and generating an executable plan; the control analyzer generating a control flow representation of control flow information of the control skeleton; and a plan synthesizer for synthesizing the output from the query compiler and the control analyzer by merging a code sequence generated from the control flow information of the control skeleton with the executable plan.
Claim 2
Independent Claim
136 words
A system for compiling a database language statement having a procedural part packaged together with at least one declarative part, the system comprising: a query extractor for separating the procedural part from the declarative part whereby the procedural part, separated from the declarative part, is a control skeleton; an integrated compiler having a query compiler and a control analyzer wherein said control analyzer is specialized for compiling the procedural part; the query compiler compiling the at least one declarative part and generating an executable plan; the control analyzer generating a control flow representation of control flow information of the control skeleton; and a plan synthesizer for synthesizing the output from the query compiler and the control analyzer by merging a code sequence generated from the control flow information of the control skeleton with the executable plan.
Claim 3
Dependent Claim
27 words
The system of claim 1 wherein the control skeleton comprises the procedural part of the database language statement and a token in place of the declarative part.
Claim 4
Dependent Claim
18 words
The system of claim 1 wherein the control flow representation preserves a semantic of the database language statement.
Claim 5
Dependent Claim
17 words
The system of claim 1 wherein the query extractor resides in a parser of the query compiler.
Claim 6
Dependent Claim
21 words
The system of claim 1 wherein the query compiler generates a representation of the declarative part independently from the control skeleton.
Claim 7
Dependent Claim
55 words
The system of claim 1 wherein the query compiler performs a name resolution function to determine a meaning of a local variable and invokes a symbol table look up routine to return a host variable name to a semantic routine of the query compiler if the name resolution function fails to find a column name.
Claim 8
Dependent Claim
36 words
The system of claim 1 further comprising at least one scope and a symbol table into which said control skeleton is fed for resolving local variables declared inside a compound statement used to create the scope.
Claim 9
Dependent Claim
41 words
The system of claim 1 wherein the control analyzer generates at least one scope and a symbol table from the control skeleton, populates a host variable table with each local variable, and populates an outer-most symbol table with each host variable.
Claim 10
Dependent Claim
40 words
The system of claim 8 wherein the query compiler handles all variables through the host variable table populated with host variables and local variables and a code generator allocating storage for the host and local variables from the symbol table.
Claim 11
Dependent Claim
30 words
The system of claim 1 wherein the plan synthesizer emits a global bind-in operator at the beginning of the executable plan to move host variable values into a SQL runtime.
Claim 12
Dependent Claim
31 words
The system of claim 1 wherein the plan synthesizer emits a global bind-out operator at the end of the executable plan to move host variable values out of a SQL runtime.
Claim 13
Dependent Claim
32 words
The system of claim 7 wherein the plan synthesizer utilizes information from the at least one scope, the symbol table, the control flow information and each executable plan for generating the meta-plan.
Claim 14
Dependent Claim
37 words
The system of claim 1 further comprising a global optimizer applying a procedural language optimization technique to the control skeleton sequence whereby the at least one declarative part is treated as a black box with certain characteristics.
Claim 15
Dependent Claim
25 words
The system of claim 5 wherein the representation of the declarative part is extended with a set of procedural nodes for the control flow representation.
Claim 16
Dependent Claim
29 words
The system of claim 1 wherein the control analyzer generates at least one scope and a symbol table when a compound statement is encountered in the database language statement.
Claim 17
Dependent Claim
28 words
The system of claim 1 wherein the control analyzer performs a control flow and data flow analysis for feedback to the query compiler in performing a global optimization.
Claim 18
Dependent Claim
32 words
The system of claim 16 wherein the control flow analysis is performed by traversing the control skeleton, and the plan synthesizer and query compiler operate interactively to generate an optimized executable meta-plan.
Claim 19
Dependent Claim
34 words
The system of claim 15 wherein the control analyzer utilizes the control flow representation, the at least one scope, and the symbol table to feed back information to the query compiler for global optimization.
Claim 20
Dependent Claim
18 words
The system of claim 1 wherein the control analyzer and query compiler operate interactively to perform global optimization.
Claim 21
Dependent Claim
15 words
The system of claim 1 wherein the control analyzer unifies local variables and host variables.
Claim 22
Independent Claim
160 words
A system for compiling a database language statement having a procedural part packaged with at least one declarative part, the system comprising: a parser for separating the procedural part from the declarative part whereby the procedural part, separated from the declarative part, is a control skeleton, and for generating a first representation of the declarative part and a control flow representation of the control skeleton; an analyzer creating a table dependency graph from each declarative part; a threaded code generator for generating a code sequence representing the control flow of the control skeleton; a query rewrite applying rewrite rules to the declarative part based upon information from the analyzer to rewrite a query for each declarative part; a query optimizer optimizing the code sequence and the plan for the declarative part based upon the information from the analyzer; and a plan synthesizer synthesizing a final plan from an optimized code sequence and an optimized execution plan from the query optimizer.
Claim 23
Independent Claim
160 words
A system for compiling a database language statement having a procedural part packaged with at least one declarative part, the system comprising: a parser for separating the procedural part from the declarative part whereby the procedural part, separated from the declarative part, is a control skeleton, and for generating a first representation of the declarative part and a control flow representation of the control skeleton; an analyzer creating a table dependency graph from each declarative part; a threaded code generator for generating a code sequence representing the control flow of the control skeleton; a query rewrite applying rewrite rules to the declarative part based upon information from the analyzer to rewrite a query for each declarative part; a query optimizer optimizing the code sequence and the plan for the declarative part based upon the information from the analyzer; and a plan synthesizer synthesizing a final plan from an optimized code sequence and an optimized execution plan from the query optimizer.
Claim 24
Dependent Claim
36 words
The system of claim 21 wherein the analyzer associates each edge of the control flow representation with a cost by measuring a frequency of an execution of a corresponding query node in the control flow representation.
Claim 25
Independent Claim
237 words
A system for compiling a database language statement having a procedural part packaged together with at least one declarative part, the database language statement embedded in an application program for querying a database managed by a server, the system comprising: an integrated compiler having a first compilation path for compiling each declarative part apart from the procedural part and having a second compilation path for processing the procedural part; a control analyzer, in the second compilation path, for analyzing a control flow of said procedural part; populating a host variable table with local variables, and creating a symbol table of local and host variables; a query compiler, in the first compilation path for handling all local variables as host variables from the host variable table populated with local variables in compiling each declarative part into an executable plan; a threaded code generator, in the second compilation path, for generating a threaded code sequence of the control flow of the procedural part; a plan synthesizer for embedding each executable plan into the threaded code sequence thereby creating a meta-plan, and allocating storage for local and host variables from the symbol table during code generation time; a run time interpreter recursively executing each execution plan embedded within the threaded code sequence within the meta-plan wherein the meta-plan has one bind-in operator and one bind-out operator for communicating with the application input and output values of local and host variables.
Claim 26
Independent Claim
237 words
A system for compiling a database language statement having a procedural part packaged together with at least one declarative part, the database language statement embedded in an application program for querying a database managed by a server, the system comprising: an integrated compiler having a first compilation path for compiling each declarative part apart from the procedural part and having a second compilation path for processing the procedural part; a control analyzer, in the second compilation path, for analyzing a control flow of said procedural part; populating a host variable table with local variables, and creating a symbol table of local and host variables; a query compiler, in the first compilation path for handling all local variables as host variables from the host variable table populated with local variables in compiling each declarative part into an executable plan; a threaded code generator, in the second compilation path, for generating a threaded code sequence of the control flow of the procedural part; a plan synthesizer for embedding each executable plan into the threaded code sequence thereby creating a meta-plan, and allocating storage for local and host variables from the symbol table during code generation time; a run time interpreter recursively executing each execution plan embedded within the threaded code sequence within the meta-plan wherein the meta-plan has one bind-in operator and one bind-out operator for communicating with the application input and output values of local and host variables.
Claim 27
Independent Claim
90 words
A method for compiling a database language statement having a procedural part packaged together with at least one declarative part, said method comprising: separating the procedural part from the declarative part; generating, by a query compiler, an executable plan for each of the at least one declarative part; generating a threaded code sequence based upon control flow information from the procedural part; and embedding the executable plan for each of the at least one declarative part as a sub plan into the threaded code sequence to create an executable meta-plan.
Claim 28
Independent Claim
90 words
A method for compiling a database language statement having a procedural part packaged together with at least one declarative part, said method comprising: separating the procedural part from the declarative part; generating, by a query compiler, an executable plan for each of the at least one declarative part; generating a threaded code sequence based upon control flow information from the procedural part; and embedding the executable plan for each of the at least one declarative part as a sub plan into the threaded code sequence to create an executable meta-plan.
Claim 29
Dependent Claim
35 words
The method of claim 24 wherein the step of separating the procedural part from the declarative part further comprises replacing the declarative part with a token in the procedural part to create a control skeleton.
Claim 30
Dependent Claim
26 words
The method of claim 24 further comprising: invoking, recursively, an interpreter, when a sub plan is encountered at runtime, for an execution of the sub plan.
Claim 31
Dependent Claim
28 words
The method of claim 24 further comprising: populating a host variable table with local variables for use by the query compiler in handling all variables as host variables.
Claim 32
Dependent Claim
39 words
The method of claim 27 further comprising: populating, during a parsing phase, a symbol table with local variables and host variables and allocating storage, during the generation of the threaded code sequence, for the local variables and host variables.
Claim 33
Dependent Claim
18 words
The method of claim 28 further comprising: executing the meta-plan utilizing one bind-in operator and one bind-out operator.
Claim 34
Dependent Claim
35 words
The method of claim 24 further comprising: applying a procedural language optimization technique to the threaded code sequence whereby the at least one declarative part is treated as a black box with a certain characteristic.
Claim 35
Independent Claim
121 words
A method for compiling a database language statement having a procedural part packaged together with at least one declarative part, the method comprising: separating the database language statement into the procedural part and the declarative part; utilizing a query compilation path, for the declarative part, for generating an executable plan for each one of the at least one declarative part; utilizing a second compilation path, separate from said query compilation path, for the procedural part, for generating control flow information and a threaded code sequence based upon the control flow information; and synthesizing a final execution plan for the database language statement from the threaded code sequence and the executable plan for each one of the at least one declarative part.
Claim 36
Independent Claim
121 words
A method for compiling a database language statement having a procedural part packaged together with at least one declarative part, the method comprising: separating the database language statement into the procedural part and the declarative part; utilizing a query compilation path, for the declarative part, for generating an executable plan for each one of the at least one declarative part; utilizing a second compilation path, separate from said query compilation path, for the procedural part, for generating control flow information and a threaded code sequence based upon the control flow information; and synthesizing a final execution plan for the database language statement from the threaded code sequence and the executable plan for each one of the at least one declarative part.
Claim 37
Dependent Claim
104 words
The method of claim 31 wherein the step of separating the database language statement further comprises: transforming a SET statement into an equivalent query statement thereby directly translating the procedural part to the declarative part; extracting a search condition of a procedural part and replacing the search condition with a compiler generated local variable and, based upon the search condition, assigning a first representation for true or a second representation for false to the local variable, thereby creating a pure procedural part; and replacing each declarative part with a token to create a control skeleton for the procedural part of the database language statement.
Claim 38
Dependent Claim
22 words
The method of claim 31 wherein the first compilation path and second compilation path interchange information to perform a global optimization technique.
Claim 39
Independent Claim
130 words
A method for compiling a database language statement having a procedural part packaged together with at least one declarative part, the method comprising: transforming a SET statement into an equivalent query statement thereby directly translating the procedural part to a pure declarative part; extracting a search condition of a procedural part and replacing the search condition with a compiler generated local variable and, based upon the search condition, assigning a first representation for true or a second representation for false to the local variable, thereby creating a pure procedural part; replacing each declarative part with a token to create a control skeleton representing the procedural part of the database language statement; and compiling each declarative part through a query compiler and processing the control skeleton separate from the declarative part.
Claim 40
Independent Claim
130 words
A method for compiling a database language statement having a procedural part packaged together with at least one declarative part, the method comprising: transforming a SET statement into an equivalent query statement thereby directly translating the procedural part to a pure declarative part; extracting a search condition of a procedural part and replacing the search condition with a compiler generated local variable and, based upon the search condition, assigning a first representation for true or a second representation for false to the local variable, thereby creating a pure procedural part; replacing each declarative part with a token to create a control skeleton representing the procedural part of the database language statement; and compiling each declarative part through a query compiler and processing the control skeleton separate from the declarative part.
Claim 41
Independent Claim
88 words
A method of compiling a database language statement having a procedural part packaged together with at least one declarative part, the method comprising: separating the procedural part and the declarative part into a control skeleton and the declarative part; compiling, through a first compilation path through a query compiler, each declarative part into an execution plan; generating, separately from said first compilation path, a threaded code sequence representing a control flow of the control skeleton; and synthesizing the threaded code sequence and each execution plan into one meta-plan.
Claim 42
Independent Claim
88 words
A method of compiling a database language statement having a procedural part packaged together with at least one declarative part, the method comprising: separating the procedural part and the declarative part into a control skeleton and the declarative part; compiling, through a first compilation path through a query compiler, each declarative part into an execution plan; generating, separately from said first compilation path, a threaded code sequence representing a control flow of the control skeleton; and synthesizing the threaded code sequence and each execution plan into one meta-plan.
Claim 43
Independent Claim
110 words
A system for compiling a database language statement having a procedural part packaged together with at least one declarative part, said system comprising: means for separating the procedural part from the declarative part; means for processing the declarative part through a query compiler to generate an executable plan for each of the at least one declarative part; means, separate from the query compiler, for analyzing control flow information of the procedural part and generating a threaded code sequence based upon the control flow information; and means for merging the executable plan for each of the at least one declarative part into the threaded code sequence to create an executable meta-plan.
Claim 44
Independent Claim
110 words
A system for compiling a database language statement having a procedural part packaged together with at least one declarative part, said system comprising: means for separating the procedural part from the declarative part; means for processing the declarative part through a query compiler to generate an executable plan for each of the at least one declarative part; means, separate from the query compiler, for analyzing control flow information of the procedural part and generating a threaded code sequence based upon the control flow information; and means for merging the executable plan for each of the at least one declarative part into the threaded code sequence to create an executable meta-plan.
Claim 45
Dependent Claim
18 words
The system of claim 36 further comprising means for treating local variables as if they were host variables.
Claim 46
Dependent Claim
51 words
The system of claim 37 further comprising: means for including local variables along with the host variables in a host variable table generated by the query compiler; and means for allocating storage in the meta-plan as a persistent store for allowing values of local variables to exist across multiple declarative parts.
Claim 47
Independent Claim
107 words
A system for compiling a database language statement having a procedural part packaged together with at least one declarative part, said system comprising: means for separating the procedural part from the declarative part; means for integrating a compilation of the declarative part in a first compilation path and a processing of the procedural part in a second path; means, in the first compilation path, for compiling each declarative part into an execution plan; means, in the second path for generating a threaded code sequence representing a control flow of the procedural part; and means for synthesizing the threaded code sequence and each execution plan into a meta-plan.
Claim 48
Independent Claim
107 words
A system for compiling a database language statement having a procedural part packaged together with at least one declarative part, said system comprising: means for separating the procedural part from the declarative part; means for integrating a compilation of the declarative part in a first compilation path and a processing of the procedural part in a second path; means, in the first compilation path, for compiling each declarative part into an execution plan; means, in the second path for generating a threaded code sequence representing a control flow of the procedural part; and means for synthesizing the threaded code sequence and each execution plan into a meta-plan.
Claim 49
Dependent Claim
23 words
The system of claim 39 wherein the means for compiling each declarative part further comprises means for treating local variables as host variables.
Claim 50
Dependent Claim
37 words
The system of claim 40 wherein the means for treating local variables as host variables further comprises means for populating a host variable table with local variables for use by said means for compiling each declarative part.
Claim 51
Dependent Claim
43 words
The system of claim 39 further comprising means for populating a table with both local and host variables during a parsing phase of the database language statement and means for allocating storage for all variables in the table during a generation of code.
Claim 52
Dependent Claim
20 words
The system of claim 39 further comprising means for generating one bind-in operator and one bind-out operator for the meta-plan.
Claim 53
Dependent Claim
15 words
The system of claim 39 further comprising means for globally optimizing the threaded code sequence.
Claim 54
Dependent Claim
40 words
The system of claim 39 further comprising means, in the second path, for performing a control flow analysis of the procedural part and means for feeding the analysis to the means for compiling the declarative part for performing global optimization.
Claim 55
Independent Claim
174 words
A system for compiling a database language statement having a procedural part packaged with at least one declarative part, the system comprising: means for separating the procedural part from the declarative part into a control skeleton and the at least one declarative part; means for generating a first representation of the declarative part and generating a control flow representation of a control flow of the control skeleton; means for performing an analysis on the control flow representation and creating a table dependency graph from each declarative part; means for generating a code sequence representing the control flow of the control skeleton; means for applying rewrite rules to the declarative part, based upon information from the means for performing an analysis, for generating a plan for each declarative part; means for optimizing the code sequence and the plan for the declarative part based upon the information from the means for performing an analysis; and means for synthesizing a final plan from an optimized code sequence and an optimized execution plan from the means for optimizing.
Claim 56
Independent Claim
174 words
A system for compiling a database language statement having a procedural part packaged with at least one declarative part, the system comprising: means for separating the procedural part from the declarative part into a control skeleton and the at least one declarative part; means for generating a first representation of the declarative part and generating a control flow representation of a control flow of the control skeleton; means for performing an analysis on the control flow representation and creating a table dependency graph from each declarative part; means for generating a code sequence representing the control flow of the control skeleton; means for applying rewrite rules to the declarative part, based upon information from the means for performing an analysis, for generating a plan for each declarative part; means for optimizing the code sequence and the plan for the declarative part based upon the information from the means for performing an analysis; and means for synthesizing a final plan from an optimized code sequence and an optimized execution plan from the means for optimizing.
Claim 57
Dependent Claim
144 words
An article of manufacture having a computer usable medium having computer readable program code means embodied therein for enabling a compilation of a database language statement having a procedural part packaged together with at least one declarative part, said article of manufacture comprising: means for enabling a separation of the procedural part from the declarative part; means for enabling an integrated compilation of the declarative part in a first compilation path and a processing of the procedural part in a second path; means for enabling, in the first compilation path, a compilation of each declarative part into an execution plan by a query compiler; means for enabling, in the second path, a generation of a threaded code sequence representing a control flow of the procedural part; and means for enabling a merging of the threaded code sequence and each execution plan into a meta-plan.
Claim 58
Dependent Claim
144 words
An article of manufacture having a computer usable medium having computer readable program code means embodied therein for enabling a compilation of a database language statement having a procedural part packaged together with at least one declarative part, said article of manufacture comprising: means for enabling a separation of the procedural part from the declarative part; means for enabling an integrated compilation of the declarative part in a first compilation path and a processing of the procedural part in a second path; means for enabling, in the first compilation path, a compilation of each declarative part into an execution plan by a query compiler; means for enabling, in the second path, a generation of a threaded code sequence representing a control flow of the procedural part; and means for enabling a merging of the threaded code sequence and each execution plan into a meta-plan.
Claim 59
Independent Claim
65 words
A system for compiling a database language statement having a procedural part packaged together with at least one declarative part, the system comprising: means for compiling each declarative part into an executable plan; means for generating a threaded code sequence of a control flow of the procedural part; and means for embedding each executable plan into the threaded code sequence as a single executable meta-plan.
Claim 60
Independent Claim
65 words
A system for compiling a database language statement having a procedural part packaged together with at least one declarative part, the system comprising: means for compiling each declarative part into an executable plan; means for generating a threaded code sequence of a control flow of the procedural part; and means for embedding each executable plan into the threaded code sequence as a single executable meta-plan.
Claim 61
Dependent Claim
18 words
The system of claim 48 wherein the single executable meta-plan has one bind-in operator and one bind-out operator.
Claim 62
Independent Claim
54 words
A method for compiling a database language statement having a procedural part packaged together with at least one declarative part, the method comprising: compiling each declarative part into an executable plan; generating a threaded code sequence of a control flow of the procedural part; and embedding each executable plan into the threaded code sequence.
Claim 63
Independent Claim
54 words
A method for compiling a database language statement having a procedural part packaged together with at least one declarative part, the method comprising: compiling each declarative part into an executable plan; generating a threaded code sequence of a control flow of the procedural part; and embedding each executable plan into the threaded code sequence.
Claim 64
Dependent Claim
94 words
An article of manufacture having a computer usable medium having computer readable program code means embodied therein for enabling a compilation of a database language statement having a procedural part packaged together with at least one declarative part, said article of manufacture comprising: means for enabling a compilation of each declarative part into an executable plan; means for enabling a generation of a threaded code sequence of a control flow of the procedural part; and means for enabling an embedding of each executable plan into the threaded code sequence as a single executable meta-plan.
Claim 65
Dependent Claim
94 words
An article of manufacture having a computer usable medium having computer readable program code means embodied therein for enabling a compilation of a database language statement having a procedural part packaged together with at least one declarative part, said article of manufacture comprising: means for enabling a compilation of each declarative part into an executable plan; means for enabling a generation of a threaded code sequence of a control flow of the procedural part; and means for enabling an embedding of each executable plan into the threaded code sequence as a single executable meta-plan.
References Cited (Backward Citations)
US5617567A
Cited
US5201046A
Cited
US5291582A
Cited
US5487132A
Cited
US5432930A
Cited
US5546570A
Cited
US5675804A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-02-22 | 2002-08-24 | 2003-02-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-02-22 | 2006-08-24 | 2007-02-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-02-22 | 2010-08-24 | 2011-02-23 | $7700.00 | Window Closed / Lapsed |