System and method for optimizing the structure and display of complex data filters

• US 6,470,335 B1
• Filed: 06/01/2000
• Issued: 10/22/2002
• Est. Priority Date: 06/01/2000
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Marusak, Scott M.
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): ALAUBAIDI, HAYTHIM J
• Application Number:
  US09/585,079
• Time in Patent Office: 873 Days
• Field of Search: 707/2, 707/10, 707/3-6, 707/104, 345/837, 345/853, 345/969
• 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: G06F 16/2454 Optimisation of common expressions
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 715/969 Network layout and operation interface

Abstract

A system and method for optimizing the structure and display of complex data filters is provided. The system includes software modules for creating, optimizing and then displaying complex data filter queries structured according to a particular query language. The query is modeled by generating a filter network comprising a plurality of filter nodes, wherein each filter node corresponds to a conditional expression in the query. Optimization modules then optimize the structure and visual display of the filter network. The system software modules may include a query input module, a graphical interface module, a visual optimization module, and a query language optimization module. The query input module enables a user to input a data filter query into the system using a particular query language. The graphical interface module then maps the input query into a graphical representation of the data filter using a readily understandable graphical paradigm. The visual optimization module optimizes the graphical display of the query by merging sub-networks of the filter network that generate the same query language, and the query language optimization module optimizes the structure of the input query by eliminating redundant filter nodes.

Claims

1. An optimization method for database queries, comprising the steps of:

(a) receiving a database query described by a query language logical structure;

(b) generating a filter network comprising a plurality of filter nodes, wherein the structure of the filter network corresponds to the logical structure of the query;

(c) optimizing the structure of the filter network by identifying pairs of redundant filter nodes in the filter network and deleting one of the redundant nodes in the pair; and

(d) optimizing the display of the filter network by identifying similar sub-networks in the filter network and merging the sub-networks.

2. The method of claim 1, further comprising the step of:

displaying the optimized filter network.

3. The method of claim 1, further comprising the step of:

saving the optimized filter network to a data store.

4. The method of claim 1, wherein the generating step further comprises the steps of:

associating a filter node with each conditional expression in the database query; and

generating a filter node model for each filter node that includes one of the conditional expressions in the database query and a deletion flag that indicates whether the filter node has been merged or deleted in one of the optimization steps.

5. The method of claim 4, wherein the filter node model includes filter node pointers for maintaining the filter nodes as a doubly linked list.

6. The method of claim 5, wherein the filter node pointers include parent and child node pointers for coupling the filter node to one or more parent filter nodes and one or more child filter nodes.

7. The method of claim 6, wherein the parent node pointers include an AND parent node pointer and an OR parent node pointer.

8. The method of claim 6, wherein the child node pointers include an AND child node pointer and an OR child node pointer.

9. The method of claim 1, wherein the generating step further comprises the steps of:

providing an originating node that indicates the input of the filter network;

providing one or more terminating nodes that indicate the one or more outputs of the filter network; and

providing a plurality of link operators for coupling the originating node to the one or more terminating nodes through the plurality of filter nodes.

10. The method of claim 8, further comprising the steps of:

depicting the filter network according to a plumbing paradigm.

11. The method of claim 10, wherein the depicting step further comprises the steps of:

depicting the originating node as a funnel;

depicting the one or more terminating nodes as faucets;

depicting the plurality of filter nodes as boxes; and

depicting the link operators as pipes that couple the funnel to the faucets through the plurality of boxes.

12. The method of claim 11, further comprising the steps of:

configuring one of the link operators as an AND operator and depicting the AND link operator as a straight-line pipe.

13. The method of claim 11, further comprising the steps of:

configuring one of the link operators as an OR operator and depicting the OR link operator as a tee-line pipe.

14. The method of claim 1, wherein the receiving step further comprises the steps of:

providing a query input window for receiving a textual description of the query language logical structure.

15. The method of claim 1, wherein the receiving step further comprises the steps of:

providing a query input window for receiving a graphical description of the query language logical structure.

16. The method of claim 1, wherein the structural optimization step comprises the steps of:

identifying two filter nodes that, together with any succeeding nodes in the filter network, generate the same query language logical structure; and

deleting one of the two filter nodes from the filter network.

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

prior to deleting one of the two filter nodes, determining that the two filter nodes are logically coupled to a common parent node.

18. The method of claim 16, further comprising the step of:

generating the query language logical structure for each of the two filter nodes and any succeeding nodes in the filter network; and

storing the query language logical structure in an array.

19. The method of claim 16, further comprising the steps of:

repeating the identifying and deleting steps for each filter node in the filter network.

20. The method of claim 1, wherein the visual optimization step comprises the steps of:

identifying two filter sub-networks that generate the same query language logical structure;

determining whether the two filter sub-networks can be merged; and

if so, then merging the two filter sub-networks.

21. The method of claim 20, further comprising the steps of:

generating the query language logical structure for each of the two sub-networks; and

