APPARATUS, METHOD, AND PROGRAM FOR VISUALIZING BOOLEAN EXPRESSIONS

• US 20080104088A1
• Filed: 10/12/2007
• Published: 05/01/2008
• Est. Priority Date: 10/13/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kuriyama, Kinya, Nagai, Mariko, Takuma, Daisuke
• Granted Patent: US 7,930,320 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/9032 Query formulation

Abstract

An apparatus, a method, and a program for visualizing a Boolean expression so that it is readily recognized what is added to or excluded from conditions. A Boolean expression to be visualized is input in the form of a binary tree in which a leaf node represents an operand in the Boolean expression and a node other than the leaf node represents an operator in the Boolean expression. The input binary tree is transformed into a two-dimensional nested representation composed of a plurality of regions, and a pictorial representation for visualization is drawn on the basis of the nested representation and is displayed. When the Boolean expression is provided in a string expression, the string expression is transformed into a binary tree.

Claims

1. An apparatus for visualizing a Boolean expression, the apparatus comprising:

an input section inputting a Boolean expression to be visualized in a form of a binary tree in which a leaf node represents an operand in the Boolean expression and a node other than the leaf node represents an operator in the Boolean expression;

a transforming section transforming the binary tree into a two-dimensional nested representation composed of a plurality of regions;

a drawing section drawing a pictorial representation for visualization on the basis of the nested representation;

a storage section storing the binary tree input by the input section, the nested representation created by the transforming section, and the pictorial representation drawn by the drawing section; and

a display section visually displaying the pictorial representation.

2. The apparatus of claim 1, wherein the transforming section includes:

a leaf node transforming unit transforming each leaf node in the binary tree input by the input section into a nested object functioning as an operand of a Boolean operation;

a tree operation unit creating a two-dimensional nested representation by performing the Boolean operation using the nested object as the operand; and

an AND operation unit, an OR operation unit, and a NOT operation unit performing logical operations for creating the nested representation.

3. The apparatus of claim 1, wherein when the Boolean expression is provided in a string expression, the input section transforms the sting expression into a binary tree.

4. The apparatus of claim 3, wherein the input section transforms the string expression into a normal tree and then transforms the normal tree into a binary tree.

5. The apparatus of claim 3, wherein a leaf node of the binary tree has a label representing an operand and a NOT flag, and a node other than the leaf node has an attribute of AND or OR and a NOT flag.

6. The apparatus of claim 1, wherein the nested representation is composed of at least one nested object containing a plurality of nodes.

7. The apparatus of claim 6, wherein the transforming section transforms a leaf node of the binary tree into a nested object having a label of the leaf node and a flag, and highlights an operand corresponding to the leaf node when the flag is set to a first value and highlights a region enclosing the operand when the flag is set to a second value.

8. The apparatus of claim 7, wherein the transforming section creates at least one nested object containing a plurality of nodes by performing an operation on the nested object of the leaf node in accordance with an operator specified in a higher node of the binary tree and the flag of the nested object.

9. The apparatus of claim 8, wherein each of the plurality of nodes has (1) a label indicative of an operand or all elements and a flag indicative of whether or not the node is highlighted or (2) a pointer to another nested object, a user-defined label, and a flag indicative of whether or not the node is highlighted.

10. The apparatus of claim 9, wherein when the operation is a NOT operation, the flags of all nodes contained in a nested object to be operated on are inverted.

11. The apparatus of claim 9, wherein when the operation is an AND operation, it is determined which one of types each of a first and second nested objects to be operated on belongs to, the types including a first type in which a nested object has only one highlighted node and no lower node, a second type in which a nested object has only one node which is highlighted and whose higher node is not highlighted, and a third type in which a nested object does not belong to either the first or second type, and addition of node and inversion of flag are selectively performed in accordance with the types of the first and the second nested objects.

12. The apparatus of claim 11, wherein:

(1) in a case where the first nested object is of the first type, if a flag of an all-element node which is the highest node of the second nested object is false, a flag of a node of the first nested object whose flag is true is set to false, and all lower nodes of the all-element node of the second nested object are placed inside the node of the first object; and

if the flag of the highest all-element node of the second nested object is true, all the lower nodes of the all-element node of the second nested object are placed inside the node of the first nested object whose flag is true,

(2) in a case where neither the first nor second nested object is of the first type and the second nested object is of the second type, a lower node of a node which is contained in each of the nested objects and whose flag is true is removed, an AND operation between the nested objects of the first type is performed, and the removed lower nodes are placed inside a node contained in a result of the AND operation whose flag is true,

(3) in a case where the first nested object is not of the first type and the second nested object is of the third type, a new nested object, which is provided with a pointer to the second nested object in an all-element node and to which a node whose flag is true is added, is created, an AND operation between the new nested object and the first nested object is performed, and the second nested object is added as a dependent nested object of the first nested object,

(4) in a case other than (1) to (3), the first nested object and the second nested object are reversed and the operations of (1) to (3) are performed.

13. The apparatus of claim 12, wherein in a case where the operation is an OR operation, if both flags of root nodes of the first and the second nested objects to be operated on are false, all lower nodes of the root node of the second nested object is placed inside the root node of the first nested object, and if at least one of the flags of the root nodes of the first and the second nested objects is true, an AND operation is performed after all flags of the first nested object and the second nested object are inverted, and all flags of a result of the AND operation are inverted.

14. The apparatus of claim 9, wherein the drawing section

(1) draws a rectangle associated with an all-element node and highlights the all-element node if a flag of the all-element node is true, and

(2) if a node associated with a drawn rectangle has a lower node which has not been associated with a rectangle, draws a rectangle associated with the lower node in the interior of the drawn rectangle so as not to overlap another rectangle placed inside the drawn rectangle.

15. A method for visualizing a Boolean expression, the method comprising the steps of:

inputting a Boolean expression to be visualized in the form of a binary tree in which a leaf node represents an operand in the Boolean expression and a node other than the leaf node represents an operator in the Boolean expression and storing the binary tree;

transforming the binary tree into a two-dimensional nested representation composed of a plurality of regions and storing the two-dimensional nested representation;

drawing a pictorial representation for visualization on the basis of the nested representation and storing the pictorial representation; and

displaying the pictorial representation.

16. A program storage device storing a program for visualizing a Boolean expression, the program causing a computer to function as:

an input section for inputting a Boolean expression to be visualized in the form of a binary tree in which a leaf node represents an operand in the Boolean expression and a node other than the leaf node represents an operator in the Boolean expression;

a transforming section for transforming the binary tree into a two-dimensional nested representation composed of a plurality of regions;

a drawing section for drawing a pictorial representation for visualization on the basis of the nested representation;

a storage section for storing the binary tree input by the input section, the nested representation created by the transforming section, and the pictorial representation drawn by the drawing section; and

a display section for displaying the pictorial representation.