Interactive data exploration apparatus and methods

• US 5,999,192 A
• Filed: 04/30/1996
• Issued: 12/07/1999
• Est. Priority Date: 04/30/1996
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Srivastava, Divesh, Selfridge, Peter Gilman
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/640,411
• Time in Patent Office: 1,316 Days
• Field of Search: 395/140, 395/141, 395/142, 395/143, 345/440, 345/441, 345/433, 345/333, 345/334, 345/335
• US Class Current: 345/440
• CPC Class Codes: G06F 16/26 Visual data mining; Browsing structured data

Abstract

A data exploration tool which has a graphical user interface that employs directed graphs to provide histories of the data exploration operations. Nodes in the directed graphs represent operations on data; the edges represent relationships between the operations. One type of the directed graphs is the derivation graph, in which the root of the graph is a node representing a data set and an edge leading from a first node to a second node indicates that the operation represented by the second node is performed on the result of the operation represented by the first node. Operations include query, segmentation, aggregation, and data view operations. A user may edit the derivation graph and may select a node for execution. When that is done, all of the operations represented by the nodes between the root node and the selected node are performed as indicated in the graph. The operations are performed using techniques of lazy evaluation and encachement of results with the nodes. Another type of the directed graphs is the subsumption graph, in which an edge leading from a first node to a second node indicates that the second node stands in a subsumption relationship to the first node. If a result of the operation represented by the first node has been computed, the result is available to calculate the result of the operation represented by the second node.

Claims

1. A business data exploration and analysis apparatus for discovering useful patterns in database information and for interactively specifying one or more operations on business data stored as database information, the apparatus being employed in a system which has a display, an input device, and access to the business data and the apparatus comprising:

a first acyclical directed graph of one or more nodes and edges in the display, a node in the first acyclical directed graph representing a business data operation and an edge ending in a node in the first acyclical directed graph indicating that the node from which the edge comes is a source of business data for the operation performed by the node at which the edge ends, the first acyclical directed graph providing a derivational history of the operation or operations on the business data, at least one operation comprising a query, segmentation, aggregation or a viewer operation to determine useful patterns in the business data by determining relationships in the business data, and

first means responsive to the input device for executing operations specified in nodes of the first graph on the business data specified by the edges thereof.

2. The apparatus set forth in claim 1 wherein:

the first graph further includes a root node representing a source of the data.

3. The apparatus set forth in claim 2 wherein:

the input device selects a node of the first graph and

the first means responsive to the input device executes the operations in the nodes between the selected node and the root node, the operations being executed on the data specified by the edges beginning at the root node.

4. The apparatus set forth in claim 2 wherein:

the operations specified by the first graph are parameterized by the properties of the source of data represented by the root node, whereby the operations may be performed on any other source of data which has those properties.

5. The apparatus set forth in claim 1 further comprising:

second means responsive to the input device for adding a node to the first graph.

6. The apparatus set forth in claim 5 wherein:

the second means further specifies a constraint associated with the operation represented by the added node.

7. The apparatus set forth in claim 5 wherein:

the second means does not cause the operation specified by the added node to be performed.

8. The apparatus set forth in claim 1 further comprising:

means for associating result data produced by the operation represented by a node with the node; and

the first means responsive to the input device uses any result data associated with a node when the first means executes the operations.

9. The apparatus set forth in claim 8 further comprising:

a data structure representing a second acyclic directed graph of one or more of the nodes and additional edges in the display, the additional edges indicating subsumption relationships between the results of the operations represented by the nodes connected by the additional edges,

the first means responsive to the input device using the data structure to locate a subsuming node having result data associated therewith and using the result data to execute an operation specifed by a subsumed node.

10. The apparatus set forth in any one of claims 1 through 8 wherein:

the data is stored in a data base; and

the operations on the data represented by the nodes include a data base operation which performs a data base operation on the data.

11. The apparatus set forth in claim 10 wherein:

the data base operation is a query operation which employs constraints to produce a subset of the data produced by an operation represented by a node from which an edge leads to the node representing the query operation.

12. The apparatus set forth in claim 10 wherein:

the data base operation is a segmentation operation which divides the data produced by an operation represented by a node from which an edge leads to the node representing the segmentation into non-overlapping groups according to values of an attribute of the data.

13. The apparatus set forth in claim 10 wherein:

the data base operation is an aggregation operation which provides summary information about data produced by an operation represented by a node from which an edge leads to the node representing the aggregation operation.

