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 3 Subrahmanian, V. S. 2 Parisi, Francesco 2 Sliva, Amy 1 Benouaret, Karim 1 Benslimane, Djamal 1 Santos Costa, Vítor 1 De Raedt, Luc 1 Dekhtyar, Alex 1 Demoen, Bart 1 Doder, Dragan 1 Flesca, Sergio 1 Furfaro, Filippo 1 Goldsmith, Judy 1 Grant, John R. 1 Greco, Sergio 1 Gullo, Francesco 1 Kimmig, Angelika 1 Kraus, Sarit 1 Magnani, Matteo 1 Manisterski, Efrat 1 Martinez, Maria Vanina 1 Montesi, Danilo 1 Ognjanović, Zoran 1 Omri, Asma 1 Omri, Mohamed-Nazih 1 Peleg, David 1 Ponti, Giovanni 1 Qin, Biao 1 Rocha, Ricardo 1 Simari, Gerardo I. 1 Tagarelli, Andrea 1 Wang, Shan 1 Zhang, Yingqian 1 Zhao, Wenzhong all top 5 Cited in 8 Serials 2 Information Sciences 2 International Journal of Approximate Reasoning 1 Acta Informatica 1 Artificial Intelligence 1 Journal of Computer and System Sciences 1 Journal of Logic and Computation 1 1 Annals of Mathematics and Artificial Intelligence 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) Citations by Year