System and method for interactively formulating database queries using graphical representations

• US 5,701,456 A
• Filed: 08/30/1995
• Issued: 12/23/1997
• Est. Priority Date: 03/17/1993
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jacopi, Tom William, Siwek, Howard Alexander, Payton, Brian Gerrit
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Choules, Jack M.
• Application Number:
  US08/520,903
• Time in Patent Office: 846 Days
• Field of Search: 395/608, 395/610, 395/614, 395/615, 395/603, 395/604, 395/602, 395/348, 395/349
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2428 Query predicate definition using graphical user interfaces, including menus and forms G06F16/2423 takes precedence
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

In a computerized database system, a query is formulated to retrieve data from the database by interactively identifying at least one table containing query data, and at least one column and at least one row in the identified table containing the query data. The rows are interactively identified using a condition statement. The condition statement is interactively formulated using at least one displayed flowline. Input is received from the user specifying a position on the flowline for insertion of a predicate and the predicate. The flowline is displayed with the predicate inserted in the specified location. The predicates are displayed on the flowline in between nodes. Predicates on the same flowline are combined through a logical AND operation. Predicates on different flowlines between the same nodes are combined through a logical OR operation. The flowline is converted to a corresponding Boolean algebra statement and displayed. Input from the user adding a predicate is received in the Boolean statement and is converted to a corresponding updated graphical flow representation.

Claims

1. A method for converting a graphical representation to a Boolean algebra statement representation comprising the steps of:

(a) when two arcs have the same To_-- Nodes and From_-- Nodes, combining the arcs into one arc with the conditions represented by the original arc linked by a logical OR operand;

(b) when two arcs are in a series with a Third_-- Node in between having the same two arcs going into and out of it, combining the arcs into one arc with the conditions represented by each original arc linked by an AND operator;

(c) pushing onto a stack a graph path;

(d) popping a path from the stack for further processing;

(e) processing the path to produce a Boolean algebra statement segment while identifying any new paths;

(f) pushing a new path onto the stack; and

(g) repeating steps (d) through (f) until the stack is empty.

2. A program storage device, readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for retrieving query data stored in tables having columns and rows, the computer being comprised of a central processing unit (CPU), a memory, a display device, and a user interaction device, the method comprising the steps of:

(a) receiving input identifying at least one table containing the query data;

(b) receiving input identifying at least one column of the identified table containing the query data;

(c) receiving input identifying at least one row in the identified table containing the query data using a condition statement interactively formulated by the following steps;

(1) displaying a graphical flow representation comprising at least one flowline comprising at least one arc, a predicate assigned to each arc, and a plurality of nodes, each arc positioned between a From_-- Node node and a To_-- Node node, wherein predicates on the same flowline are combined through a logical AND operation, and predicates on different flowlines between the same nodes are combined through a logical OR operation;

(2) receiving input specifying a position on a flowline of the graphical flow representation for insertion of a predicate;

(3) receiving input specifying the predicate;

(4) inserting the predicate at the specified position on the flowline;

(5) displaying the graphical flow representation with the predicate inserted in the specified position on the

flowline;

(6) converting the graphical flow representation into a corresponding Boolean algebra statement; and

(7) displaying the Boolean algebra statement.

3. The method of claim 2, further comprising the steps of:

receiving input from the user adding a predicate to a Boolean algebra statement;

converting the Boolean algebra statement to a corresponding graphical flow representation; and

displaying the graphical flow representation device.

4. The method of claim 2, comprising the further step of converting a graph that is a graphical flow representation to a Boolean algebra statement, the converting step comprising the steps of:

compressing the graph to a minimum number of nodes and arcs to produce a compressed graph; and

creating a corresponding Boolean algebra string by identifying at least one path through the compressed graph from a beginning node to an ending node.

5. The method of claim 4, wherein the step of compressing the graph further comprises the steps of:

