Optimal Query Processing Meets Information Theory in Database Optimization

optimal query processing meets information theory n.w
1 / 57
Embed
Share

Explore the intersection of optimal query processing and information theory in database management. Learn about computing queries on labeled hypergraphs, enumeration problems, decision problems, and principles for finding upper bounds. Discover how to convert information-theoretic proofs into algorithms for efficient query processing.

  • Query Processing
  • Information Theory
  • Database Optimization
  • Hypergraphs
  • Enumeration
rayaanacharya
havy_23 Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Optimal Query Processing Meets Information Theory Dan Suciu University of Washington Mahmoud Abo-Khamis Hung Ngo RelationalAI Inc. [PODS 2016] [PODS 2017]

  2. Basic Question What is the optimal runtime to compute a query Q on a database D? Q, D are labeled hypergraphs Problem 1: list all occurrences in Q in D Problem 2: check if there exists Q in D Data complexity: Q is fixed, runtime = f(D) 2

  3. Example Queries R Enumerate all labeled triangles: X Y R(X,Y) S(Y,Z) T(Z,X) S T Z Check if there exists a labeled 4-cycle R X Y x y z u R(x,y) S(y,z) T(z,u) K(u,x) S K U Z T 3

  4. Main Results Fix statistics for D (cardinalities, functional dependencies, max degrees) Fix the query Q Tight, but open if computable Problem 1: enumeration problem Computable, but not tight Thm D, (1) |Q(D)| Entropic-bound Polymatroid-bound (2) Q(D) computable in time (Polymatroid-bound) Problem 2: decision problem Optimal? Thm D, Q(D) is computable in time (2submodular-width)

  5. Main Principle Find information-theoretic proof of the upper bound, or the submodular width Convert proof to algorithm 5

  6. Outline Enumeration problem Decision problem Conclusions 6

  7. Maximum Output Size maxD satisfies stats (|Q(D)|) E.g. R(X,Y) S(Y,Z), |R|, |S| N No other info: S.Y is a key: S.Y has degree d:|Q(D)| d N |Q(D)| N2 |Q(D)| N E.g. R(X,Y) S(Y,Z) T(Z,X) No other info: |Q(D)| N3/2 7

  8. Maximum Output Size maxD satisfies stats (|Q(D)|) E.g. R(X,Y) S(Y,Z), |R|, |S| N No other info: S.Y is a key: S.Y has degree d:|Q(D)| d N |Q(D)| N2 |Q(D)| N E.g. R(X,Y) S(Y,Z) T(Z,X) No other info: |Q(D)| N3/2 8

  9. Maximum Output Size maxD satisfies stats (|Q(D)|) E.g. R(X,Y) S(Y,Z), |R|, |S| N No other info: S.Y is a key: S.Y has degree d:|Q(D)| d N |Q(D)| N2 |Q(D)| N E.g. R(X,Y) S(Y,Z) T(Z,X) No other info: |Q(D)| N3/2 9

  10. Maximum Output Size maxD satisfies stats (|Q(D)|) E.g. R(X,Y) S(Y,Z), |R|, |S| N No other info: S.Y is a key: S.Y has degree d:|Q(D)| d N |Q(D)| N2 |Q(D)| N E.g. R(X,Y) S(Y,Z) T(Z,X) No other info: |Q(D)| N3/2 10

  11. Maximum Output Size maxD satisfies stats (|Q(D)|) E.g. R(X,Y) S(Y,Z), |R|, |S| N No other info: S.Y is a key: S.Y has degree d: |Q(D)| d N |Q(D)| N2 |Q(D)| N E.g. R(X,Y) S(Y,Z) T(Z,X) No other info: |Q(D)| N3/2 11

  12. Maximum Output Size maxD satisfies stats (|Q(D)|) E.g. R(X,Y) S(Y,Z), |R|, |S| N No other info: S.Y is a key: S.Y has degree d: |Q(D)| d N |Q(D)| N2 |Q(D)| N E.g. R(X,Y) S(Y,Z) T(Z,X) No other info: |Q(D)| N3/2 12

  13. Maximum Output Size maxD satisfies stats (|Q(D)|) E.g. R(X,Y) S(Y,Z), |R|, |S| N No other info: S.Y is a key: S.Y has degree d: |Q(D)| d N |Q(D)| N2 |Q(D)| N E.g. R(X,Y) S(Y,Z) T(Z,X) No other info: |Q(D)| N3/2 13

  14. Maximum Output Size maxD satisfies stats (|Q(D)|) E.g. R(X,Y) S(Y,Z), |R|, |S| N No other info: S.Y is a key: S.Y has degree d: |Q(D)| d N |Q(D)| N2 |Q(D)| N E.g. R(X,Y) S(Y,Z) T(Z,X) No other info: |Q(D)| N3/2 14

  15. Background: Entropy, Polymatroid Fix a set X={X1, ,Xk} and a function H: 2X R+ Def H is called entropic if there exists random variables X s.t. H(U) = entropy of U, for U X Def H is a polymatroid if H( ) = 0 H(V) H(U) H(U) + H(V) H(U V) + H(U V) Shannon inequalities for U V Every entropic function is a polymatroid Converse fails for k 4[Zhang&Yeung 98]

  16. Enumeration Problem Fix a set of statistics for D (cardinalities, FDs, degrees) Fix a query Q with variables X={X1, ,Xk} Asymptotically tight, but open if computable Theorem D that satisfies the statistics log |Q(D)| max H entropic satisfying stats H(X) max H polymatroid satisfying stats H(X) Computable in EXPTIME, but not tight Thm D, Q(D) computable in time (Polymatroid-bound) 16

  17. X Y Proof of Upper Bound Z Q(X,Y,Z) = R(X,Y) S(Y,Z) T(Z,X) Database D entropic function H 17

  18. X Y Proof of Upper Bound Z Q(X,Y,Z) = R(X,Y) S(Y,Z) T(Z,X) Database D entropic function H Database D R(X,Y) S(Y,Z) T(Z,X) X a a b d Y 3 2 2 3 Y 3 2 3 2 Z m q q m Z m q q m X a a b d 18

  19. X Y Proof of Upper Bound Z Q(X,Y,Z) = R(X,Y) S(Y,Z) T(Z,X) Database D entropic function H Output Q(D) Database D R(X,Y) S(Y,Z) T(Z,X) X a a b d a Y 3 2 2 3 3 Z m q q m q X a a b d Y 3 2 2 3 Y 3 2 3 2 Z m q q m Z m q q m X a a b d 19

  20. X Y Proof of Upper Bound Z Q(X,Y,Z) = R(X,Y) S(Y,Z) T(Z,X) Database D entropic function H Output Q(D) Database D R(X,Y) S(Y,Z) T(Z,X) X a a b d a Y 3 2 2 3 3 Z m q q m q 1/5 1/5 1/5 1/5 1/5 X a a b d Y 3 2 2 3 Y 3 2 3 2 Z m q q m Z m q q m X a a b d H(XYZ) = log |Q(D)| 20

  21. X Y Proof of Upper Bound Z Q(X,Y,Z) = R(X,Y) S(Y,Z) T(Z,X) Database D entropic function H Output Q(D) Database D R(X,Y) S(Y,Z) T(Z,X) X a a b d a Y 3 2 2 3 3 Z m q q m q 1/5 1/5 1/5 1/5 1/5 X a a b d Y 3 2 2 3 Y 3 2 3 2 Z m q q m Z m q q m X a a b d 2/5 1/5 1/5 1/5 2/5 2/5 1/5 0 1/5 2/5 1/5 1/5 H(XYZ) = log |Q(D)| 21

  22. X Y Proof of Upper Bound Z Q(X,Y,Z) = R(X,Y) S(Y,Z) T(Z,X) Database D entropic function H Output Q(D) Database D R(X,Y) S(Y,Z) T(Z,X) X a a b d a Y 3 2 2 3 3 Z m q q m q 1/5 1/5 1/5 1/5 1/5 X a a b d Y 3 2 2 3 Y 3 2 3 2 Z m q q m Z m q q m X a a b d 2/5 1/5 1/5 1/5 2/5 2/5 1/5 0 1/5 2/5 1/5 1/5 H(XYZ) = log |Q(D)| H(XY) log NR H(YZ) log NS H(Z|Y) log degS(z|y) H(XZ) log NT Cardinalitites, functional dependences, max degrees

  23. X Y Proof of Upper Bound Z Q(X,Y,Z) = R(X,Y) S(Y,Z) T(Z,X) |R|,|S|,|T| N |Q(D)| N3/2 23

  24. X Y Proof of Upper Bound Z Q(X,Y,Z) = R(X,Y) S(Y,Z) T(Z,X) |R|,|S|,|T| N |Q(D)| N3/2 3 log N h(XY) + h(YZ) + h(XZ) h(XYZ) + h(Y) + h(XZ) h(XYZ) + h(XYZ) + h( ) = 2 h(XYZ) = 2 log |Output| 24

  25. X Y Proof of Upper Bound Z Q(X,Y,Z) = R(X,Y) S(Y,Z) T(Z,X) |R|,|S|,|T| N |Q(D)| N3/2 submodularity 3 log N h(XY) + h(YZ) + h(XZ) h(XYZ) + h(Y) + h(XZ) h(XYZ) + h(XYZ) + h( ) = 2 h(XYZ) = 2 log |Output| 25

  26. X Y Proof of Upper Bound Z Q(X,Y,Z) = R(X,Y) S(Y,Z) T(Z,X) |R|,|S|,|T| N |Q(D)| N3/2 submodularity 3 log N h(XY) + h(YZ) + h(XZ) h(XYZ) + h(Y) + h(XZ) h(XYZ) + h(XYZ) + h( ) = 2 h(XYZ) = 2 log |Output| 26

  27. X Y Proof of Upper Bound Z Q(X,Y,Z) = R(X,Y) S(Y,Z) T(Z,X) |R|,|S|,|T| N |Q(D)| N3/2 submodularity 3 log N h(XY) + h(YZ) + h(XZ) submodularity h(XYZ) + h(Y) + h(XZ) h(XYZ) + h(XYZ) + h( ) = 2 h(XYZ) = 2 log |Output| 27

  28. X Y Proof of Upper Bound Z Q(X,Y,Z) = R(X,Y) S(Y,Z) T(Z,X) |R|,|S|,|T| N |Q(D)| N3/2 submodularity 3 log N h(XY) + h(YZ) + h(XZ) submodularity h(XYZ) + h(Y) + h(XZ) h(XYZ) + h(XYZ) + h( ) = 2 h(XYZ) = 2 log |Output| 28

  29. X Y Proof of Upper Bound Z Q(X,Y,Z) = R(X,Y) S(Y,Z) T(Z,X) |R|,|S|,|T| N |Q(D)| N3/2 submodularity 3 log N h(XY) + h(YZ) + h(XZ) submodularity h(XYZ) + h(Y) + h(XZ) h(XYZ) + h(XYZ) + h( ) = 2 h(XYZ) = 2 log |Q(D)| 29

  30. X Y Proof of Upper Bound Z Q(X,Y,Z) = R(X,Y) S(Y,Z) T(Z,X) |R|,|S|,|T| N |Q(D)| N3/2 submodularity 3 log N h(XY) + h(YZ) + h(XZ) submodularity h(XYZ) + h(Y) + h(XZ) h(XYZ) + h(XYZ) + h( ) = 2 h(XYZ) Shearer s inequality h(XY) + h(YZ) + h(XZ) 2 h(XYZ) = 2 log |Q(D)| 30

  31. X Y Proof to Algorithm Z Q(X,Y,Z) = R(X,Y) S(Y,Z) T(Z,X) h(XY) + h(YZ) + h(XZ) 2 h(XYZ) h(XY)+h(YZ)+h(XZ) + h(Y) + h(XZ) h(XYZ) Proof h(XYZ) 31

  32. X Y Proof to Algorithm Z Q(X,Y,Z) = R(X,Y) S(Y,Z) T(Z,X) h(XY) + h(YZ) + h(XZ) 2 h(XYZ) Algorithm R(X,Y) S(Y,Z) T(Z,X) h(XY)+h(YZ)+h(XZ) + h(Y) + h(XZ) h(XYZ) Proof h(XYZ) 32

  33. X Y Proof to Algorithm Z Q(X,Y,Z) = R(X,Y) S(Y,Z) T(Z,X) h(XY) + h(YZ) + h(XZ) 2 h(XYZ) Algorithm R(X,Y) S(Y,Z) T(Z,X) h(XY)+h(YZ)+h(XZ) N3/2 + h(Y) + h(XZ) h(XYZ) Rlight(X,Y) S(Y,Z) Proof h(XYZ) Rlight or Rheavy: degree(Y) or > N1/2 33

  34. X Y Proof to Algorithm Z Q(X,Y,Z) = R(X,Y) S(Y,Z) T(Z,X) h(XY) + h(YZ) + h(XZ) 2 h(XYZ) Algorithm R(X,Y) S(Y,Z) T(Z,X) h(XY)+h(YZ)+h(XZ) N3/2 + h(Y) + h(XZ) h(XYZ) N3/2 Rlight(X,Y) S(Y,Z) Proof h(XYZ) Rheavy(Y) T(X,Z) Rlight or Rheavy: degree(Y) or > N1/2 34

  35. X Y Proof to Algorithm Z Q(X,Y,Z) = R(X,Y) S(Y,Z) T(Z,X) Runtime (N3/2) h(XY) + h(YZ) + h(XZ) 2 h(XYZ) Algorithm R(X,Y) S(Y,Z) T(Z,X) h(XY)+h(YZ)+h(XZ) N3/2 + h(Y) + h(XZ) h(XYZ) N3/2 Rlight(X,Y) S(Y,Z) Proof h(XYZ) Rheavy(Y) T(X,Z) Rlight or Rheavy: degree(Y) or > N1/2 35

  36. Enumeration Problem: Discussion Cardinalities: [Atserias,Grohe,Marx 08, Ngo,Re,Rudra 13] Entropic bound = polymatroid bound Algorithm for Q(D) has single log factor Cardinalities + FDs + max degrees: Entropic bound polymatroid bound Algorithm for Q(D) has polylog factor 36

  37. Outline Enumeration problem Decision problem Conclusions 37

  38. Decision Problem Fix Q, fix statistics on D Problem: does Q occur in D? submodular width Theorem One can check if Q is in D in time (2subw(Q)) Optimal? (fine grained lower bound is open!) 38

  39. Background: Tree Decomposition Informally: TD = a tree where each node t represents an enumeration problem Fractional hypetree width [Grohe,Marx 14] mintree maxnode t maxD Submodular width [Marx 2013] maxD mintree maxnode t 39

  40. X Y Q() = x y z u R(x,y) S(y,z) T(z,u) K(u,x) U Z |R|,|S|,|T|,|K| N O(N3/2) algorithm [Alon,Yuster,Zwick 97] mintree maxnode t maxD 40

  41. X Y Q() = x y z u R(x,y) S(y,z) T(z,u) K(u,x) U Z |R|,|S|,|T|,|K| N O(N3/2) algorithm [Alon,Yuster,Zwick 97] mintree maxnode t maxD Tree decompositions R(x,y),S(y,z) S(y,z),T(z,u) T(z,u),K(u,x) K(u,x),R(x,y) 41

  42. X Y Q() = x y z u R(x,y) S(y,z) T(z,u) K(u,x) U Z |R|,|S|,|T|,|K| N O(N3/2) algorithm [Alon,Yuster,Zwick 97] mintree maxnode t maxD Tree decompositions R(x,y),S(y,z) S(y,z),T(z,u) T(z,u),K(u,x) K(u,x),R(x,y) Runtime (N2) (suboptimal) 42

  43. X Y Q() = x y z u R(x,y) S(y,z) T(z,u) K(u,x) U Z |R|,|S|,|T|,|K| N O(N3/2) algorithm [Alon,Yuster,Zwick 97] mintree maxnode t maxD Tree decompositions R(x,y),S(y,z) S(y,z),T(z,u) T(z,u),K(u,x) K(u,x),R(x,y) Runtime (N2) (suboptimal) 43

  44. X Y Q() = x y z u R(x,y) S(y,z) T(z,u) K(u,x) U Z |R|,|S|,|T|,|K| N O(N3/2) algorithm [Alon,Yuster,Zwick 97] maxD mintree maxnode t Tree decompositions R(x,y),S(y,z) S(y,z),T(z,u) T(z,u),K(u,x) K(u,x),R(x,y) 44

  45. X Y Q() = x y z u R(x,y) S(y,z) T(z,u) K(u,x) U Z |R|,|S|,|T|,|K| N O(N3/2) algorithm [Alon,Yuster,Zwick 97] maxD mintree maxnode t Tree decompositions R(x,y),S(y,z) S(y,z),T(z,u) T1 min( max(h(xyz),h(zux)), max(h(yzu),h(uxy))) = T(z,u),K(u,x) K(u,x),R(x,y) 45

  46. X Y Q() = x y z u R(x,y) S(y,z) T(z,u) K(u,x) U Z |R|,|S|,|T|,|K| N O(N3/2) algorithm [Alon,Yuster,Zwick 97] maxD mintree maxnode t Tree decompositions R(x,y),S(y,z) S(y,z),T(z,u) T1 min( max(h(xyz),h(zux)), max(h(yzu),h(uxy))) = T(z,u),K(u,x) K(u,x),R(x,y) T2 46

  47. X Y Q() = x y z u R(x,y) S(y,z) T(z,u) K(u,x) U Z |R|,|S|,|T|,|K| N O(N3/2) algorithm [Alon,Yuster,Zwick 97] maxD mintree maxnode t Tree decompositions R(x,y),S(y,z) S(y,z),T(z,u) T1 min( max(h(xyz),h(zux)), max(h(yzu),h(uxy))) = T(z,u),K(u,x) K(u,x),R(x,y) T2 47

  48. X Y Q() = x y z u R(x,y) S(y,z) T(z,u) K(u,x) U Z |R|,|S|,|T|,|K| N O(N3/2) algorithm [Alon,Yuster,Zwick 97] maxD mintree maxnode t Tree decompositions R(x,y),S(y,z) S(y,z),T(z,u) T1 min( max(h(xyz),h(zux)), max(h(yzu),h(uxy))) = T(z,u),K(u,x) K(u,x),R(x,y) T2 = max(min(h(xyz),h(yzu)), min(h(xyz),h(uxy)), min(h(zux),h(yzu)), min(h(zux),h(uxy))) 48

  49. X Y Q() = x y z u R(x,y) S(y,z) T(z,u) K(u,x) U Z |R|,|S|,|T|,|K| N O(N3/2) algorithm [Alon,Yuster,Zwick 97] maxD mintree maxnode t Tree decompositions R(x,y),S(y,z) S(y,z),T(z,u) T1 min( max(h(xyz),h(zux)), max(h(yzu),h(uxy))) = T(z,u),K(u,x) K(u,x),R(x,y) 3 log N h(xy) + h(yz) + h(zu) T2 = max(min(h(xyz),h(yzu)), min(h(xyz),h(uxy)), min(h(zux),h(yzu)), min(h(zux),h(uxy))) 49

  50. X Y Q() = x y z u R(x,y) S(y,z) T(z,u) K(u,x) U Z |R|,|S|,|T|,|K| N O(N3/2) algorithm [Alon,Yuster,Zwick 97] maxD mintree maxnode t Tree decompositions R(x,y),S(y,z) S(y,z),T(z,u) T1 min( max(h(xyz),h(zux)), max(h(yzu),h(uxy))) = T(z,u),K(u,x) K(u,x),R(x,y) 3 log N h(xy) + h(yz) + h(zu) h(xyz) + h(y) + h(zu) T2 = max(min(h(xyz),h(yzu)), min(h(xyz),h(uxy)), min(h(zux),h(yzu)), min(h(zux),h(uxy))) 50

