Traversal algorithm

A provenance chain can be traversed to look up information sources and origins of a described object. The baseline algorithm below traverses the traversal information of the finalized provenance components in a provenance chain. The Examples show its use.

Input

• The identifier of a forward connector representing the described object that is the subject of the query.
• The identifier of the finalized provenance component in which the traversal starts, i.e. the component documenting the described activity that produced the described object.

Alternatively, the identifier of the described object may be used, provided that it can be linked to a backward or forward connector.

Steps

1. Access the finalized provenance component using its identifier, check its content, and verify the type of the input connector.
2. If the type is not correct, report an error.
3. Otherwise:
   1. find all backward connectors from which the input forward connector is derived, using the derivation relations between the forward and backward connectors (or the redundant connectors);
   2. for each backward connector found, run the algorithm with the identifier of the backward connector and the component identifier given by its attribute cpm:referencedBundleId. In the referenced component, the connector with this identifier is a forward connector.
4. Terminate when no new backward connectors are found.

Step 3b can be performed in a recursive or non-recursive, and federated or non-federated way, which determines who can see the response. The algorithm can be run in the forward direction analogously, using the forward connectors.

Properties

• Termination. The algorithm always terminates: provenance chains are finite and contain no cycles, because derivation relations over connectors represent a temporal ordering and a connector is never derived from itself, directly or indirectly.
• Access control. Authorization is part of accessing the content of a component. The algorithm is therefore provided only with the finalized provenance components and their parts that the user is authorized to access.

Queries on domain-specific information

Some queries can be answered from the traversal information alone, e.g. the connector and component identifiers of all documented precursors of a described object. Other queries require information from the domain-specific part. To avoid traversing the domain-specific part of every component, the traversal information can indicate which information is present in the domain-specific part, e.g. by the type of the main activity (see the Examples). Defining such indicators is the purpose of domain- and scenario-specific adoptions of CPM.