Conditioning Probabilistic Relational Data with Referential Constraints
No Thumbnail Available
Date
2014-03-12T08:46:48Z
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A probabilistic relational database is a compact form of a set of deterministic relational databases (namely, possible worlds), each
of which has a probability. In our framework, the existence of tuples is determined by associated Boolean formulae based on elementary events.
An estimation, within such a setting, of the probabilities of possible worlds uses a prior probability distribution speci ed over the elementary events. Direct observations and general knowledge, in the form of constraints, help re ning these probabilities, possibly ruling out some
possible worlds. More precisely, new constraints can translate the observation of the existence or non-existence of a tuple, the knowledge of a
well-de ned rule, such as primary key constraint, foreign key constraint, referential constraint, etc. Informally, the process of enforcing knowledge on a probabilistic database, which consists of computing a new subset of valid possible worlds together with their new (conditional) probabilities, is called conditioning. In this paper, we are interested in nding a new probabilistic relational database after conditioning with referential constraints
involved. In the most general case, conditioning is intractable. As a result, we restricted our study to probabilistic relational databases in which formulae of tuples are independent events in order to achieve some tractability results. We devise and present polynomial algorithms for conditioning probabilistic relational databases with referential constraints.