Indexing provenance data and evaluating provenance data queries in data processing systems

Abstract

Techniques for indexing provenance data and evaluating provenance data queries are disclosed. For example, a method for processing one or more queries directed toward data associated with a data processing system comprises the following steps. One or more data items of a first data set associated with the data processing system are mapped to a first representation type and one or more data items of a second data set associated with the data processing system are mapped to a second representation type. A bi-directional index of a data provenance relation existing between the data items of the first data set and the data items of the second data set is computed. The bi-directional index is computed in terms of the first representation type and the second representation type. A query evaluation is performed using the bi-directional index, in response to receipt of a provenance query. The bi-directional index is used for query evaluation whether the received provenance query is a backward provenance query or a forward provenance query. A response is generated for the received provenance query based on a result of the query evaluation. In one further example, the provenance query evaluation step may be performed by using only the bi-directional index and does not require access to base data or maintaining stored provenance data.