combining each pair of arcs having the same To_-- Nodes and From_-- Nodes into a resulting arc with the predicates assigned to the pair of arcs connected by a logical OR operator assigned as a resulting predicate to the resulting arc; and

combining each pair of arcs having the same To_-- Node of a first arc and From_-- Node of a second arc into a resulting arc with the predicates assigned to the pair of arcs connected by an AND operator assigned as a resulting predicate to the resulting arc.

6. The method of claim 5, further comprising the steps of:

(i) pushing a graph path onto a stack;

(ii) popping a path from the stack for further processing;

(iii) processing the popped path to produce a Boolean algebra statement segment while identifying any new paths;

(iv) pushing a new path onto the stack; and

(v) repeating steps (ii) through (iv) until the stack is empty.

7. The method of claim 3, further comprising the step of converting a Boolean algebra statement representation to a graphical flow representation, the converting step comprising the steps of:

arranging the Boolean algebra statement into a parse tree comprising a plurality of elements including a root, each element being a leaf or a non-leaf, each non-leaf having a left child and a right child, and each element having a value assigned for a From_-- Node and a To_-- Node, wherein each leaf is assigned a predicate and each non-leaf is assigned an OR operator or an AND operator; and

processing each element of the tree in pre-order traversal assigning each predicate as an arc connecting a From_-- Node to a To_-- Node.

8. The method of claim 7, wherein the processing step comprises the steps of:

assigning the root From_-- Node and To_-- Node a beginning node and an ending node, respectively, of a resulting graph;

for each OR operator element, assigning the OR operator element From_-- Node and To_-- Node as the From_-- Node and To_-- Node, respectively, of the left child and right child of the OR operator element;

for each AND operator element, creating a new node, assigning the AND operator element From_-- Node as the From_-- Node of the left child of the AND operator element, assigning the new node as the To_-- Node of the left child and the From_-- Node of the right child of the AND operator element, and assigning the AND operator element To_-- Node as the To_-- Node of the right child of the AND operator element; and

for each predicate element, creating an arc connecting the From_-- Node to the To_-- Node of the predicate element and assigning the predicate to the arc.

9. The method of claim 2, further comprising the step of interactively designating a section of the graphical flow representation as having a logical NOT operation applied to the section.

10. The method of claim 2, wherein the condition statement applies to groups of data.

11. The method of claim 2, further comprising the step of displaying a flow representation of a query as a series of icons in a directed graph, the icons corresponding to table and column selection, row condition formulation, and sorting, wherein the user selects icons to formulate part of a query.

12. The method of claim 2, further comprising the step of displaying a UNION query as a directed graph having a plurality of query graphs converging following the row condition formulation icon.

13. A program storage device, readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for converting a Boolean algebra statement representation to a graphical representation, the method comprising the steps of:

(a) arranging the Boolean statement into a parse tree, wherein each element in the parse tree has a tree From_-- Node and a tree To_-- Node, each element is a leaf or a non-leaf, each non-leaf has a left child and a right child, each leaf is a connector, and each non-leaf is an OR operator or an AND operator; and

(b) processing each element of the tree in preorder traversal to assign each condition predicate as a graph arc defined as connecting a graph From Node to a graph To_-- Node, comprising the steps of;

(1) assigning the root element From_-- Node and To_-- Node as the Beginning_-- Node and Ending_-- Node of the graph;

(2) for an OR operator element, assigning an OR operator element From_-- Node and To_-- Node as the From_-- Node and To_-- Node of both of the OR operator element children;

(3) for an AND operator element, creating a New_-- Node, assigning the AND operator element From_-- Node as the From_-- Node of the left hand child of the AND operator element, the AND operator element To_-- Node as the To_-- Node of the right hand child of the AND connector element, assigning the New_-- Node as the To_-- Node of the left hand child and the from node of the right hand child of the AND operator element; and

(4) for condition elements, creating an arc connecting the From_-- Node to the To_-- Node of the condition element by the condition.

