Managing metadata for graph-based computations

• US 7,877,350 B2
• Filed: 06/27/2005
• Issued: 01/25/2011
• Est. Priority Date: 06/27/2005
• Status: Active Grant

• Current Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Original Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Inventors: Larson, Brond, Allin, Glenn John, Wholey, J. Skeffington, Stanfill, Craig W.
• Primary Examiner(s): Fleurantin; Jean B.
• Assistant Examiner(s): Kerzhner; Aleksandr
• Application Number:
  US11/167,902
• Publication Number:
  US 20060294150A1
• Time in Patent Office: 2,038 Days
• Field of Search: 707/101, 707/609, 707/999.101
• US Class Current: 707/609
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• 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/24526 Internal representations for queries
• CPC Class Codes: G06F 8/51 Source to source

Abstract

Determining metadata associated with a graph-based computation includes functionally transforming metadata associated with a first portion of a graph to generate transformed metadata associated with a second portion of the graph; determining a third portion of the graph related to the second portion of the graph; and propagating the transformed metadata from the second portion of the graph to the third portion of the graph.

Claims

1. A method for determining metadata associated with a graph-based computation, the method including:

functionally transforming metadata, different from data processed by a first portion of a graph, that specifies at least one characteristic of data processed by the first portion of the graph to generate transformed metadata, different from data processed by a second portion of the graph, that specifies at least one characteristic of data processed by the second portion of the graph, wherein the first portion includes a first port of a first graph element and the second portion includes a second port of the first graph element;

determining a third portion of the graph related to the second portion of the graph by a link representing a data flow of data elements output from the second portion of the graph and received at the third portion of the graph, wherein the third portion of the graph includes an input port of a second graph element; and

propagating the transformed metadata that was generated for the second portion of the graph to the third portion of the graph according to the link representing the data flow of data elements;

wherein the transformed metadata that was generated for the second portion of the graph specifies at least one characteristic of the data elements output from the second portion of the graph and received at the third portion of the graph; and

generating a partial ordering of graph elements in the graph including the first graph element and the second graph element, the partial ordering determined at least in part by links representing data flows interconnecting the graph elements, and determining metadata for ports of the graph elements according to the partial ordering, and after propagating the transformed metadata to the input port of the second graph element, moving the second graph element to the end of the partial ordering.

2. The method of claim 1, wherein the data flow includes a data flow between ports of two interconnected graph elements.

3. The method of claim 1, wherein the data flow includes an internal data flow between two ports of a graph element.

4. The method of claim 1, wherein the functional transformation includes a metadata definition that includes at least one reference to the metadata that specifies at least one characteristic of data processed by the first port.

5. The method of claim 4, wherein the metadata definition defines metadata for the second port as a function of the referenced metadata.

6. The method of claim 1, wherein the first port is an input port and the second port is an output port.

7. The method of claim 1, wherein the metadata being functionally transformed is supplied by a user.

8. The method of claim 1, wherein the metadata being functionally transformed is propagated from a fourth portion of the graph.

9. The method of claim 1, further including propagating the transformed metadata in response to a change in connectivity of the graph.

10. The method of claim 1, further including propagating the transformed metadata in response to a user action.

11. The method of claim 1, further including:

receiving a request from a user; and

displaying metadata that specifies at least one characteristic of data processed by a graph element to the user in response to the request.

12. The method of claim 11, wherein the request from the user includes input from the user selecting a graph element for which metadata is to be displayed.

13. The method of claim 12, wherein the input from the user includes positioning an on-screen pointer near a graphical representation of the selected graph element for a predetermined amount of time.

14. The method of claim 11, wherein the displayed metadata includes metadata propagated from another graph element.

15. The method of claim 11, wherein the displayed metadata is displayed before the graph-based computation specified by the graph is run.

16. The method of claim 1, further comprising:

outputting data elements processed according to the transformed metadata from the second portion of the graph; and

processing data elements received at the third portion of the graph according to the transformed metadata.

17. The method of claim 1, wherein the data elements output from the second portion of the graph and received at the third portion of the graph include records and the transformed metadata describes at least one of:

a sequence of fields of the records, and data types corresponding to values in the record.

18. Software stored on a computer-readable medium, for determining metadata associated with a graph-based computation, the software including instructions for causing a computer system to:

