Queries with difference on probabilistic databases


Conference Paper

We study the feasibility of the exact and approximate com-putation of the probability of relational queries with differ-ence on tuple-independent databases. We show that even the difference between two"safe" conjunctive queries with-out self-joins is"unsafe" for exact computation. We turn to approximation and design an FPRAS for a large class of re-lational queries with difference, limited by how difference is nested and by the nature of the subtracted subqueries. We give examples of inapproximable queries outside this class. © 2011 VLDB Endowment.

Duke Authors

Cited Authors

  • Khanna, S; Roy, S; Tannen, V

Published Date

  • August 1, 2011

Published In

Volume / Issue

  • 4 / 11

Start / End Page

  • 1051 - 1062

Electronic International Standard Serial Number (EISSN)

  • 2150-8097

Citation Source

  • Scopus