14. In a computerized database system having a central processing unit (CPU), a memory, a display device, and a user interaction device, a method for retrieving query data stored in tables having columns and rows, comprising the steps of:

(a) receiving input identifying at least one table containing the query data;

(b) receiving input identifying at least one column of the identified table containing the query data;

(c) receiving input identifying at least one row in the identified table containing the query data using a condition statement interactively formulated by the following steps;

(1) displaying a graphical flow representation comprising at least one flowline comprising at least one arc, a predicate assigned to each arc, and a plurality of nodes, each arc positioned between a From_-- Node node and a To_-- Node node, wherein predicates on the same flowline are combined through a logical AND operation, and predicates on different flowlines between the same nodes are combined through a logical OR operation;

(2) receiving input specifying a position on a flowline of the graphical flow representation for insertion of a predicate;

(3) receiving input specifying the predicate;

(4) inserting the predicate at the specified position on the flowline;

(5) displaying the graphical flow representation with the predicate inserted in the specified position on the flowline;

(6) converting the graphical flow representation into a corresponding Boolean algebra statement; and

(7) displaying the Boolean algebra statement.

15. The method of claim 14, further comprising the steps of:

receiving input from the user adding a predicate to a Boolean algebra statements

converting the Boolean algebra statement to a corresponding graphical flow representation; and

displaying the graphical flow representation device.

16. The method of claim 14, comprising the further step of converting a graph that is a graphical flow representation to a Boolean algebra statement, the converting step comprising the steps of:

compressing the graph to a minimum number of nodes and arcs to produce a compressed graph; and

creating a corresponding Boolean algebra string by identifying at least one path through the compressed graph from a beginning node to an ending node.

17. The method of claim 16, wherein the step of

compressing the graph further comprises the steps of:

combining each pair of arcs having the same To_-- Nodes and From_-- Nodes into a resulting arc with the predicates assigned to the pair of arcs connected by a logical OR operator assigned as a resulting predicate to the resulting arc; and

combining each pair of arcs having the same To_-- Node of a first arc and From_-- Node of a second arc into a resulting arc with the predicates assigned to the pair of arcs connected by an AND operator assigned as a resulting predicate to the resulting arc.

18. The method of claim 17, further comprising the steps of:

(i) pushing a graph path onto a stack;

(ii) popping a path from the stack for further processing;

(iii) processing the popped path to produce a Boolean algebra statement segment while identifying any new paths;

(iv) pushing a new path onto the stack; and

(v) repeating steps (ii) through (iv) until the stack is empty.

19. The method of claim 15, further comprising the step of converting a Boolean algebra statement representation to a graphical flow representation, the converting step comprising the steps of:

arranging the Boolean algebra statement into a parse tree comprising a plurality of elements including a root, each element being a leaf or a non-leaf, each non-leaf having a left child and a right child, and each element having a value assigned for a From_-- Node and a To_-- Node, wherein each leaf is assigned a predicate and each non-leaf is assigned an OR operator or an AND operator; and

processing each element of the tree in pre-order traversal assigning each predicate as an arc connecting a From_-- Node to a To_-- Node.

20. The method of claim 19, wherein the processing step comprises the steps of:

assigning the root From_-- Node and To_-- Node a beginning node and an ending node, respectively, of a resulting graph;

for each OR operator element, assigning the OR operator element From_-- Node and To_-- Node as the From_-- Node and To_-- Node, respectively, of the left child and right child of the OR operator element;

for each AND operator element, creating a new node, assigning the AND operator element From_-- Node as the From_-- Node of the left child of the AND operator element, assigning the new node as the To_-- Node of the left child and the From_-- Node of the right child of the AND operator element, and assigning the AND operator element To_-- Node as the To_-- Node of the right child of the AND operator element; and

for each predicate element, creating an arc connecting the From_-- Node to the To_-- Node of the predicate element and assigning the predicate to the arc.

