# US 2008/0307104 A1 · Methods and Apparatus for Functional Model-Based Data Provenance in Stream Processing Environments

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0307104 A1
- Document ID: US20080307104A1
- Status: Published application
- Kind: A1
- Application number: 11/760,070
- Filed: 2007-06-08
- Published: 2008-12-11
- Earliest claimed: 2007-06-08
- Assignees: International Business Machines Corporation
- Inventors: Lisa Amini; Marion Lee Blount; John Sidney Davis, II; Wim De Pauw; Archan Misra; Daby Mousse Sow; Chitra Venkatramani; Min Wang
- Web page: https://patentgrep.com/patent/US20080307104A1

## CPC

- G06F 16/24568: {Data stream processing; Continuous queries}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Techniques for deriving a provenance of one or more of a plurality of output data elements generated from a given output port of a PC are provided. At least one dependency function is created that relates the one or more output data elements to a set of one or more input ports of the PC and a corresponding plurality of input data elements. The dependency function comprises an encoding of at least one of one or more temporal filters and one or more sequence filters relating to the plurality of input data elements. The at least one dependency function is stored. A history of stream-level bindings of one or more input streams to one or more input ports of the processing component and one or more output streams from one or more output ports of the processing component is stored. The plurality of input data elements belonging to the one or more input streams and the plurality of output data elements belonging to the one or more output streams are stored. The set of one or more input data elements from the plurality of input data elements are determined that relate to the one or more output data elements in accordance with at least one dependency function and the history of stream-level bindings.

## Claims

### Claim 1

A method for deriving a provenance of one or more of a plurality of output data elements generated from a given output port of a processing component comprising the steps of:
creating at least one dependency function that relates the one or more output data elements to a set of one or more input ports of the processing component and a corresponding plurality of input data elements, wherein the dependency function comprises an encoding of at least one of one or more temporal filters and one or more sequence filters relating to the plurality of input data elements;
storing the at least one dependency function;
storing a history of stream-level bindings of one or more input streams to one or more input ports of the processing component and one or more output streams from one or more output ports of the processing component, and storing the plurality of input data elements belonging to the one or more input streams and the plurality of output data elements belonging to the one or more output streams; and
determining a set of one or more input data elements from the plurality of input data elements that relate to the one or more output data elements in accordance with the at least one dependency function and the history of stream-level bindings.

### Claim 2 (depends on 1)

The method of claim 1, wherein, in the step of creating a dependency function, the dependency function comprises an encoding of one or more temporal filters and dependency is specified in terms of sets of past time windows relative to a time at which the one or more output data elements are generated.

### Claim 3 (depends on 1)

The method of claim 1, wherein, in the step of creating a dependency function, the dependency function comprises an encoding of one or more sequence filters and dependency is specified in terms of sets of at least one of past sample windows and data element sequences relative to at least one of a time and a sequence identifier associated with the one or more output data elements.

### Claim 4 (depends on 1)

The method of claim 1, wherein the step of creating a dependency function comprises the step of associating a predicate-based dependency function, wherein dependency is defined in terms of one more predicates over the set of one or more input data elements.

### Claim 5 (depends on 1)

The method of claim 1, wherein the step of creating a dependency function comprises the step of associating a set of distinct dependency sub-functions, such that each sub-function is associated with a set of values assumed by internal or external state variables used by the processing component.

### Claim 6 (depends on 1)

The method of claim 1, wherein, in the step of creating a dependency function, the dependency function comprises an encoding of one or more temporal filters and one or more sequential filters.

### Claim 7 (depends on 1)

The method of claim 1, wherein the step of creating a dependency function comprises the step of associating a default dependency function that relates each output data element of the one or more output streams to all elements of the one or more input streams.

### Claim 8 (depends on 1)

The method of claim 1, wherein the step of storing the history of stream-level bindings comprises the step of storing a static set of bindings between streams and processing components.

### Claim 9 (depends on 1)

The method of claim 1, wherein the step of storing the history of stream-level bindings comprises the step of storing a dynamic set of time-varying bindings between streams and processing components.

### Claim 10 (depends on 1)

