Paper Info
Title
Dissociation and Propagation for Efficient Query Evaluation over Probabilistic Databases.
Abstract
Queries over probabilistic databases are either safe, in which case they can be evaluated entirely in a relational database engine, or unsafe, in which case they need to be evaluated with a general-purpose inference engine at a high cost. We propose a new approach by which every query is evaluated inside the database engine, by using a new method called dissociation. A dissociated query is obtained by adding extraneous variables to some atoms until the query becomes safe. We show that the probability of the original query and that of the dissoci- ated query correspond to two well-known scoring functions on graphs, namely graph reliability (which is #P-hard), and the propagation score (which is related to PageRank and is in PTIME): When restricted to graphs, standard query probability is graph reliability, while the dissoci- ated probability is the propagation score. We dene a propagation score for self-join-free conjunctive queries and prove that it is always an up- per bound for query reliability, and that both scores coincide for all safe queries. Given the widespread and successful use of graph propagation methods in practice, we argue for the dissociation method as a highly ef- cient way to rank probabilistic query results, especially for those queries which are highly intractable for exact probabilistic inference.
Year
Venue
Keywords
2010
MUD
relational database,score function,conjunctive queries,probabilistic database
DocType
Volume
Citations 
Conference
abs/1310.6257
11
PageRank 
References 
Authors
0.61
19
2
Name
Order
Citations
PageRank
Wolfgang Gatterbauer149834.18
Dan Suciu296251349.54