21. The method of claim 14, further comprising the step of interactively designating a section of the graphical flow representation as having a logical NOT operation applied to the section.

22. The method of claim 14, wherein the condition statement applies to groups of data.

23. The method of claim 14, further comprising the step of displaying a flow representation of a query as a series of icons in a directed graph, the icons corresponding to table and column selection, row condition formulation, and sorting, wherein the user selects icons to formulate part of a query.

24. The method of claim 14, further comprising the step of displaying a UNION query as a directed graph having a plurality of query graphs converging following the row condition formulation icon.

25. A method for converting a Boolean algebra statement representation to a graphical representation, comprising the steps of:

(a) arranging the Boolean statement into a parse tree, wherein each element in the parse tree has a tree From_-- Node and a tree To_-- Node, each element is a leaf or a non-leaf, each non-leaf has a left child and a right child, each leaf is a connector, and each non-leaf is an OR operator or an AND operator; and

(b) processing each element of the tree in preorder traversal to assign each condition predicate as a graph arc defined as connecting a graph From_-- Node to a graph To_-- Node, comprising the steps of;

(1) assigning the root element From_-- Node and To_-- Node as the Beginning_-- Node and Ending_-- Node of the graph;

(2) for an OR operator element, assigning an OR operator element From_-- Node and To_-- Node as the From_-- Node and To_-- Node of both of the OR operator element children;

(3) for an AND operator element, creating a New_-- Node, assigning the AND operator element From_-- Node as the From_-- Node of the left hand child of the AND operator element, the AND operator element To_-- Node as the To_-- Node of the right hand child of the AND connector element, assigning the New_-- Node as the To_-- Node of the left hand child and the Prom_-- Node of the right hand child of the AND operator element; and

(4) for condition elements, creating an arc connecting the From_-- Node to the To_-- Node of the condition element by the condition.

26. A computerized database system, comprising:

(a) a computer system comprised of a central processing unit (CPU), a memory, a display device, and a user interaction device,

(b) means, performed by the computer system, for retrieving query data stored in tables having columns and rows, the means for retrieving comprising;

(1) means for receiving input identifying at least one table containing the query data;

(2) means for receiving input identifying at least one column of the identified table containing the query data;

(3) means for receiving input identifying at least one row in the identified table containing the query data a using a condition statement interactively formulated by the following elements;

means for displaying a graphical flow representation comprising at least one flowline comprising at least one arc, a predicate assigned to each arc, and a plurality of nodes, each arc positioned between a From_-- Node node and a To_-- Node node, wherein predicates on the same flowline are combined through a logical AND operation, and predicates on different flowlines between the same nodes are combined through a logical OR operation;

means for receiving input specifying a position on a flowline of the graphical flow representation for insertion of a predicate;

means for receiving input specifying the predicate;

means for inserting the predicate at the specified position on the flowline;

means for displaying the graphical flow representation with the predicate inserted in the specified position on the flowline;

means for converting the graphical flow representation into a corresponding Boolean algebra statement; and

means for displaying the Boolean algebra statement.

27. The apparatus of claim 26, further comprising:

means for receiving input from the user adding a predicate to a Boolean algebra statement;

means for converting the Boolean algebra statement to a corresponding graphical flow representation; and

means for displaying the graphical flow representation device.

28. The apparatus of claim 26, further comprising means for converting a graph that is a graphical flow representation to a Boolean algebra statement, the means for converting comprising:

means for compressing the graph to a minimum number of nodes and arcs to produce a compressed graph; and

means for creating a corresponding Boolean algebra string by identifying at least one path through the compressed graph from a beginning node to an ending node.

29. The apparatus of claim 28, wherein the means for compressing the graph further comprises:

means for combining each pair of arcs having the same To_-- Nodes and From_-- Nodes into a resulting arc with the predicates assigned to the pair of arcs connected by a logical OR operator assigned as a resulting predicate to the resulting arc; and

