In view of the paradigm shift that makes science ever more data-driven, we consider deterministic scientific hypotheses as uncertain data. This vision comprises a probabilistic database (p-DB) design methodology for the systematic construction and management of U-relational hypothesis DBs, viz., @math -DBs. It introduces hypothesis management as a promising new class of applications for p-DBs. We illustrate the potential of @math -DB as a tool for deep predictive analytics.
@cite_1: Past research on probabilistic databases has studied the problem of answering queries on a static database. Application scenarios of probabilistic databases however often involve the conditioning of a database using additional information in the form of new evidence. The conditioning problem is thus to transform a probabilistic database of priors into a posterior probabilistic database which is materialized for subsequent query processing or further refinement. It turns out that the conditioning problem is closely related to the problem of computing exact tuple confidence values. It is known that exact confidence computation is an NP-hard problem. This has led researchers to consider approximation techniques for confidence computation. However, neither conditioning nor exact confidence computation can be solved using such techniques. In this paper we present efficient techniques for both problems. We study several problem decomposition methods and heuristics that are based on the most successful search techniques from constraint satisfaction, such as the Davis-Putnam algorithm. We complement this with a thorough experimental evaluation of the algorithms proposed. Our experiments show that our exact algorithms scale well to realistic database sizes and can in some scenarios compete with the most efficient previous approximation algorithms.
Also related to the @math -DB vision is the topic of conditioning a p-DB. It has been firstly addressed by Koch and Olteanu motivated by data cleaning applications @cite_1 . They have introduced the assert operation to implement, as in AI, a kind of knowledge compilation, viz., world elimination in face of constraints (e.g., FDs). For hypothesis management, nonetheless, we need to apply by asserting observed data (not constraints). In @math , we present an example that settles the kind of conditioning problem that is relevant to @math -DB . In order to provide a concrete feel of our vision, in the next sections we present preliminary results on our methodology for constructing an @math -DB on top of MayBMS .