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

• US 5,592,668 A
• Filed: 06/06/1995
• Issued: 01/07/1997
• 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): CHOULES, JACK M
• Assistant Examiner(s): Wang, Peter Y.
• Application Number:
  US08/488,384
• Time in Patent Office: 581 Days
• Field of Search: 395/600, 395/161, 395/12, 395/155
• 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 including a general purpose programmable digital computer, said computer having central processing means, bus means, display means, data entry means, memory means, data storage means, and graphical user interface for describing in a natural language a query to a database, said apparatus further comprising:

diagram means for producing a diagram on said display means;

cursor control means for moving a cursor over said diagram;

repository means further comprising relational database means implemented on said computer;

fact tree formation means for forming a fact tree based on said query; and

fact tree description means for describing said fact tree in said natural language, said fact tree description means including

(a) first variable assignment means for assigning variables based on said fact tree, said variables comprising root, parent, child and node, wherein said root is the root of said fact tree, said parent is the parent of said root, said child is the child of the root and said node is the number of the child,

(b) parent test means for testing if a value of said parent is null,

(c) root text creation means, responsive to a determination by said parent test means that said value of said parent is null, for creating text for said root,

(d) node text creation means, responsive to a determination by said parent test means that a value of said parent is not null, for creating text for said node,

(e) print means for printing, on said display means, said text created by said root text creation means and said node text creation means,

(f) counter means for counting an iteration as an iteration value,

(g) node test means for determining if said iteration value is equal to a value of said node, and

(h) recursive means for recursively invoking said fact tree description means using depth-first search means.

2. The apparatus of claim 1, wherein said root text creation means further comprises:

second variable assignment means for assigning variables based on said fact tree, said variables comprising first noun, first restriction and first text wherein said first noun is the noun in said root, said first restriction is the restriction in said root and said first text is equal to the value of said noun and a phrase indicating totality;

first restriction test means for testing if a value of said first restriction is null;

first text modification means, responsive to a determination by said first restriction test means that a value of said first restriction is not null, for modifying said first text to be equal to said text and a word or phrase indicating presentation;

second text modification means, responsive to a determination by said first restriction test means that a value of said restriction is null, for modifying said text to be equal to said text and said noun and said restriction and a word or phrase indicating presentation; and

first text return means for returning said text as modified by said first or said second text modification means to said fact tree description means.

3. The apparatus of claim 1, wherein said node text creation means further comprises:

third variable assignment means for assigning variables based on said fact tree, said variables comprising second noun, parent-noun, phrase, second restriction and second text wherein said second noun is a noun in said root, said parent-noun is a noun in said root'"'"'s parent, said phrase is a phrase of said root, said restriction is a restriction in said root and said second text is equal to said second noun added to said parent-noun added to said phrase;

second restriction test means for testing if a value of said second restriction is null;

third text modification means, responsive to a determination by said second restriction test means that a value of said restriction is not null, for modifying said text to be equal to said second text added to said second noun added to said second restriction;

child testing means for testing if said root has said child;

fourth text modification means, responsive to a determination by said child test means that said root has said child, for modifying said text to be equal to said text added to said noun; and

second text return means for returning said text to said fact tree description means.

4. Method for describing, in a natural language, a query to a database previously implemented on a general purpose programmable digital computer, said computer comprising central processing means, bus means, display means, data entry means, memory means, data storage means, graphical user interface and repository means further comprising relational database means implemented on said computer, said description method further comprising the steps of:

producing a diagram on said display means;

moving a cursor over said diagram;

forming a fact tree based on said query; and

describing said fact tree in said natural language, said step of describing said fact tree further comprising the steps of

(a) assigning variables based on said fact tree, said variables comprising root, parent, child and node, wherein said root is the root of said fact tree, said parent is the parent of said root, said child is the child of the root and said node is the number of the child using a first variable assignment method,

(b) testing if a value of said parent is null using a parent test method,

(c) creating text for said root using a root text creation method, responsive to a determination by said parent test method that said value of said parent is null,

(d) creating text for said node using a node text creation method, responsive to a determination by said parent test method that a value of said parent is not null,

(e) printing, on said display means, said text created by said root text creation method and said node text creation method using a print method,

(f) counter method for counting an iteration as an iteration value,

(g) determining if said iteration value is equal to a value of said node using a node test method, and

(h) recursively invoking said fact tree description method using a depth-first recursive search method.