means for combining each pair of arcs having the same To_-- Node of a first arc and From_-- Node of a second arc into a resulting arc with the predicates assigned to the pair of arcs connected by an AND operator assigned as a resulting predicate to the resulting arc.

30. The apparatus of claim 29, further comprising:

(i) means for pushing a graph path onto a stack;

(ii) means for popping a path from the stack for further processing;

(iii) means for processing the popped path to produce a Boolean algebra statement segment while identifying any new paths;

(iv) means for pushing a new path onto the stack; and

(v) means for repeating the means (ii) through (iv) until the stack is empty.

31. The apparatus of claim 27, further comprising means for converting a Boolean algebra statement representation to a graphical flow representation, the means for converting comprising:

means for arranging the Boolean algebra statement into a parse tree comprising a plurality of elements including a root, each element being a leaf or a non-leaf, each non-leaf having a left child and a right child, and each element having a value assigned for a From_-- Node and a To_-- Node, wherein each leaf is assigned a predicate and each non-leaf is assigned an OR operator or an AND operator; and

means for processing each element of the tree in pre-order traversal assigning each predicate as an arc connecting a From_-- Node to a To_-- Node.

32. The apparatus of claim 31, wherein the means for processing comprises:

means for assigning the root From_-- Node and To_-- Node a beginning node and an ending node, respectively, of a resulting graph;

for each OR operator element, means for assigning the OR operator element From_-- Node and To_-- Node as the From_-- Node and To_-- Node, respectively, of the left child and right child of the OR operator element;

for each AND operator element, means for creating a new node, means for assigning the AND operator element From_-- Node as the From_-- Node of the left child of the AND operator element, assigning the new node as the To_-- Node of the left child and the From_-- Node of the right child of the AND operator element, and means for assigning the AND operator element To_-- Node as the To_-- Node of the right child of the AND operator element; and

for each predicate element, means for creating an connecting the From_-- Node to the To_-- Node of the predicate element and means for assigning the predicate to the arc.

33. The apparatus of claim 26, further comprising means for interactively designating a section of the graphical flow representation as having a logical NOT operation applied to the section.

34. The apparatus of claim 26, wherein the condition statement applies to groups of data.

35. The apparatus of claim 26, further comprising means for displaying a flow representation of a query as a series of icons in a directed graph, the icons corresponding to table and column selection, row condition formulation, and sorting, wherein the user selects icons to formulate part of a query.

36. The apparatus of claim 26, further comprising means for displaying a UNION query as a directed graph having a plurality of query graphs converging following the row condition formulation icon.

37. A computer-implemented apparatus for converting a Boolean algebra statement representation to a graphical representation, comprising:

(a) means for arranging the Boolean statement into a parse tree, wherein each element in the parse tree has a tree From_-- Node and a tree To_-- Node, each element is a leaf or a non-leaf, each non-leaf has a left child and a right child, each leaf is a connector, and each non-leaf is an OR operator or an AND operator; and

(b) means for processing each element of the tree in preorder traversal to assign each condition predicate as a graph arc defined as connecting a graph From_-- Node to a graph To_-- Node, comprising;

(1) means for assigning the root element From_-- Node and To_-- Node as the Beginning_-- Node and Ending_-- Node of the graph;

(2) for an OR operator element, means for assigning an OR operator element From_-- Node and To_-- Node as the From_-- Node and To_-- Node of both of the OR operator element children;

(3) for an AND operator element, means for creating a New_-- Node, means for assigning the AND operator element From_-- Node as the From_-- Node of the left hand child of the AND operator element, the AND operator element To_-- Node as the To_-- Node of the right hand child of the AND connector element, means for assigning the New_-- Node as the To_-- Node of the left hand child and the From_-- Node of the right hand child of the AND operator element; and

(4) for condition elements, means for creating an arc connecting the From_-- Node to the To_-- Node of the condition element by the condition.