Method and apparatus for generating a query to an information system specified using natural language-like constructs

• US 5,574,908 A
• Filed: 06/06/1995
• Issued: 11/12/1996
• Est. Priority Date: 08/25/1993
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Asymetrix Corp.
• Inventors: McCormack, Jonathan I., Harding, James A.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): WANG, PETER
• Application Number:
  US08/485,210
• Time in Patent Office: 525 Days
• Field of Search: 395/600, 395/161
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2423 Interactive query statement specification based on a database schema
• CPC Class Codes: G06F 16/2428 Query predicate definition using graphical user interfaces, including menus and forms G06F16/2423 takes precedence
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/968 Partitioning
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Computerized tools for modeling database designs and specifying queries of the data contained therein. Once it is determined that an information system needs to be created, the Fact Compiler of the present invention is invoked to create it. After creating the information system, the user creates a fact-tree as a prelude to generating queries to the system. After creating the fact-tree, the user verifies that it is correct using the Tree Interpreter of the present invention. Once the fact tree has been verified, the Query Mapper of the present invention is used to generate information system queries.

Claims

1. Apparatus for generating a query to an information system, said information system having been created using a drag-and-drop information system specification means utilizing a computer language having both textual and graphical forms for translating natural language-like constructs into object-role modeling symbology, said information system specification means further for entering text, utilizing the textual form of said computer language, onto a display device, for parsing said text into at least one of object, fact and constraint into a repository, for forming a conceptual schema representing said information system, and for mapping said conceptual schema to a database, said apparatus implemented on a programmable computer including memory, data entry means, said display means, a graphical user interface, and having said repository implemented thereon, said apparatus using said natural language-like constructs for specifying said query to said information system by providing means for displaying said conceptual schema utilizing said graphical form of said computer language, drag and drop cursor control means for moving a cursor over said conceptual schema diagram and for selecting a first object, and fact tree formation means for forming a fact tree from a first object stored in said repository and displayed on said conceptual schema diagram, said first object forming the root node of a fact tree, said apparatus further comprising:

relational query mapping means for mapping said query to said database and for returning said query in a language appropriate to said database, said query mapping means utilizing said root node defined by said first object, which first object is displayed using utilizing said graphical form of said computer language, and selected by said drag and drop cursor control means.

2. The apparatus of claim 1 wherein:

said fact tree formation means is further for forming said fact tree from a fact stored in said repository, said fact further selected from said conceptual schema diagram, said first object forming said root node of a fact tree, said fact forming a non-root node of said fact tree; and

said relational query mapping means is further for returning said query using said fact as a non-root node.

3. The apparatus of claim 1 wherein:

said fact tree formation means is further for forming said fact tree from a constraint stored in said repository, said constraint further selected from said conceptual schema diagram, said first object forming said root node of a fact tree, said constraint for restricting said root of said tree to a given instance of said first object; and

said relational query mapping means further for returning said query restricted to said given instance of said first object defined by said constraint.

4. The apparatus of claim 1 wherein said query mapping means further comprises:

query variable initialization means, responsive to a call to said query mapping means, for initializing query variables, said query variables comprising Root, WhereClause, FromList and SelectList, JoinTable and JoinColumn;

said Root variable initialized to the value of root, and said WhereClause, FromList and SelectList, JoinTable and JoinColumn variables being initialized to a null value;

query build means, responsive to said query initialization means, for receiving said Root, JoinTable and JoinColunm variables, and building said query;

query variable format means format means for formatting said query variables after said query variables are returned from said query build means;

query assembly means for assembling said query from said query variables; and

query return means for returning said query mapping means.

5. The apparatus of claim 4 wherein said query build means further comprises:

local build variable initialization means, responsive to invocation of said query build means for initializing local build variables, said local build variables comprising Root, Parent, Nodes and Child(i . . . nodes), Table and Column where said Root variable is set to the value of root, said Parent variable is set to the value of the parent of said root, said Nodes variable is the number of children of said root, Child(i . . . n) are children of said root, said Table variable is the table from said Child(i . . . n)'"'"'s mapping and said Column is the column for a second noun from said Child(i . . . n)'"'"'s mapping;

nodes checking means, responsive to said value of said Nodes variable, for returning to said query mapping means if said nodes checking means determines the value of said Nodes variable to be equal to zero;

