## ProbView

swMATH ID: | 9438 |

Software Authors: | Lakshmanan, V.S., Leone, N., Ross, R. and Subrahmanian, V.S. |

Description: | ProbView: a flexible probabilistic database system. Probability theory is mathematically the best understood paradigm for modeling and manipulating uncertain information. Probabilities of complex events can be computed from those of basic events on which they depend, using any of a number of strategies. Which strategy is appropriate depends very much on the known interdependencies among the events involved. Previous work on probabilistic databases has assumed a fixed and restrictivecombination strategy (e.g., assuming all events are pairwise independent). In this article, we characterize, using postulates, whole classes of strategies for conjunction, disjunction, and negation, meaningful from the viewpoint of probability theory. (1) We propose a probabilistic relational data model and a genericprobabilistic relational algebra that neatly captures various strategiessatisfying the postulates, within a single unified framework. (2) We show that as long as the chosen strategies can be computed in polynomial time, queries in the positive fragment of the probabilistic relational algebra have essentially the same data complexity as classical relational algebra. (3) We establish various containments and equivalences between algebraic expressions, similar in spirit to those in classical algebra. (4) We develop algorithms for maintaining materialized probabilistic views. (5) Based on these ideas, we have developed a prototype probabilistic database system called ProbView on top of Dbase V.0. We validate our complexity results with experiments and show that rewriting certain types of queries to other equivalent forms often yields substantial savings. |

Homepage: | http://dl.acm.org/citation.cfm?id=261131 |

Related Software: | Trio; ProTDB; MYSTIQ; PSQL; clusfind; flanagan; LingPipe; MayBMS; Sat4j; QSopt-Exact; MS SQL Server; DARX; XPath; CherryPy; YAP-Prolog; ProbLog; TAX; WordNet |

Cited in: | 11 Documents |

all
top 5

### Cited by 34 Authors

all
top 5

### Cited in 8 Serials

### Cited in 4 Fields

10 | Computer science (68-XX) |

1 | Mathematical logic and foundations (03-XX) |

1 | Statistics (62-XX) |

1 | Information and communication theory, circuits (94-XX) |