SPROUT: Lazy vs. Eager Query Plans for Tuple-Independent Probabilistic Databases

TLDR

Scalable computation of tuple confidences remains a key challenge in probabilistic databases. This work introduces an efficient secondary‑storage operator for exact query evaluation on tuple‑independent probabilistic databases. Implemented in the SPROUT PostgreSQL extension, the operator behaves as a sequence of aggregations, uses static query structure and functional dependencies to group aggregations and decide scan counts, and can be pushed or pulled past joins within relational plans. On the TPC‑H benchmark, the operator efficiently evaluates most aggregation‑removed queries and achieves substantial efficiency gains over existing methods.

Abstract

A paramount challenge in probabilistic databases is the scalable computation of confidences of tuples in query results. This paper introduces an efficient secondary-storage operator for exact computation of queries on tuple-independent probabilistic databases. We consider the conjunctive queries without self-joins that are known to be tractable on any tuple-independent database, and queries that are not tractable in general but become tractable on probabilistic databases restricted by functional dependencies. Our operator is semantically equivalent to a sequence of aggregations and can be naturally integrated into existing relational query plans. As a proof of concept, we developed an extension of the PostgreSQL 8.3.3 query engine called SPROUT. We study optimizations that push or pull our operator or parts thereof past joins. The operator employs static information, such as the query structure and functional dependencies, to decide which constituent aggregations can be evaluated together in one scan and how many scans are needed for the overall confidence computation task. A case study on the TPC-H benchmark reveals that most TPC-H queries obtained by removing aggregations can be evaluated efficiently using our operator. Experimental evaluation on probabilistic TPC-H data shows substantial efficiency improvements when compared to the state of the art.