parent checking means, responsive to a determination by said nodes checking means that the value of said nodes variable is greater than zero, for checking if the value of said Parent variable is a null value;

first selector adding means, responsive to a determination by said parent checking means that said value of said Parent variable is a null value, for updating said SelectList variable by adding to said SelectList variable the variables Table and Column, said Table variable equal to a table from said node'"'"'s mapping and said Column variable equal to a column from said node'"'"'s mapping, where said value of said node is equal to Child(i);

join creation means, responsive to a determination by said parent checking means that said value of said Parent variable is other than a null value, for joining a subquery to said query by adding an inner-join to said WhereClause;

iteration counter means for counting iterations;

iteration counter initialization means for initializing said iteration counter means to a value of 1;

iterative node test means for testing whether the value of said Nodes variable is less than or equal to the value of said iteration counter means, and returning to said query mapping means if said iterative node testing means determines the value of said Nodes variable to be greater than the value of said iteration counter;

second selector adding means, responsive to a determination by said iterative node test means that said Nodes variable is less than or equal to the value of said iteration counter means, for adding node'"'"'s Table to said FromList variable and adding said node'"'"'s table and column to said SelectList variable, where said value of said node is equal to Child(i), and Child(i) is the value of said iteration counter means;

recursive query build invoking means for joining queries created for child nodes of said node to said query;

iteration counter incrementing means for incrementing said iteration counter means by a value of 1; and

loop means for returning to said iterative node test means.

12. The apparatus of claim 5 wherein said first selector adding means further comprises:

variable initialization means for setting the value of local variable Node equal to the value of said Child(i) variable;

table locating means for setting the value of said Table variable to the table of said Node variable'"'"'s mapping;

column locating means for setting the value of said Column variable to the column for the first noun from said Node variable'"'"'s mapping;

listing means for setting the value of said SelectList variable to the previous value of said SelectList variable added to said Table variable and said Column variable; and

selector return means for returning said value of said SelectList variable to said query build means.

13. The apparatus of claim 5 wherein said second selector adding means further comprises variable initialization means for setting the value of local variable Node equal to the value of said Child(i) variable which is equal to the value of said iteration counter means;

table locating means for setting the value of said Table variable to the table of said Node variable'"'"'s mapping;

column locating means for setting the value of said Column variable to the column for the first noun from said Node variable'"'"'s mapping;

first listing means for setting the value of said SelectList variable to the previous value of said SelectList variable added to said Table variable and said Column variable;

second listing means for setting the value of said FromList variable to the previous value of said FromList variable added to said Table variable; and

selector return means for returning said value of said FromList variable and said SelectList variable to said query build means.

14. The apparatus of claim 5 wherein said join creation means further comprises:

variable initialization means for setting the value of local variable Node equal to the value of said Child(i) variable;

table locating means for setting the value of said Table variable to the table of said Node variable'"'"'s mapping;

column locating means for setting the value of said Column variable to the column for the first noun from said Node variable'"'"'s mapping;

join assembly means for assembling said join by setting the value of said WhereClause variable to the value of said WhereClause variable added to said Table variable added to said Column variable added to said Column variable added to said JoinTable variable added to said JoinColumn variable; and

join return means for returning said join assembled by said join assembly means to said query build means.

6. A method for generating a query to an information system, said information system having been created using drag-and-drop information system specification means utilizing a computer language having both textual and graphical forms for translating natural language-like constructs into object-role modeling symbology, said information specification means further for entering text onto a display device utilizing said textual form of said computer language, for parsing said text into at least one of object, fact and constraint into a repository, for forming a conceptual schema diagram representing said information system, and for mapping said conceptual schema to a database, said apparatus implemented on a programmable computer including memory, data entry means, said display means, a graphical user interface, and having said repository implemented thereon, said method using said natural language-like constructs for specifying said query to said information system by providing means for displaying said conceptual schema utilizing said graphical form of said computer language, drag and drop cursor control means for moving a cursor over said conceptual schema diagram and for selecting a first object, and fact tree formation means for forming a fact tree from a first object stored in said repository and displayed on said conceptual schema diagram, said first object forming the root node of a fact tree, said method further comprising the steps of:

mapping said query to said database with a relational query mapping means utilizing said root node defined by said first object, which first object is displayed utilizing said graphical form of said computer language, and selected by said drag and drop cursor control means; and

returning said query in a language appropriate to said database.

