Mining approximate interval-based temporal dependencies

Temporal functional dependencies add valid time to classical functional dependencies 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 tuple valid times. The related approximate problem is when we want to check whether our data satisfy, without any constraint for the schema, a given ITFD under a given error threshold 0 ⩽ ϵ⩽ 1. This can be rephrased as: given a relation instance r, is it possible to delete at most ϵ· | 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 (i.e., mine) important dependencies among attribute values in a database. In this paper we analyze the complexity of problem ITFD-Approx restricting ourselves to Allen’s interval relations: we shall see how the complexity of such a problem may significantly change, depending on the considered interval relation.