Implementing Not-Exists Predicates over a Probabilistic Database

by
Ting-You Wang

Abstract:

Many SQL queries over data collected from RFID devices use the NOT-EXISTS predicate, but such queries are not currently supported by our probabilistic database system, MystiQ. In this talk I will describe an extension of MystiQ that supports SQL queries with the NOT-EXISTS predicates. This is a non-trivial extension, because NOT-EXISTS is non-monotone, while all previous queries supported by MystiQ were monotone, making the query probabilities more difficult to compute. The approach I will describe is to break up the query into multiple, monotone queries, and combine their probabilities by addition and subtraction to compute that of the original query. I will also describe how this technique was integrated with the rest of the MystiQ system, including top-k multisimulation and safe-plans optimizations.

Advised by Dan Suciu

CSE 403
Wednesday
May 23, 2007
4:30 - 5:20 pm