storing the query language logical structure in an array.

22. The method of claim 20, wherein the determining step comprises the steps of:

first determining whether the head filter node associated with one of the sub-networks is not logically ORed to a parent filter node;

second determining whether the head filter node associated with the other sub-network is not logically ANDed to a parent filter node; and

if these first and second determining steps are true, then determining that the two filter sub-networks can be merged.

23. The method of claim 20, further comprising the steps of:

repeating the identifying, determining and merging steps for each filter sub-network in the filter network.

24. A method of displaying a complex data filter, comprising the steps of:

generating a filter network model for the complex data filter, wherein the filter network model includes an originating node, one or more terminating nodes, and a plurality of filter nodes, wherein the originating node is coupled to the one or more terminating nodes through the plurality of filter nodes;

depicting the originating node as a funnel;

depicting the one or more terminating nodes as faucets;

depicting the filter nodes as boxes, wherein each box contains a conditional expression associated with the filter node;

depicting the logical couplings between originating node, the terminating node and the filter nodes using one or more types of pipes; and

displaying the filter network using the funnel, the faucets, the boxes, and the one or more types of pipes.

25. A system for optimizing database queries, comprising:

a query input module that receives a database query described by a query language logical structure;

a graphical interface module that generates a filter network comprising a plurality of filter nodes, wherein the structure of the filter network corresponds to the logical structure of the query;

a structural optimization module that optimizes the structure of the filter network; and

a visual optimization module that optimizes the display of the filter network.

26. The system of claim 25, further comprising:

a data store for saving the filter network.

27. The system of claim 25, further comprising:

a database containing a plurality of records; and

a query tool that applies the filter network to the plurality of records in the database.

28. The system of claim 25, further comprising:

a graphical display that displays the filter network.

29. The system of claim 25, wherein the structural optimization module optimizes the structure of the filter network by identifying pairs of redundant filter nodes in the filter network and deleting one of the redundant nodes in the pair.

30. The system of claim 25, wherein the visual optimization module optimizes the display of the filter network by identifying similar sub-networks in the filter network and merging the sub-networks.

31. A computer-readable medium encoded with program instructions for optimizing and displaying database queries, wherein the program instructions enable the steps of:

receiving a database query;

generating a filter network comprising a plurality of filter nodes, wherein the structure of the filter network corresponds to the logical structure of the query;

optimizing the structure of the filter network by identifying pairs of redundant filter nodes in the filter network and deleting one of the redundant nodes in the pair;

optimizing the display of the filter network by identifying similar sub-networks in the filter network and merging the sub-networks; and

displaying the optimized filter network.

32. A method for optimizing the display of complex data filters, comprising the steps of:

receiving a complex data filter including a plurality of filter nodes organized into a filter network, wherein each filter node corresponds to a conditional expression in the complex data filter;

generating a data model for each of the filter nodes in the filter network, wherein the data model includes a conditional expression for each filter node and a corresponding flag that indicates whether or not the node has been optimized; and

optimizing the display of the filter network by;

identifying similar sub-networks in the filter network;

merging the similar sub-networks; and

setting the flag for one of the filter nodes in the merged sub-network to indicate that the node has been optimized.

33. A system for optimizing complex data filter queries, comprising:

means for receiving a query;

means for generating a filter network corresponding to the logical structure of the query, wherein the filter network includes a plurality of filter nodes that each correspond to one conditional expression in the query;

means for optimizing the structure of the filter network; and

means for optimizing the display of the filter network.

34. A visualization optimization method for database queries, comprising the steps of:

receiving a database query described by a query language logical structure;

generating a filter network comprising a plurality of filter nodes, wherein the structure of the filter network corresponds to the logical structure of the query;

optimizing the structure of the filter network by identifying pairs of redundant filter nodes in the filter network and deleting one of the redundant nodes in the pair;

optimizing the display of the filter-network by identifying similar sub-networks in the filter network and merging the sub-networks;

wherein the display of the filter network is optimized by steps comprising;

identifying two filter sub-networks that generate the same query language logical structure;

determining whether the two filter sub-networks can be merged; and

if so, then merging the two filter sub-networks;

wherein the determining step comprises the steps of;

(a) determining whether the head filter node associated with one-of the sub-networks is not logically ORed to a parent filter node;

(b) determining whether the head filter node associated with the other sub-network is not logically ANDed to a parent filter node; and

if the determining steps of (a) and (b) are true, then determining that the two filter sub-networks can be merged.

35. A visualization optimization method for viewing conditions associated with base queries, comprising the steps of:

receiving a database query described by a query language logical structure;

generating a filter network comprising a plurality of filter nodes, wherein the structure of the filter network corresponds to the logical structure of the query;

optimizing the structure of the filter network by identifying pairs of redundant filter nodes the filter network and deleting one of the redundant nodes in the pair;

optimizing display of the filter network by identifying similar sub-networks in the filter work and merging the sub-networks; and

displaying on a graphical display the optimized filter network.