Probabilistic Temporal Databases, I: Algebra
Probabilistic Temporal Databases, I: Algebra
Files
Publication or External Link
Date
1999-01-27
Authors
Dekhtyar, Alex
Ross, Robert
Subrahmanian, V. S.
Advisor
Citation
DRUM DOI
Abstract
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 times 24 times 60 times 60 times 1000) possibilities. As noted by
Zaniolo et. al., 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 {\em 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.
(Also cross-referenced as UMIACS-TR-99-09)