Abstracts Category : Other

Validation of SQL queries over streaming warehouses

by Ritika Jain

There is often a need to recover the missing query that produced a particular outputfrom a data stream. As an example, since a data stream is constantly evolving,the analyst may be curious about using the query from the past to evaluate it on thecurrent state of the data stream, for further analysis. Previous research has studiedthe problem of reverse engineering a query that would produce a given result at aparticular database state.We study the following problem. Given a streaming database D=<D0,D1,D2..>,a result Rout , and a set of candidate queries Q, efficiently find all queries Qi Qsuch that for some state Dji of the stream, Qi(Dji) = Rout , and report the pair(Q,witQ) where witQ is the witness of (in)validity. A witness for a valid queryQval is a state Di s.t. Qval(Di) = Rout. For an invalid query Qinval , a witness is a pairof consecutive states (Di, Di+1) such that Rout Qinval (Di) Qinval (Di+1) Rout.We allow any PTIME computable monotone query to be included in Q. Whiletechniques developed in previous research can be used to generate the candidatequery set Q, we focus on developing a scalable strategy for quickly determiningthe witness. We establish theoretical worst-case performance guarantees for ourproposed approach and show that it is no more than a factor of O(log |DRDS|) of theoptimal Lucky guess strategy, where Q(DRDS) = Rout. We empirically evaluateour technique and compare with natural baselines inspired from previous research.We show that the baselines either fail to scale or incur an inordinate amount ofoverhead by failing to take advantage of natural properties of a data stream. Bycontrast, our strategy scales effortlessly for very large data streams. Moreover,it never performs more than a small constant times the optimal amount of work,regardless of the state of the data stream that may have led to Rout.