US 9,069,808 B2Granted

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

AssigneeInternational Business Machines Corporation

InventorsAnastasios Kementsietsidis, Min Wang

Life of this patent

Estimating the term…

Loading patent…

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.

Claims25

Dependent claims

A method for processing one or more queries directed toward data associated with a data processing system, the method comprising steps of:

mapping one or more data items of a first data set associated with the data processing system to a first representation type, wherein the data items of the first data set comprise output data items;
mapping one or more data items of a second data set associated with the data processing system to a second representation type, wherein the data items of the second data set comprise input data items;
computing 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, wherein the bi-directional index is computed in terms of the first representation type and the second representation type, wherein the first representation type comprises labels and the second representation type comprises objects, and wherein the bi-directional index is a persistent structure that does not store annotations of the data items, wherein computing a bi-directional index comprises:
creating a first binary matrix, wherein rows of the first binary matrix represent labels, columns of the binary matrix represent objects, and an entry [i, j] in the first binary matrix is set to a first binary value when a label of row i is associated with an object of column j for a given data provenance relation;
and
computing a plurality of vectors based on entries of the first binary matrix, the plurality of vectors comprising a compressed representation of entries of the first binary matrix;
performing a provenance query evaluation using the bi-directional index, in response to receipt of a provenance query, wherein the bi-directional index is used for the query evaluation whether the received provenance query is a backward provenance query or a forward provenance query, wherein a backward provenance query provides an indication as to which input data items, generate a specific output data item, and wherein a forward provenance query provides an indication as to what influence an input data item has on a generation of which output data items, wherein the provenance query evaluation is performed using the bi-directional index without access to the input and output data items, wherein performing the provenance query evaluation comprises performing a search over the compressed representation of entries of the first binary matrix provided by plurality of vectors;
and
generating a response for the received provenance query based on a result of the query evaluation;
wherein the mapping, computing, performing, and generating steps are executed on a computing system comprising a processor and a memory, wherein one or more software modules for implementing the mapping, computing, and performing steps are loaded from the memory and executed by the processor.

7 more elements

Apparatus for processing one or more queries directed toward data associated with a data processing system, the apparatus comprising:

a memory;
and
a processor coupled to the memory and configured to:
(i) map one or more data items of a first data set associated with the data processing system to a first representation type, wherein the data items of the first data set comprise output data items, and to map one or more data items of a second data set associated with the data processing system to a second representation type, wherein the data items of the second data set comprise input data items;
(ii) compute 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, wherein the bi-directional index is computed in terms of the first representation type and the second representation type, wherein the first representation type comprises labels and the second representation type comprises objects, and wherein the bi-directional index is a persistent structure that does not store annotations of the data items, wherein computing a bi-directional index comprises:
creating a first binary matrix, wherein rows of the first binary matrix represent labels, columns of the binary matrix represent objects, and an entry [i, j] in the first binary matrix is set to a first binary value when a label of row i is associated with an object of column j for a given data provenance relation;
and
computing a plurality of vectors based on entries of the first binary matrix, the plurality of vectors comprising a compressed representation of entries of the first binary matrix;
(iii) perform a provenance query evaluation using the bi-directional index, in response to receipt of a provenance query, wherein the bi-directional index is used for query evaluation whether the received provenance query is a backward provenance query or a forward provenance query, wherein a backward provenance query provides an indication as to which input data items generate a specific output data item, and wherein a forward provenance query provides an indication as to what influence an input data item has on a generation of which output data items wherein the provenance query evaluation is performed using the bi-directional index without access to the input and output data items, wherein performing the provenance query evaluation comprises performing a search over the compressed representation of entries of the first binary matrix provided by plurality of vectors;
and
(iv) generate a response for the received provenance query based on a result of the query evaluation.

8 more elements

A computer program product comprising a non-transitory computer readable storage medium including computer usable program code stored thereon for processing one or more queries directed toward data associated with a data processing system, the computer program product comprising:

computer usable program code for mapping one or more data items of a first data set associated with the data processing system to a first representation type, wherein the data items of the first data set comprise output data items, and for mapping one or more data items of a second data set associated with the data processing system to a second representation type, wherein the data items of the second data set comprise input data items;
computer usable program code for computing 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, wherein the bi-directional index is computed in terms of the first representation type and the second representation type, wherein the first representation type comprises labels and the second representation type comprises objects, and wherein the bi-directional index is a persistent structure that does not store annotations of the data items, wherein computing a bi-directional index comprises:
creating a first binary matrix, wherein rows of the first binary matrix represent labels, columns of the binary matrix represent objects, and an entry [i, j] in the first binary matrix is set to a first binary value when a label of row i is associated with an object of column j for a given data provenance relation;
and
computing a plurality of vectors based on entries of the first binary matrix, the plurality of vectors comprising a compressed representation of entries of the first binary matrix;
computer usable program code for performing a provenance query evaluation using the bi-directional index, in response to receipt of a provenance query, wherein the bi-directional index is used for query evaluation whether the received provenance query is a backward provenance query or a forward provenance query, wherein a backward provenance query provides an indication as to which input data items generate a specific output data item, and wherein a forward provenance query provides an indication as to what influence an input data item has on a generation of which output data items, wherein the provenance query evaluation is performed using the bi-directional index without access to the input and output data items, wherein performing the provenance query evaluation comprises performing a search over the compressed representation of entries of the first binary matrix provided by plurality of vectors;
and
computer usable program code for generating a response for the received provenance query based on a result of the query evaluation.

5 more elements

Dependencies are inferred from the claim text.