7. The method of claim 6 further comprising the steps of:

selecting a fact from said conceptual schema diagram using said drag and drop cursor control means;

forming said fact tree from said first object and said fact, said first object forming said root node of a fact tree, said fact forming a non-root node of said fact tree; and

returning said query using said fact as a non-root node.

8. The method of claim 6 further comprising the steps of:

selecting a constraint from said conceptual schema diagram using said drag and drop cursor control means;

forming said fact tree from said first object and said constraint, said first fact forming said root node of a fact tree, said constraint for restricting said root node of said fact tree to a given instance of said first object; and

returning said query restricted to said given instance of said first object defined by said constraint.

9. The method of claim 6 wherein said step of mapping said query to said database further comprises the steps of;

initializing query variables, said query variables comprising Root, WhereClause, FromList and SelectList, JoinTable and JoinColumn;

said Root variable initialized to the value of root, and said WhereClause, FromList and SelectList, JoinTable and JoinColumn variables being initialized to a null value using query variable initialization means, responsive to a call to said query mapping means;

build said query using query build means responsive to said Root, JoinTable and JoinColumn variables, and to said query initialization means;

formatting said query variables using query variable format means after said query variables are returned from said query build means;

assembling said query from said query variables using query assembly means; and

returning said query mapping means using query return means.

10. The method of claim 24 wherein said step of building said query further comprises the steps of:

initializing local build variables using local build variable initialization means responsive to invocation of said query build means, said local build variables comprising Root, Parent, Nodes and Child(i . . . nodes), Table and Column where said Root variable is set to the value of root, said Parent variable is set to the value of the parent of said root, said Nodes variable is the amber of children of said root, Child(i . . . n) are children of said root, said Table variable is the table from said Child(i . . . n)'"'"'s mapping and said Column is the column for a second noun from said Child(i . . . n)'"'"'s mapping;

returning to said query mapping means if said nodes checking means determines the value of said Nodes variable to be equal to zero, using nodes checking means, responsive to said value of said Nodes variable;

checking if the value of said Parent variable is a null value using parent checking means, responsive to a determination by said nodes checking means that the value of said nodes variable is greater than zero;

updating said SelectList variable by adding to said SelectList variable the variables Table and Column, said Table variable equal to a table from said node'"'"'s mapping and said Column variable equal to a column from said node'"'"'s mapping, where said value of said node is equal to Child(i) using first selector adding means, responsive to a determination by said parent checking means that said value of said Parent variable is a null value;

joining a subquery to said query by adding an inner-join to said WhereClause using join creation means, responsive to a determination by said parent checking means that said value of said Parent variable is other than a null value;

counting iterations using iteration counter means;

initializing said iteration counter means to a value of 1 using iteration counter initialization means;

testing whether the value of said Nodes variable is less than or equal to the value of said iteration counter means, and returning to said query mapping means if said iterative node testing means determines the value of said Nodes variable to be greater than the value of said iteration counter means using iterative node test means;

adding node'"'"'s table to said FromList variable and adding said node'"'"'s table and column to said SelectList variable, where said value of said node is equal to Child(i), and Child(i) is the value of said iteration counter means using second selector adding means, responsive to a determination by said iterative node test means that said Nodes variable is less than or equal to the value of said iteration counter means;

joining queries created for child nodes of said node to said query using recursive query build invoking means;

incrementing said iteration counter means by a value of 1 using iteration counter incrementing means; and

returning to said iterative node test means using loop means.

15. The method of claim 10 wherein said step of updating said SelectList variable further comprises the steps of:

setting the value of local variable Node equal to the value of said Child(i) variable;

setting the value of said Table variable to the table of said Node variable'"'"'s mapping;

setting the value of said Column variable to the column for the first noun from said Node variable'"'"'s mapping;

setting the value of said SelectList variable to the previous value of said SelectList variable added to said Table variable and said Column variable; and

returning said value of said SelectList variable to said step of building said query.

16. The method of claim 10 wherein said step of joining a subquery to said query further comprises the steps of:

setting the value of local variable Node equal to the value of said Child(i) variable;

setting the value of said Table variable to the table of said Node variable'"'"'s mapping;

setting the value of said Column variable to the column for the first noun from said Node variable'"'"'s mapping;

