1、A Formal Approach to Finding Explanations for Database Queries,Sudeepa Roy Dan Suciu University of Washington, Seattle,1,We need to understand “Big Data”,ref. Big data whitepaper, Jagadish et al., 2011-12,D1,D2,D3,Data Analysis System,1. Acquire Data,2. Prepare Data,Clean,Extract Feature,Integrate,5
2、. Plot Graphs,6. Ask Questions!,4. Run Queries,Do you have an explanation?,2,Why is there a peak for #sigmod papers from industry during 2000-06,while #academia papers kept increasing?,Why is #SIGMOD papers #PODS papers in UK?,Sample Questions,Dataset: Pre-processed DBLP + Affiliation data Disclaime
3、r: Not all authors have affiliation info,Explanations by our approach at the end,3,“What was the cause of the observation?” Not simple association or correlation e.g. People having headache drink coffeeDoes coffee cause headache?Does headache lead to drinking coffee?,Ideal goal: Why Causality,4,Has
4、been studied for many years (Hume1748) Extensive study in AI over the last decade by Judea Pearl using the notion of intervention:X is a cause of Y, if removal of X also removes Y keeping other conditions unchangedNeeds controlled experiments Not always possible with a database ,But, causality is ha
5、rd,5,Realistic Database-y goal: Why Explanation,Causality,Explanation,Controlled,Experiment,Input database and observed query outputs,Causal Paths,PK-FK constraints and their,generalization,Intervention,Remove input,tuples,query output should,change,Top Causes,Top explanations will change the output
6、,in the expected direction to a greater extent,6,Previous/Related Work,Causality in databases Meliou et al.10, Meliou et al.11Explanations in databases Explaining outliers in aggregate queries: Wu-Madden13 Specific applications (Map-Reduce, Access log, User Rating,):e.g. Khoussainova et al.12, Fabbr
7、i et al.12, Das et al.11Other related topics Provenance, deletion propagation: e.g. Green et al.07, Buneman et al.01 Missing answer/Why-Not: e.g. Herschel et al.09, Huang et al.10, Chapman-Jagadish09 Finding causal structure/data mining: e.g. Silverstein et al.00 OLAP: e.g. Sarawagi-Sathe01,Informal
8、ly use interventionExplanation = predicateMostly single table, no join,Pearls notion of causality and interventionCausal structure from input to output by lineageCause = Individual input tuples, not predicatesNo inherent causal structure in input data,Upcoming VLDB 2014 Tutorial “Causality and Expla
9、nations in Databases” Alexandra Meliou, Sudeepa Roy, Dan Suciu,This work: Formal framework of explanations (= predicates)and theoretical analysis causal structure within input data independent of queries or user questions allow multiple tables and joinsOptimizations and Evaluation find top explanati
10、ons using data cube,7,Outline,FrameworkCausal Paths and InterventionComputing InterventionOptimization: Ranking Explanations by Data CubeEvaluationFuture Work,8,Input and Output,Run Group-By Queries and Plot,Toy DBLP database,Output Plot,User question Numerical expression EDirection: high/low,E = (q
11、1/q3) / (q2/q4) Direction = high,Why is q1/q3 q2/q4,e.g. q1select count(distinct x.pubid) from Author x, Authored y, Publication z where x.id = y.id and y.pubid = z.pubidand z.venue = SIGMODand 2000 = z.yearand z.year = 2004and x.domain = com,These values will vary for q2, q3, q4,Input,Explanation(s
12、) : Predicate on attributes e.g. name = JG name = JG inst = C.edu name = JG year = 2007 Note: attr from multiple tables,Output,E should change when database is “intervened “with ,9,Causal Paths by Foreign Key Constraints,Causal path X Y: removing X removes Y Analogy in DB: Foreign key constraints an
13、d cascade delete semantics,Author (id, name, inst, dom),Authored (id, pubid),Publication (pubid, year, venue),Standard F.K. (cascade delete),Back and Forth F.K. (cascade delete + reverse cascade delete),Forward,Reverse,Intuition: An author can exist if one of her papers is deletedA paper cannot exis
14、t if any of its co-authors is deleted,10,Causal Paths and Intervention,Candidate explanation : name = RR,Reverse,Forward,Intervention : Tuples T0 that satisfy + Tuples reachable from T0,Given , computation of requires a recursive query,Multiple tables require universal table,11,Objective: top-k expl
15、anations,Consider user question: Why is E = (q1/q2)/(q3/q4) low, Find top-k explanations w.r.t a score = E(D - )The obvious approach:,Two sources of complexity,1. For all possible predicates Compute the intervention for Delete tuples in from D Evaluate q1, q2, q3, q4 on D Compute E(D - )2. Find top
16、explanations with highest scores E(D - ) (top-k),Recursion,12,Computing by a Recursive Program,Properties: Program has a unique least fixpoint which can be obtained in poly-time (n = |D| steps)Program is not monotone in database, i.e., if D D, not necessarily (D) (D) Therefore not expressible in dat
17、alog But expressible in datalog + negation,Delete from universal table tuples |= ,Cascade delete,Reverse Cascade delete,13, is fixed,Convergence Depends on Schema,Convergence in 4 steps,S,R,T,Convergence requires n - 1 steps,Can be generalized,14,Finding Top-k Explanations with Data Cube,For all pos
18、sible predicates Compute the intervention for ,#Possible predicates is hugeRunning FOR LOOP is expensiveRunning RECURSION is expensiveOptimization: OLAP data cube,why (q1*q4)/(q2*q3) high?,Suppose we want predicates on attributes name, inst, venue as explanations,group by name, inst, venue with cube
19、,name, inst, venue,e.g. Cube for q1,15,e.g. Query for q1,q1: com, 2000-04,q2: com, 2007-11,q3: edu, 2000-04,q4: edu, 2007-11,Sketch of Algorithm with Data Cube,1. (Outer)-join the cubes + compute score,Score,All computation done by DBMSBut,Cube Algorithm matches theory for some inputs (e.g. single t
20、able, DBLP examples)For other inputs it is a heuristic (recursion is necessary),2. Run Top-K,16,Experiment 1: Data Cube Optimization vs. Iterative Algo,Natality Dataset 2010: (from National Center for Health Statistics (NCHS). Single table with 233 attributes, 4M entries, 2.89GB size.,More experimen
21、ts in the paper,17,Data size vs. time,Experiment 2: Scalability of the Data Cube Optimization,No. of attributes,E1 E2,E1 E2,Why (q1/q2) low,Why (q1/q2)/(q3/q4) low,18,Data size vs. time,(Max) No. of attributes in explanation predicates vs. time,Qualitative Evaluation (DBLP),Q. Why is there a peak fo
22、r #sigmod papers from industry during 2000-06, while #academia papers kept increasing?,Intuition: 1. If we remove these industrial labs and their senior researchers, the peak during 2000-04 is more flattened 2. If we remove these universities with relatively new but highly prolific db groups, the cu
23、rve for academia is less increasing,19,Hard due to lack of gold standard,Qualitative Evaluation (DBLP),Intuition: If we remove these leading theoretical DB researchers or their universities/cities, the bar for UK will look different.e.g. for UK,Originally: PODS = 62%, SIGMOD = 38% Removing all publi
24、cations by Libkin: PODS = 46%, SIGMOD = 54%,Q. Why is #SIGMOD papers #PODS papers in UK?,20,P = 32, S = 3,P = 24, S = 1,P = 9, S = 0,P = 15, S = 2,source: DBLP,Not top expl.: Wenfei Fan Peter Buneman ,P = 15, S = 12,P = 6, S = 12,Current/Future Work,Optimize for arbitrary SPJUA queries and schemas Go beyond data cube Model increasing/decreasing trend by linear regression (E = slope) Ranking algorithm: simple, meaningful, diverse explanations Prototype with a GUI,21,Thank you,Questions?,22,
