You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format. However, this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the Department of Computer Science of the University of Maryland at College Park under terms that include this permission. All other rights are reserved by the author(s).
Probabilistic Temporal Databases, I: Algebra. Alex Dekhtyar. Robert Ross. V. S. Subrahmanian. January 1999.
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) University of Maryland Institute for Advanced Computer Studies, Department of Computer Science, University of Maryland,
Hybrid Probabilistic Programs: Algorithms and Complexity. Michael Dekhtyar. Alex Dekhtyar. V.S. Subrahmanian. December 1998.
Hybrid Probabilistic Programs (HPPs) are logic programs that allow the programmer to explicitly encode his knowledge of the dependencies between events being described in the program. In this paper, we classify HPPs into three classes called HPP_1,HPP_2 and HPP_r for r >= 3. For these classes, we provide three types of results for HPPs. First, we develop algorithms to compute the set of all ground consequences of an HPP. Then we provide algorithms and complexity results for the problems of entailment (``Given an HPP P and a query Q as input, is Q a logical consequence of P?'') and consistency (``Given an HPP P as input, is P consistent?''). Our results provide a fine characterization of when polynomial algorithms exist for the above problems, and when these problems become intractable. (Also cross-referenced as UMIACS-TR-98-76) University of Maryland Institute for Advanced Computer Studies, Department of Computer Science, University of Maryland,
Hybrid Probabilistic Programs. Alex Dekhtyar. V. S. Subrahmanian. March 1998.
The precise probability of a compound event (e.g. e1 v e2, e1 ^ e2) depends upon the known relationships (e.g. independence, mutual exclusion, ignorance of any relationship, etc.) between the primitive events that constitute the compound event. To date, most research on probabilistic logic programming [20, 19, 22, 23, 24] has assumed that we are ignorant of the relationship between primitive events. Likewise, most research in AI (e.g. Bayesian approaches) have assumed that primitive events are independent. In this paper, we propose a hybrid probabilistic logic programming language in which the user can explicitly associate, with any given probabilistic strategy, a conjunction and disjunction operator, and then write programs using these operators. We describe the syntax of hybrid probabilistic programs, and develop a model theory and fixpoint theory for such programs. Last, but not least, we develop three alternative procedures to answer queries, each of which is guaranteed to be sound and complete. (Also cross-referenced as UMIACS-TR-98-16) University of Maryland Institute for Advanced Computer Studies, Department of Computer Science, University of Maryland,
Last Generated Fri Aug 11 04:01:01 EDT 2000