assembling said join by setting the value of said WhereClause variable to the value of said WhereClause variable added to said Table variable added to said Column variable added to said JoinTable variable added to said JoinColumn variable; and

returning said join to said step of building said query.

17. The method of claim 10 wherein said step of adding node'"'"'s table to said FromList variable and adding said node'"'"'s table and column to said SelectList variable further comprises the steps of:

setting the value of local variable Node equal to the value of said Child(i) variable, said Child(i) variable being equal to the value of said iteration counter;

setting the value of said Table variable to the table of said Node variable'"'"'s mapping;

setting the value of said Column variable to the column for the first noun from said Node variable'"'"'s mapping;

setting the value of said SelectList variable to the previous value of said SelectList variable added to said Table variable and said Column variable;

setting the value of said FromList variable to the previous value of said FromList variable added to said Table variable; and

returning said value of said FromList variable and said SelectList variable to said query build means.

11. Apparatus for generating a query to an information system, said information system having been created using a drag-and-drop information system specification means utilizing a computer language having both textual and graphical forms for translating natural language-like constructs into object-role modeling symbology, said information system specification means further for entering text, utilizing the textual form of said computer language, onto a display device, for parsing said text into at least one of object, fact and constraint into a repository, for forming a conceptual schema representing said information system, and for mapping said conceptual schema to a database, said apparatus implemented on a programmable computer including memory, data entry means, said display means, a graphical user interface, and having said repository implemented thereon, said apparatus using said natural language-like constructs for specifying said query to said information system by providing means for displaying said conceptual schema utilizing said graphical form of said computer language, drag and drop cursor control means for moving a cursor over said conceptual schema diagram and for selecting a first object and a fact stored in said repository and displayed on said conceptual schema diagram, and fact tree information means for forming a fact tree from said first object and said fact, said first object forming the root node of said fact tree and said fact forming the non-root node of said fact tree, said apparatus further comprising:

query mapping means for using said root node as aa first input and returning a first query equivalent to said root node, and for using said non-root node as a second input and returning a second query, said first and said second queries in a computer language appropriate to said database, said query mapping means further including,

(a) query variable initialization means, responsive to a call to said query mapping means, for initializing query variables, said query variables comprising Root, WhereClause, FromList and SelecList, JoinTable and JoinColumn, said Root variable initialized to the value of root, and said WhereClause, FromList and SelecList, JoinTable and JoinColumn variables being initialized to a null value, and

(b) query build means, responsive to said query initialization means, for receiving said Root, JoinTable and JoinColumn variables, and for building said query, said query build means further including,

(i) local build variable initialization means, responsive to invocation of said query build means for initializing local build variables, said local build variables comprising Root, Parent, Nodes and Child(i . . . nodes), Table and Column where said Root variable is set to the value of root, said Parent variable is set to the value of the parent of said root, said Nodes variable is the number of children of said root, Child(i . . . n) are children of said root, said Table variable is the table from said Child(. . . n)'"'"'s mapping and said Column is the column for a second noun from said Child(i . . . n)'"'"'s mapping,

(ii) nodes checking means, responsive to said value of said Nodes variables, for returning to said query mapping means if said nodes checking means determines the value of said Nodes variable to be equal to zero,

(iii) parent checking means, responsive to a determination by said nodes checking means that the value of said nodes variable is greater than zero, for checking if the value of said Parent variable is a null value,

(iv) first selector adding means, responsive to a determination by said parent checking means that said value of said Parent variable is a null value, for updating said SelectList variable by adding to said SelectList variable the variables Table and Column, said Table variable equal to a table from said node'"'"'s mapping and said Column variable equal to a column from said node'"'"'s mapping, where said value of said node is equal to Child(i),

(v) join creation means, responsive to a determination by said parent checking means that said value of said Parent variable is other than a null value, for joining a subquery to said query by adding an inner-join to said WhereClause,

(vi) iteration counter means for counting iterations,

(vii) iteration counter initialization means for initializing said iteration counter means to a value of 1,

(viii) iterative node test means for testing whether the value of said Nodes variable is less than or equal to the value of said iteration counter means, and returning to said query mapping means if said iterative node testing means determines the value of said Nodes variable to be greater than the value of said iteration counter,

(ix) second selector adding means, responsive to a determination by said iterative node test means that said Nodes variable is less than or equal to the value of said iteration counter means, for adding node'"'"'s Table to said FromList variable and adding said node'"'"'s table and column to said SelectList variable, where said value of said node is equal to Child(i), and Child(i) is the value of said iteration counter means,