functionally transform metadata, different from data processed by a first portion of a graph, that specifies at least one characteristic of data processed by the first portion of the graph to generate transformed metadata, different from data processed by a second portion of the graph, that specifies at least one characteristic of data processed by the second portion of the graph, wherein the first portion includes a first port of a first graph element and the second portion includes a second port of the first graph element;

determine a third portion of the graph related to the second portion of the graph by a link representing a data flow of data elements output from the second portion of the graph and received at the third portion of the graph, wherein the third portion of the graph includes an input port of a second graph element; and

propagate the transformed metadata that was generated for the second portion of the graph to the third portion of the graph according to the link representing the data flow of data elements;

wherein the transformed metadata that was generated for the second portion of the graph specifies at least one characteristic of the data elements output from the second portion of the graph and received at the third portion of the graph; and

generate a partial ordering of graph elements in the graph including the first graph element and the second graph element, the partial ordering determined at least in part by links representing data flows interconnecting the graph elements, and determining metadata for ports of the graph elements according to the partial ordering, and after propagating the transformed metadata to the input port of the second graph element, moving the second graph element to the end of the partial ordering.

19. The software of claim 18, wherein the data flow includes a data flow between ports of two interconnected graph elements.

20. The software of claim 18, wherein the data flow includes an internal data flow between two ports of a graph element.

21. The software of claim 18, wherein the functional transformation includes a metadata definition that includes at least one reference to the metadata that specifies at least one characteristic of data processed by the first port.

22. The software of claim 21, wherein the metadata definition defines metadata for the second port as a function of the referenced metadata.

23. The software of claim 18, wherein the first port is an input port and the second port is an output port.

24. The software of claim 18, wherein the metadata being functionally transformed is supplied by a user.

25. The software of claim 18, wherein the metadata being functionally transformed is propagated from a fourth portion of the graph.

26. The software of claim 18, wherein the data elements output from the second portion of the graph and received at the third portion of the graph include records and the transformed metadata describes at least one of:

a sequence of fields of the records, and data types corresponding to values in the record.

27. A system for determining metadata associated with a graph-based computation, the system including:

means for functionally transforming metadata, different from data processed by a first portion of a graph, that specifies at least one characteristic of data processed by the first portion of the graph to generate transformed metadata, different from data processed by a second portion of the graph, that specifies at least one characteristic of data processed by the second portion of the graph, wherein the first portion includes a first port of a first graph element and the second portion includes a second port of the first graph element;

means for determining a third portion of the graph related to the second portion of the graph by a link representing a data flow of data elements output from the second portion of the graph and received at the third portion of the graph, wherein the third portion of the graph includes an input port of a second graph element; and

means for propagating the transformed metadata that was generated for the second portion of the graph to the third portion of the graph according to the link representing the data flow of data elements;

wherein the transformed metadata that was generated for the second portion of the graph specifies at least one characteristic of the data elements output from the second portion of the graph and received at the third portion of the graph; and

means for generating a partial ordering of graph elements in the graph including the first graph element and the second graph element, the partial ordering determined at least in part by links representing data flows interconnecting the graph elements, and determining metadata for ports of the graph elements according to the partial ordering, and after propagating the transformed metadata to the input port of the second graph element, moving the second graph element to the end of the partial ordering.

28. The system of claim 27, wherein the data flow includes a data flow between ports of two interconnected graph elements.

29. The system of claim 27, wherein the data flow includes an internal data flow between two ports of a graph element.

30. The system of claim 27, wherein the functional transformation includes a metadata definition that includes at least one reference to the metadata that specifies at least one characteristic of data processed by the first port.

31. The system of claim 30, wherein the metadata definition defines metadata for the second port as a function of the referenced metadata.

32. The system of claim 27, wherein the first port is an input port and the second port is an output port.

33. The system of claim 27, wherein the metadata being functionally transformed is supplied by a user.

34. The system of claim 27, wherein the metadata being functionally transformed is propagated from a fourth portion of the graph.

35. The system of claim 27, wherein the data elements output from the second portion of the graph and received at the third portion of the graph include records and the transformed metadata describes at least one of:

a sequence of fields of the records, and data types corresponding to values in the record.