1. A method for optimizing provenance query response time, comprising: providing relevancy criteria that evaluates input data elements prior to an occurrence of a provenance query to dynamically select a provenance function backtracing method for responding to the provenance query that optimizes a response time of the provenance query; evaluating, by a hardware processor using the relevancy criteria, said input data elements to determine whether an input window comprising said input data elements includes a sufficient amount of relevant input data with respect to the provenance query; and if said input window lacks the sufficient amount of relevant input data, designating, by the hardware processor, said input data elements for reference to an output data element in a cache in response to the provenance query.