14. The apparatus set forth in claim 13 wherein:

the aggregation operation is in the alternative a count operation, a sum operation, or an average operation.

15. The apparatus set forth in claim 10 wherein:

the system includes a data base server upon which the data base is stored and a client which includes the display and the input device; and

the client performs the data base operation by sending a message to the server which specifies the data base operation, the server responding thereto by performing the data base operation and returning a message containing a result thereof to the client.

16. The apparatus set forth in claim 10 wherein

the apparatus further comprises:

means for providing information about the first graph to the data base for storage therein; and

means for producing the first graph by retrieving the stored information about the first graph from the data base.

17. The apparatus set forth in any one of claims 1 through 8 wherein:

the operations on the data represented by the nodes include a viewer operation which displays a result of an operation represented by a node from which an edge leads to the node representing the viewer operation.

18. The apparatus set forth in any one of claims 1 through 8 wherein:

the operations on the data represented by the nodes includes an external tool operation which applies a tool accessible to the system to a result of an operation represented by a node from which an edge leads to the node representing the external tool operation.

19. The apparatus set forth in any one of claims 1 through 8 wherein the system further includes persistent storage means and the apparatus further comprises:

means for storing a representation of the first graph in the persistent storage means and

means for using the stored representation to produce the first graph.

20. The apparatus set forth in claims 1 through 8 comprising:

a second acyclic directed graph of one or more of the nodes and additional edges in the display, the additional edges indicating subsumption relationships between the results of the operations represented by the nodes connected by the edges.

21. The apparatus of any one of claims 1 through 8, further comprising memory storing code and a processor for executing the code to implement the system.

22. A business data exploration and analysis apparatus for discovering useful patterns in data base information and for interactively specifying one or more operations to determine useful patterns in the business data by determining relationships in the business data, each operation having source data and result data and the apparatus being employed in a system which has a display, an input device for specifying the operations, and access to the data, the apparatus further comprising a first acyclical directed graph of one or more nodes and edges in the display for representing in the display a plurality of different relationships between the result data produced by a first operation and the result data produced by a second operation a node in the first acyclical directed graph representing a business data operation and an edge ending in a node in the first acyclical directed graph indicating that the node from which the edge comes is a source of business data for the operation performed by the node at which the edge ends, the first acyclical directed graph providing a derivational history of the operation or operations on the business data at least one operation comprising a query, segmentation, aggregation or a viewer operation to determine useful patterns in the business data by determining relationships in the business data.

23. The apparatus of claim 22 wherein:

the plurality of different relationships include a derivation relationship wherein the result data produced by the first operation is the source data for the second operation.

24. The apparatus of claim 23 wherein:

the plurality of different relationships include a subsumption relationship wherein the result data produced by the second operation is subsumed in the result data produced by the first operation.

25. The apparatus of claim 24 wherein:

the subsumption relationship is a query--query relationship wherein the result data produced by the first and second operations are sets of data and the set of data produced by the second operation may be described by means of a constraint on the set of data produced by the first operation.

26. The apparatus of claim 24 wherein:

the subsumption relationship is a segmentation--segmentation relationship wherein the result data produced by the first and second operations are segmentations of a set of data and the segmentation produced by the second operation may be described as a further segmentation of the segmentation produced by the first operation.

27. The apparatus of claim 24 wherein:

the subsumption relationship is a query-segmentation relationship wherein the result data produced by the first operation is a set of data describable by means of a constraint on another set of data and the result data produced by the second operation is describable as a segmentation of the result data produced by the first operation.

28. The apparatus of claim 24 wherein:

the subsumption relationship is a segmentation-query relationship wherein the result data produced by the first operation is a segmentation of another set of data and the query produces a set of data for each segment of the segmentation which is describable by means of a constraint on the segment.

29. The apparatus set forth in any one of claims 22 through 28 wherein:

there is a plurality of the first and second operations and at least one of the representations is a directed graph wherein the first and second operations are represented by nodes in the graph and the relationships are represented by edges connecting the nodes.

30. The apparatus set forth in claim 29 wherein

a plurality of the representations are represented by the directed graphs;

and

the apparatus further comprises;

means responsive to the input device for selecting a directed graph for display.

31. The apparatus set forth in claim 30 wherein:

one of the directed graphs is displayed as an overlay of another of the directed graphs.

32. The apparatus of any one of the claims 22 through 28 further comprising a memory which stores code and a processor for executing the code to implement the system.