Skip to main content
Probabilistic Temporal Databases, I: Algebra
ACM Transactions on Database Systems
  • Alex Dekhtyar, University of Kentucky
  • Robert Ross, University of Maryland - College Park
  • V. S. Subrahmanian, University of Maryland - College Park
Publication Date
Dyreson and Snodgrass have drawn attention to the fact that in many temporal database applications, there is often uncertainty present about the start time of events, the end time of events, the duration of events, etc. When the granularity of time is small (e.g. milliseconds), a statement such as "Packet p was shipped sometime during the first 5 days of January, 1998" leads to a massive amount of uncertainty (5 X 24 X 60 X 60 X 1000) possibilities. As noted in [41], past attempts to deal with uncertainty in databases have been restricted to relatively small amounts of uncertainty in attributes. Dyreson and Snodgrass have taken an important first step towards solving this problem.In this paper, we first introduce the syntax of Temporal-Probabilistic (TP) relations and then show how they can be converted to an explicit, significantly more space-consuming form called Annotated Relations. We then present a Theoretical Annotated Temporal Algebra (TATA). Being explicit, TATA is convenient for specifying how the algebraic operations should behave, but is impractical to use because annotated relations are overwhelmingly large.Next, we present a Temporal Probabilistic Algebra (TPA). We show that our definition of the TP-Algebra provides a correct implementation of TATA despite the fact that it operates on implicit, succinct TP-relations instead of the overwhelmingly large annotated relations. Finally, we report on timings for an implementation of the TP-Algebra built on top of ODBC
Publisher statement
This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Transactions on Database Systems
Citation Information
Alex Dekhtyar, Robert Ross and V. S. Subrahmanian. "Probabilistic Temporal Databases, I: Algebra" ACM Transactions on Database Systems Vol. 26 Iss. 1 (2001) p. 41 - 95
Available at: