Data Management

Faster Query Answering in Probabilistic Databases Using Read-Once Functions

Date Added: Mar 2011
Format: PDF

A Boolean expression is in read-once form if each of its variables appears exactly once. When the variables denote independent events in a probability space, the probability of the event denoted by the whole expression in read-once form can be computed in polynomial time (whereas the general problem for arbitrary expressions is #P-complete). Known approaches to checking read-once property seem to require putting these expressions in disjunctive normal form. In this paper, the authors tell a better story for a large subclass of Boolean event expressions: those that are generated by conjunctive queries without self-joins and on tuple-independent probabilistic databases.