A 1NF temporal relational model and algebra coping with valid-time temporal indeterminacy

In the real world, many phenomena are time related and in the last three decades the database community has devoted much work in dealing with \"time of facts\" in databases. While many approaches incorporating time in the relational model have been already devised, most of them assume that the exact time of facts is known. However, this assumption does not hold in many practical domains, in which temporal indeterminacy of facts occurs. The treatment of valid-time indeterminacy requires in-depth extensions to the current relational approaches. In this paper, we propose a theoretically grounded approach to cope with this issue, overcoming the limitations of related approaches in the literature. In particular, we present a 1NF temporal relational model and propose a new temporal relational algebra to query it. We also formally study the properties of the new data model and algebra, thus granting that our approach is interoperable with pre-existent temporal and non-temporal relational approaches, and is implementable on top of them. Finally, we consider computational complexity, showing that only a limited overhead is added when moving from determinate to indeterminate time.