(x) recursive query build invoking means for joining queries created for child nodes of said node to said query,

(xi) iteration counter incrementing means for incrementing said iteration counter means by a value of 1, and

(xii) loop means for returning to said iterative node test means,

(c) query variable format means format means for formatting said query variables after said query variables are returned from said query build means,

(d) query assembly means for assembling said query from said query variables, and

(e) query return means for returning said query mapping means.

18. A method for generating a query to an information system, said information system having been created using a drag-and-drop information system specification means utilizing a computer language having both textual and graphical forms for translating natural language-like constructs into object-role modeling symbology, said information system specification means further for entering text, utilizing the textual form of said computer language, onto a display device, for parsing said text into at least one of object, fact and constraint into a repository, for forming a conceptual schema representing said information system, and for mapping said conceptual schema to a database, said apparatus implemented on a programmable computer including memory, data entry means, said display means, a graphical user interface, and having said repository implemented thereon, said apparatus using said natural language-like constructs for specifying said query to said information system by providing means for displaying said conceptual schema utilizing said graphical form of said computer language, drag and drop cursor control means for moving a cursor over said conceptual schema diagram and for selecting a first object and a fact stored in said repository and displayed on said conceptual schema diagram, and fact tree formation means for forming a fact tree from said first object and said fact, said first object forming the root node of said fact tree and said fact forming the non-root node of said fact tree, said method further comprising the steps of:

(a) initializing query variables, said query variables comprising Root, WhereClause, FromList and SelectList, JoinTable and JoinColumn, said Root variable initialized to the value of root, and said WhereClause, FromList and SelectList, JoinTable and JoinColumn variables being initialized to a null value using query variable initialization means, responsive to said query mapping means,

(b) building said query using query build means responsive to said Root, JoinTable and JoinColumn variables, and to said step of initializing query variables, said query build means further comprises the step of,

(i) responsive to invocation of said query build means, initializing local build variables comprising Root, Parent, Nodes and Child(i . . . nodes), Table and Column where said Root variable is set to the value of root, said Parent variable is set to the value of the parent of said root, said Nodes variable is the number of children of said root, Child(i . . . n) are children of said root, said Table variable is the table from said Child(i . . . n)'"'"'s mapping and said Column is the column for a second noun from said Child(i . . . n)'"'"'s mapping,

(ii) returning to said step of mapping queries to said database if said Nodes variable is equal to zero,

(iii) responsive to a determination by said step of returning to said step of mapping queries that the value of said Nodes variable is greater than zero, checking if the value of said Parent variable is a null value,

(iv) responsive to a determination by said step if checking if the value of said Parent variable is a null value that said Parent variable is a null value, updating said SelectList variable by adding to said SelectList variable the variables Table and Column, said Table variable equal to a table from said node'"'"'s mapping and said Column variable equal to a column from said node'"'"'s mapping, where said value of said node is equal to Child(i),

(v) responsive to a determination by said step of checking if the value of said Parent variable is a null value that said value of said Parent variable is other than a null value, joining a subquery to said query by adding an inner-join to said WhereClause,

(vi) initializing an iteration counter means to a value of 1,

(vii) counting iterations on said iteration counter means,

(viii) testing whether the value of said Nodes variable is less than or equal to the value of said iteration counter means, and returning to said step of mapping queries to said database query mapping means if said step of testing whether the value of said Nodes variable is less than or equal to the value of said iteration counter means determines the value of said Nodes variable to be greater than the value of said iteration counter,

(ix) responsive to a determination by said step of testing whether the value of said Nodes variable is less than or equal to the value of said iteration counter means that said Nodes variable is less than or equal to the value of said iteration counter means, adding node'"'"'s table to said FromList variable and adding said node'"'"'s table and column to said SelectList variable, where said value of said node is equal to Child(i), and Child(i) is the value of said iteration counter means using second selector adding means,

(x) joining queries created for child nodes or said node to said query,

(xi) incrementing said iteration counter means by a value of 1, and

(xii) returning to said step of testing whether the value of said Nodes variable is less than or equal to the value of said iteration counter means,

(c) formatting said query variables after said query variables are returned from said step of building said query,

(d) assembling said query from said query variables, and

(e) returning to said step of mapping said query.