5. The method of claim 4, said root text creation method further comprising the steps of:

assigning variables based on said fact tree, said variables comprising first noun, first restriction and first text, wherein said first noun is the noun in said root, said first restriction is the restriction in said root and said first text is equal to the value of said first noun and a phrase indicating totality using a second variable assignment method;

testing if a value of said first restriction is null using a first restriction test method;

modifying said first text to be equal to said first text having and a word or phrase indicating presentation using a first text modification method, said first text modification method responsive to a determination by said first restriction test method that a value of said first restriction is not null;

modifying said text to be equal to said text and said noun and said restriction and a word or phrase indicating presentation using a second text modification method, said second text modification method responsive to a determination by said first restriction test method that a value of said restriction is null; and

returning said text as modified by said first or said second text modification method to said fact tree description method using a first text return method.

6. The method of claim 4, wherein said node text creation method further comprises the steps of:

assigning variables based on said fact tree, said variables comprising second noun, parent-noun, phrase, second restriction and second text wherein said second noun is a noun in said root, said parent-noun is the noun in root'"'"'s parent, said phrase is the phrase of the root, said second restriction is a restriction in said root and said second text is equal to said second noun added to said parent noun added to said phrase, said method of assigning variables using a third variable assignment method;

testing if a value of said restriction is null using a second restriction test method;

modifying said text, responsive to a determination by said second restriction test method that a value of said restriction is not null, to be equal to said text added to said noun added to said restriction, using a third text modification method;

testing if said root has said children using a child testing method;

modifying said text, responsive to a determination by said child testing method that said root has said children; and

second text return method for returning said text to said fact tree description method.

7. A method for defining a query of an information system, the 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 the natural language-like constructs into object-role modeling symbology, the specification means further for entering text onto the display device utilizing the textual form of the computer language, for parsing the text into at least one of object, fact and constraint into the repository, and for forming a conceptual schema diagram representing the information system on the display device utilizing the graphical form of the computer language, and for mapping the conceptual schema to a database, the apparatus implemented on a programmable computer including memory, data entry means, data display means, a graphical user interface, and having a repository implemented thereon, the apparatus using natural language-like constructs for querying the information system and further comprising:

means for displaying the conceptual schema utilizing the graphical form of the computer language;

drag and drop cursor control means for moving a cursor over the conceptual schema diagram, and for selecting a first object therefrom;

fact tree formation means for forming a fact tree from a first object stored in the repository and displayed on the conceptual schema diagram, the first object forming the root node of a fact tree; and

fact tree description means for describing the fact tree with natural language-like constructs on the data display means, utilizing the textual form of the computer language.

8. The apparatus of claim 7 wherein:

the cursor control means is further for selecting at least one fact relevant to the first object from the conceptual schema display means; and

the fact tree formation means is further for forming the fact tree from the first object and the fact, the fact forming a child node of the root node.

9. The apparatus of claim 7 wherein:

the cursor control means is further for selecting a constraint relevant to the first object from the conceptual schema display means; and

the fact tree formation means is further for forming the fact tree from the first object and the constraint, the constraint limiting the object.

10. Method for defining a query of an information system, the 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 the natural language-like constructs into object-role modeling symbology, the specification means further for entering text onto the display device utilizing the textual form of the computer language, for parsing the text into at least one of object, fact and constraint into the repository, and for forming a conceptual schema diagram representing the information system on the display device utilizing the graphical form of the computer language, and for mapping the conceptual schema to a database, the apparatus implemented on a programmable computer including memory, data entry means, data display means, a graphical user interface, and having a repository implemented thereon, the apparatus using natural language-like constructs for querying the information system and further comprising the steps of:

displaying the conceptual schema the display device utilizing the graphical form of the computer language;

moving a cursor over the conceptual schema diagram with a drag and drop cursor control means, and selecting a first object from the diagram;

forming a fact tree from a first object stored in the repository and displayed on the conceptual schema diagram, the first object forming the root node of a fact tree; and

describing the fact tree with natural language-like constructs on the data display means utilizing the textual form of the computer language.

11. The method of claim 10 further comprising the steps of:

selecting at least one fact relevant to the first object from the conceptual schema display means; and

forming the fact tree from the first object and the fact, the fact forming a child node of the root node.

12. The method of claim 10 further comprising the steps of:

selecting a constraint relevant to the first object from the conceptual schema display means, the constraint limiting the object; and

forming the fact tree from the first object and the constraint.