Efficient Evaluation of HAVING Queries on a Probabilistic有疑问的概率的有效性评价.pptxVIP

Christopher Re and Dan Suciu University of Washington Efficient Evaluation of HAVING Queries on a Probabilistic Database High level Overview Evaluation of conjunctive Boolean queries with aggregate tests on probabilistic DBs: HAVING in SQL, e.g. is the SUM(profit) 100k? Looking for optimal algorithms (dichotomies): For all queries q with aggregate A want P time algorithm, call this A-Safe [DS04,DS07] Some instance s.t. q is hard (#P). Technique: In safe plans, use multiplication In A-safe plans, use convolution (on monoids) 2 Motivation Item Forecaster Amount P Widget Alice $-99k 0.99 Bob $100M 0.01 Whatsit Alice $1M 1 SELECT SUM(Amount) FROM Profit WHERE item=‘Widget’ SELECT item FROM Profit WHERE item =‘Widget’ GROUP BY item HAVING SUM(Amount) 0 Expectation Style [Prior Art] HAVING style Ans: -99k *.99 +100M*0.01 ~900K Ans: 0.01 Profit 3 Overview Preliminaries Formal Problem Description Query plans and Datalog Monoid Random Variables and Convolutions Max,Min,Count and hints for others Conclusions 4 SELECT ITEM FROM PROFIT WHERE ITEM=‘Widget’ GROUP BY ITEM HAVING SUM(PROFIT) 0 HAVING Query semantics NB: Assume SQL-like semantics Conjunctive rule: No repeated symbols Aggregates Comparision: k, is a constant 5 Probabilistic Semantics NB: In paper, allow disjoint tuples Possible worlds, model Query Semantics In talk, restrict to tuple independence 6 Complexity and formal problem Data complexity: Fix Query. Instance grows. In practice, query is small. Consider k, i.e. 1000, as part of the input Skeleton, 7 Overview Preliminaries Formal Problem Description Query plans and Datalog Monoid Random Variables and Convolutions Max,Min,Count and hints for others Conclusions 8 Monoids and Semirings NB: n=1 is logical OR A monoid is a triple where M is a set and + is associative with identity 0. e.g. Commutative Semiring is Both are commutative monoids * distributes over + e.g. a Boolean algebra 9 Fix a Semiring S.