Method and apparatus for maintaining and processing provenance data in data stream processing system

Apparatus for processing data associated with a data stream received by a data stream processing system, wherein the system comprises a plurality of processing elements, the apparatus comprising:

• a memory;
• and
• a processor coupled to the memory and configured to:
• maintain a portion of data associated with the data stream, wherein the maintained data comprises inputs to each processing element that contributed to an output of each processing element;
• in response to an alert generated by one of the processing elements, trigger a scheduler to determine when a pre-calculation of a prospective query related to the alert should be executed;
• and
• when the scheduler determines that a pre-calculation of a prospective query related to the alert should be executed, use at least a portion of the maintained data to determine a set of data that contributed to the alert such that the alert-contributing set of data can be used to respond to the prospective query upon arrival thereof,
• wherein determination of the alert-contributing set of data comprises:
• representing the data stream processing system as a processing graph wherein nodes of the processing graph correspond to processing elements in the data stream processing system and links in the processing graph correspond to communication paths between the processing elements;
• creating an overlay graph wherein nodes in the overlay graph correspond to nodes in the processing graph, and links in the overlay graph correspond to links in the processing graph wherein each link in the overlay graph is a reverse of the corresponding link in the processing graph, and the overlay nodes operate concurrently with the nodes in the processing graph, wherein the overlay graph and the corresponding processing graph are separate entities;
• starting with a node that generated the alert, each node uses dependency information to forward to its linked nodes data that was forwarded to its corresponding node in the processing graph from the processing graph node corresponding to the linked node and that contributed to the alert;
• and
• continuing with backtrack processing to the overlay nodes that correspond to an input node of the processing graph until all data stream data and all functions executing on the processing node graph that contributed to the alert have been specified.

An article of manufacture for processing data associated with a data stream received by a data stream processing system, wherein the system comprises a plurality of processing elements, the article comprising a computer readable storage medium having one or more programs embodied therewith wherein the one or more programs, when executed by a computer, perform steps of:

• maintaining a portion of data associated with the data stream, wherein the maintained data comprises inputs to each processing element that contributed to an output of each processing element;
• in response to an alert generated by one of the processing elements, triggering a scheduler to determine when a pre-calculation of a prospective query related to the alert should be executed;
• and
• when the scheduler determines that a pre-calculation of a prospective query related to the alert should be executed, using at least a portion of the maintained data to determine a set of data that contributed to the alert such that the alert-contributing set of data can be used to respond to the prospective query upon arrival thereof,
• wherein determination of the alert-contributing set of data comprises:
• representing the data stream processing system as a processing graph wherein nodes of the processing graph correspond to processing elements in the data stream processing system and links in the processing graph correspond to communication paths between the processing elements;
• creating an overlay graph wherein nodes in the overlay graph correspond to nodes in the processing graph, and links in the overlay graph correspond to links in the processing graph wherein each link in the overlay graph is a reverse of the corresponding link in the processing graph, and the overlay nodes operate concurrently with the nodes in the processing graph, wherein the overlay graph and the corresponding processing graph are separate entities;
• starting with a node that generated the alert, each node uses dependency information to forward to its linked nodes data that was forwarded to its corresponding node in the processing graph from the processing graph node corresponding to the linked node and that contributed to the alert;
• and
• continuing with backtrack processing to the overlay nodes that correspond to an input node of the processing graph until all data stream data and all functions executing on the processing node graph that contributed to the alert have been specified.