Approximate Interval-Based Temporal Dependencies: The Complexity Landscape

Temporal functional dependencies (TFDs) add valid time to classical functional dependencies (FDs) in order to express data integrity constraints over the flow of time. If the temporal dimension adopted is an interval, we have to deal with interval-based temporal functional dependencies (ITFDs for short), which consider different interval relations between valid times of related tuples. The related approximate problem is when we want to check if our data satisfy, without any constraint for the schema, a given ITFD under a given error threshold 0 ≤ d ≤ 1. This can be rephrased as: given a relation instance r, is it possible to delete at most c · |r| tuples from it in such a way that the resulting instance satisfies the given ITFD? This optimization problem, ITFD-Approx for short, may represent a way to discover (data mining) important dependencies among attribute values in a database as well as a way to control data consistency. In this paper we analyze the complexity of problem ITFD-Approx restricting ourselves to Allen's interval relations: we will see how the complexity of such a problem may significantly change, depending on the considered interval relation.