Related


You Talk The Talk But Can you Walk The Walk?

You Talk The Talk But Can you Walk The Walk?

jaspercolin
How do I talk to a real person at Icelandair?

How do I talk to a real person at Icelandair?

Milton1
Microsoft Bookings Tech Talk: Enhance Customer Experience and Boost Business Efficiency

Microsoft Bookings Tech Talk: Enhance Customer Experience and Boost Business Efficiency

aaryan
Empower Students with Tech-Talk: Enhancing Skills for Success

Empower Students with Tech-Talk: Enhancing Skills for Success

karma
Mastering the Art of Writing a Compelling Talk/Speech

Mastering the Art of Writing a Compelling Talk/Speech

wrenlee
Assistive Technology in Occupational Therapy: Case Review & TED Talk Analysis

Assistive Technology in Occupational Therapy: Case Review & TED Talk Analysis

branwen
Health and Fitness Talk for Accountants Presented by Coach Chandy

Health and Fitness Talk for Accountants Presented by Coach Chandy

tom
Engaging Grammar Talk for Writing Pedagogy

Engaging Grammar Talk for Writing Pedagogy

hassan
Real-World Evaluation of Push-to-Talk Service for Public Safety Systems

Real-World Evaluation of Push-to-Talk Service for Public Safety Systems