The method of claim 1, further comprising the step of storing a history of a state of the processing component, wherein the state comprises at least one of an internal state and an external state, and wherein the set of one or more input data elements is determined in accordance with the history of the state.

### Claim 11 (depends on 10)

The method of claim 10, wherein the step of storing the history of the state comprises the step of storing, on a persistent storage medium, at least one of the internal state of the processing component and the external state of an environment, separately and independently from the plurality of output data elements.

### Claim 12 (depends on 11)

The method of claim 11, wherein the step of storing on a persistent storage medium comprises the step of implicitly achieving the storage functionality using an external service that is able to retrieve contextual history of the environment at a future time.

### Claim 13 (depends on 10)

The method of claim 10, wherein the step of storing the history of the state comprises appending state information as metadata to one or more of the plurality of output data elements.

### Claim 14 (depends on 1)

The method of claim 1, wherein the step of determining the set of one or more input data elements comprises the steps of:
determining at least one of the one or more input streams that contributed to the generation of the one or more output data elements from the history of stream-level bindings; and
applying the at least one dependency function over the at least one of the one or more input streams to determine the set of one or more input data elements that satisfy the at least one dependency function.

### Claim 15 (depends on 14)

The method of claim 14, wherein the step of determining at least one of the one or more input streams comprises the steps of:
retrieving a generation time and a stream identifier of the one or more output data elements;
retrieving a set of input streams that were bound to the output port generating the said output stream identifier, with an appropriate time window prior to the generation time of the one or more output data elements.

### Claim 16 (depends on 14)

The method of claim 14, wherein the step of applying the at least one dependency function comprises progressively increasing the set of data elements, in reverse-temporal order, associated with the input streams, until the corresponding temporal, sequence or predicate based function is satisfied.

### Claim 17 (depends on 14)

The method of claim 14, wherein the step of applying the at least one dependency function comprises the steps of:
determining the set of all input streams that ever bound to the corresponding output port generating the said data stream prior to the generation time of said data element;
retrieving all the data elements for said set of input streams with generation timestamps prior to the generation time of said data element.

### Claim 18

Apparatus for deriving a provenance of one or more of a plurality of output data elements generated from a given output port of a processing component, comprising:
a memory; and
at least one processor coupled to the memory and operative to: (i) create at least one dependency function that relates the one or more output data elements to a set of one or more input ports of the processing component and a corresponding plurality of input data elements, wherein the dependency function comprises an encoding of at least one of one or more temporal filters and one or more sequence filters relating to the plurality of input data elements; (ii) store the at least one dependency function; (iii) store a history of stream-level bindings of one or more input streams to one or more input ports of the processing component and one or more output streams from one or more output ports of the processing component, and store the plurality of input data elements belonging to the one or more input streams and the plurality of output data elements belonging to the one or more output streams; and (iv) determine a set of one or more input data elements from the plurality of input data elements that relate to the one or more output data elements in accordance with the at least one dependency function and the history of stream-level bindings.

### Claim 19

A method for making a computer implemented process to enable derivation of a provenance of one or more of a plurality of output data elements generated from a given output port of a processing component comprising the steps of
instantiating first computer instructions onto a computer readable medium, the first computer instructions configured to create at least one dependency function that relates the one or more output data elements to a set of one or more input ports of the processing component and a corresponding plurality of input data elements, wherein the dependency function comprises an encoding of at least one of one or more temporal filters and one or more sequence filters relating to the plurality of input data elements;
instantiating second computer instructions onto a computer readable medium, the second computer instructions configured to store the at least one dependency function;
instantiating third computer instructions onto a computer readable medium, the third computer instructions configured to store a history of stream-level bindings of one or more input streams to one or more input ports of the processing component and one or more output streams from one or more output ports of the processing component, and store the plurality of input data elements belonging to the one or more input streams and the plurality of output data elements belonging to the one or more output streams; and
instantiating fourth computer instructions onto a computer readable medium, the fourth computer instructions configured to determine a set of one or more input data elements from the plurality of input data elements that relate to the one or more output data elements in accordance with the at least one dependency function and the history of stream-level bindings.
