Patent ID: 8447724

Claim:
A method for determining metadata associated with a graph-based computation by a process executed on a computer system, the method including: generating a partial ordering of graph elements in a graph, the partial ordering determined at least in part by links representing data flows interconnecting the graph elements; and determining metadata of the graph elements according to the partial ordering, including propagating metadata internally within individual graph elements, and propagating metadata externally between different graph elements, the internal metadata propagation including functionally transforming metadata that specifies at least one characteristic of data processed by a first portion of the graph to generate transformed metadata that specifies at least one characteristic of data processed by a second portion of the graph, and the external metadata propagation including identifying a third portion of the graph related to the second portion of the graph by a link representing a first data flow of data elements output from the second portion of the graph and received at the third portion of the graph, 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 first data flow of data elements, and after propagating the transformed metadata, moving a graph element in the third portion of the graph to the end of the partial ordering.