Interval-based temporal functional dependencies: specification and verification

In the temporal database literature, every fact stored in a database may beequipped with two temporal dimensions: the valid time, which describes the time whenthe fact is true in the modeled reality, and the transaction time, which describes the timewhen the fact is current in the database and can be retrieved. Temporal functional dependencies(TFDs) add valid time to classical functional dependencies (FDs) in order to expressdatabase integrity constraints over the flow of time. Currently, proposals dealing with TFDsadopt a point-based approach, where tuples hold at specific time points, to express integrityconstraints such as “for each month, the salary of an employee depends only on his role”. Tothe best of our knowledge, there are no proposals dealing with interval-based temporal functionaldependencies (ITFDs), where the associated valid time is represented by an intervaland there is the need of representing both point-based and interval-based data dependencies.In this paper, we propose ITFDs based on Allen’s interval relations and discuss theirexpressive power with respect to other TFDs proposed in the literature: ITFDs allow us toexpress interval-based data dependencies, which cannot be expressed through the existingpoint-based TFDs. ITFDs allow one to express constraints such as “employees starting towork the same day with the same role get the same salary” or “employees with a given roleworking on a project cannot start to work with the same role on another project that willend before the first one”. Furthermore, we propose new algorithms based on B-trees to efficientlyverify the satisfaction of ITFDs in a temporal database. These algorithms guaranteethat, starting from a relation satisfying a set of ITFDs, the updated relation still satisfies thegiven ITFDs.