View Full Document

# Query Evaluation on Probabilistic Databases

View Full Document
View Full Document

18 views

Unformatted text preview:

Query Evaluation on Probabilistic Databases Christopher Re Nilesh Dalvi and Dan Suciu University of Washington 1 The Probabilistic Data In this paper we consider the query evaluation problem how can we evaluate SQL queries on probabilistic databases Our discussion is restricted to single block SQL queries using standard syntax with a modified semantics each tuple in the answer is associated with a probability representing our confidence in that tuple belonging to the answer We present here a short summary of the research done at the University of Washington into this problem Consider the probabilistic database in Fig 1 Productp contains three products their names and their prices are known but we are unsure about their color and shape Gizmo may be red and oval or it may be blue and square with probabilities p1 0 25 and p2 0 75 respectively Camera has three possible combinations of color and shape and IPod has two Thus the table defines for each product a probability distribution on its colors and shapes Since each color shape combination excludes the others we must have p1 p2 1 p3 p4 p5 1 and p6 p7 1 which indeed holds for our table When the sum is strictly less than one then that product may not occur in the table at all for example Camera may be missing from the table with probability 1 p3 p4 p5 Each probabilistic table is stored in a standard relational database for example Productp becomes the table in Fig 2 a For any two tuples in Productp if they have the same values of the key attributes prod and price then they are exclusive i e disjoint probabilistic events otherwise they are independent events The meaning of a probabilistic database is a probability distribution on possible worlds Productp has 16 possible worlds since there are two choices for the color and shape for Gizmo four for Camera including removing Camera altogether and two for IPod Fig 2 b illustrate two possible worlds and their probabilities Productp prod price Gizmo 20 Camera 80 IPod 300 color

Unlocking...