Faster Query Answering in Probabilistic Databases using Read-Once Functions

Details Faster Query Answering in Probabilistic Databases using Read-Once Functions Faster Query Answering in Probabilistic Databases using Read-Once Functions

2010-12-01

arxiv.org/abs/1012.0335v2

Computer Science

Databases

Accepted in ICDT 2011

Scientific paper

A boolean expression is in read-once form if each of its variables appears exactly once. When the variables denote independent events in a probability space, the probability of the event denoted by the whole expression in read-once form can be computed in polynomial time (whereas the general problem for arbitrary expressions is #P-complete). Known approaches to checking read-once property seem to require putting these expressions in disjunctive normal form. In this paper, we tell a better story for a large subclass of boolean event expressions: those that are generated by conjunctive queries without self-joins and on tuple-independent probabilistic databases. We first show that given a tuple-independent representation and the provenance graph of an SPJ query plan without self-joins, we can, without using the DNF of a result event expression, efficiently compute its co-occurrence graph. From this, the read-once form can already, if it exists, be computed efficiently using existing techniques. Our second and key contribution is a complete, efficient, and simple to implement algorithm for computing the read-once forms (whenever they exist) directly, using a new concept, that of co-table graph, which can be significantly smaller than the co-occurrence graph.

Affiliated with

Also associated with

No associations

Rating

Faster Query Answering in Probabilistic Databases using Read-Once Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Faster Query Answering in Probabilistic Databases using Read-Once Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster Query Answering in Probabilistic Databases using Read-Once Functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-602537