cheyenne
The Art of Small Talk: Navigating Social Situations with Ease

The Art of Small Talk: Navigating Social Situations with Ease

perry
Demystifying Kernels: A Simplified Approach without Complicated Math

Demystifying Kernels: A Simplified Approach without Complicated Math

leonel
Enhancing Mental Skills in Youth Hockey: A Guide for Coaches

Enhancing Mental Skills in Youth Hockey: A Guide for Coaches

del_ran
Evolution of AI: Insights from Raj Reddy's Talk at Carnegie Mellon University

Evolution of AI: Insights from Raj Reddy's Talk at Carnegie Mellon University

mhed
Enhancing Communication Skills with T.E.A.M. Talk

Enhancing Communication Skills with T.E.A.M. Talk

kaon867
National Invitational Drill Meet 2018 (NIDM 2018) Event Details

National Invitational Drill Meet 2018 (NIDM 2018) Event Details

ladel
Enhancing Math Learning with Classroom Discussions

Enhancing Math Learning with Classroom Discussions

swasey_k
Movie Talk: A Powerful Technique for Language Acquisition

Movie Talk: A Powerful Technique for Language Acquisition

font_ams
Tips for Choosing the Right School for Your Child

Tips for Choosing the Right School for Your Child

zave_395
Fuzzing Cows: The No Bull Talk on Fuzzing Security

Fuzzing Cows: The No Bull Talk on Fuzzing Security

tice_gan
Talk-Line: A Helpline for Students in Grades 3-5

Talk-Line: A Helpline for Students in Grades 3-5

fian643
Expert Tips for Delivering a 15-Minute Talk Effectively

Expert Tips for Delivering a 15-Minute Talk Effectively

acull
Small Talk in the Workplace

Small Talk in the Workplace

josephson_m

More Related Content