Efficient Query Evaluation on Probabilistic Databases概率数据库的高效查询评估.pptVIP

Efficient Query Evaluation on Probabilistic Databases Nilesh Dalvi Dan Suciu Outline Motivation Query Evaluation: Intensional Extensional Query Optimization Complexity Unsafe Plans Extensions Conclusions Databases Are Deterministic Databases we see today are deterministic A tuple is either in the query answer or not They don’t deal with uncertainties Future of Data Management Uncertainties in Data Biological Data Sensor Data (Geographical Data) Data extracted from various AI, data mining techniques (information extraction) Uncertainties are represented as probabilities Extend data management tools to handle probabilistic data Example Review Text I have not used IPOD but Apple products are good Representing Uncertainty Tuple-existence uncertainty All attributes in a tuple are known precisely; existence of the tuple is uncertain E.g. in previous slide. More later Attribute-value uncertainty Tuples (identified by keys) exist for certain; attributes (one or more) value are however uncertain Tomorrow, it may rain (probability is 0.6) Our Goal For Today Understand how queries can be evaluated efficiently on Probabilistic Databases For simplicity, we will deal with tuple-level uncertainties only We also assume independence among tuples. i.e. P(t1, t2) = P(t1) * P(t2) Possible Worlds: Example 1 Possible Worlds: Example 2 Query Evaluation So, lets consider a query: Q(D) :- S(A,B), T(C,D), B = C S join T on B = C, project on D Intuitively: Execute the query on each possible world The final result is a probabilistic relation that represents end result Query Evaluation: Example Query Evaluation Semantically correct If T has ‘n’ tuples, there can be as many as 2^n possible worlds. Exponential complexity, thus impractical Intensional Query Evaluation Define the complex event ep(t) for each tuple t For each intermediate tuple, associate an explicit (complex) event expression Compute the actual probabilities at the end For this talk, we will look only select, join project querie