Combining intensional with extensional query evaluation in tuple independent probabilistic databases |
| |
Authors: | Biao Qin Shan Wang |
| |
Affiliation: | Key Laboratory of Data Engineering and Knowledge Engineering, Renmin University of China, MOE, Beijing 100872, PR China School of Information, Renmin University of China, Beijing 100872, PR China |
| |
Abstract: | In this paper, we prove that a query plan is safe in tuple independent probabilistic databases if and only if its every answer tuple is tree structured in probabilistic graphical models. We classify hierarchical queries into core and non-core hierarchical queries and show that the existing methods can only generate safe plans for core hierarchical queries. Inspired by the bucket elimination framework, we give the sufficient and necessary conditions for the answer relation of every candidate sub-query to be used as a base relation. Finally, the proposed algorithm generates safe plans for extensional query evaluation on non-boolean hierarchical queries and invokes the SPROUT algorithm 24] for intensional query evaluation on boolean queries. A case study on the TPC-H benchmark reveals that the safe plans of Q7 and Q8 can be evaluated efficiently. Furthermore, extensive experiments show that safe plans generated by the proposed algorithm scale well. |
| |
Keywords: | Probabilistic databases Probabilistic graphical model Hierarchy Safe plan Bucket elimination framework |
本文献已被 ScienceDirect 等数据库收录! |
|