View Full Document

Dissociation and Propagation for Efficient Query Evaluation over Probabilistic Databases



View the full content.
View Full Document
View Full Document

3 views

Unformatted text preview:

Dissociation and Propagation for Efficient Query Evaluation over Probabilistic Databases Wolfgang Gatterbauer Abhay K Jha Dan Suciu University of Washington Seattle WA gatter abhaykj suciu cs washington edu 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 dissociated 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 dissociated probability is the propagation score We define a propagation score for self join free conjunctive queries and prove that it is always an upper 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 efficient way to rank probabilistic query results especially for those queries which are highly intractable for exact probabilistic inference 1 Introduction Evaluating queries over probabilistic databases PDBs is hard in general Despite important recent advances 15 20 today s approaches to query evaluation are not practical Existing techniques either split the queries into safe and unsafe and compute efficiently only the former 8 19 or work very well on certain combinations of queries and data instances but can not offer performance guarantees in general 15 18 or use general purpose approximation



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Dissociation and Propagation for Efficient Query Evaluation over Probabilistic Databases and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Dissociation and Propagation for Efficient Query Evaluation over Probabilistic Databases and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?