Combined Complexity of Conjunctive Queries with Inequalities

a nswering c onjunctive q ueries n.w
1 / 38
Embed
Share

Explore the combined complexity of computing conjunctive queries with inequalities, delving into how the addition of inequalities impacts query evaluation. Discover techniques, examples, and contributions in the realm of query plans for inequalities, shedding light on the computational intricacies involved in such scenarios.

  • Complexity
  • Inequalities
  • Query Plans
  • Conjunctive Queries
rayaanacharya
kazuhir 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. ANSWERING CONJUNCTIVE QUERIES WITH INEQUALITIES Paris Koutris1 Tova Milo2 Sudeepa Roy1 Dan Suciu1 1 University of Washington 2 Tel Aviv University ICDT 2015

  2. PROBLEM What is the combined complexity of computing conjunctive queries with inequalities (CQ )? query (q,I): q = R(x,y),S(y,z),T(z,w) I = {x z, y w} 2

  3. EXAMPLE: PATH QUERY Path query (of length k) Pk = R1(x1,x2),R2(x2,x3), ,Rk(xk,xk+1) acyclic query polynomial combined complexity R1 R2 R3 Rk . . . x1 x2 x3 xk xk+1 3

  4. EXAMPLE: PATH QUERY Path query + inequalities Pk = R1(x1,x2),R2(x2,x3), ,Rk(xk,xk+1) I = {xi xj,for all i<j} equivalent to Hamiltonian path NP-hard inequality graph R1 R2 R3 Rk . . . x1 x2 x3 xk xk+1 4

  5. EXAMPLE: PATH QUERY Path query + inequalities Pk = R1(x1,x2),R2(x2,x3), ,Rk(xk,xk+1) I = {xi xi+2, for all i} polynomial combined complexity R1 R2 R3 Rk . . . x1 x2 x3 xk xk+1 5

  6. CONTRIBUTION How does the combined complexity of computing CQs changes when we add inequalities? Given any blackbox algorithm that computes q, we can compute (q,I) with a g(q,I) log(|D|) blowup Given any Selection-Projection-Join plan that computes q, we can compute (q,I) with a f(q,I) blowup 6

  7. OUTLINE Color Coding The Main Technique Query Plans for Inequalities 7

  8. BACKGROUND [Papadimitriou, Yannakakis 97] Let q be a boolean acyclic CQ and D be a database instance. Then, q can be evaluated in time k = #variables in the inequality graph fixed-parameter tractability 8

  9. COLOR CODING: IDEA [Alon, Yuster, Zwick 97] Pick a random coloring h: Dom {1, , k} maps values to k colors If a tuple t belongs in the answer of the full query, then the colors satisfy the inequalities with probability e-k tuple a b c d col #1 1 2 1 4 q = R(x,y),S(y,z),T(z,w) I = {x z, y w} col #2 1 2 3 3 valid 9

  10. COLOR CODING: THEOREM /Theorem/ Let q be a CQthat can be computed in time T(|q|, |D|). Then, (q, I) can be computed in time Color-coding demands the construction of k-perfect hash family for every instance There is a log(|D|) additional factor The algorithm is oblivious to the combined structure of the query + inequalities 10

  11. OUTLINE Color Coding The Main Technique Query Plans for Inequalities 11

  12. MAIN TECHNIQUE q = R(x1, ,xm),S(y1, ,yl) + inequalities How do we compute (q,I) ? Cartesian product, then apply the inequalities time O(ml|R||S|) IDEA: compress R to a representation R of size independent of |R|, then compute the product R ,S 12

  13. RUNNING EXAMPLE inequality graph (bipartite) H R(x1, x2) (1,1) (1,2) (1,4) (1,8) (2,3) (2,1) (3,2) (5,2) (2,2) (2,4) y1 x1 y2 x2 y3 13

  14. H-ACCEPTED TUPLES A tuple t over the schema of S is H-accepted by R if for some t in R, t and t satisfy the inequalities in H y1 R(x1, x2) (1,1) (1,2) (1,4) (1,8) (2,3) (2,1) (3,2) (5,2) (2,2) (2,4) x1 y2 x2 y3 t = (2,1,3) is H-accepted t = (2,1,2) is not! 14

  15. H-EQUIVALENCE Relations R1, R2 are H-equivalent if for any tuple t, t is H- accepted by R1 if and only if t is H-accepted by R2 /Lemma/ There exists a sub-instance R of R s.t. R ,R are H-equivalent |R | f(H), independent of R R can be computed in time O(f(H) |R|) 15

  16. H-FORBIDDEN TUPLES A tuple t over Dom + {-} is H-forbidden for R if for every tuple t in R, the inequalities between t, t are violated R(x1, x2) (1,1) (1,2) (1,4) (1,8) (2,3) (2,1) (3,2) (5,2) (2,2) (2,4) t = (1,2,3) is H-forbidden t = (1,2,-) is also H-forbidden The H-forbidden tuples are infinitely many but the minimally H-forbidden are finite 16

  17. THE ALGORITHM R(x1, x2) (1,1) (1,2) (1,4) (-,-,-) (1,8) (1,1) (2,3) (2,1) (1,-,-) (-,-,1) (3,2) (-,1,-) (5,2) (2,2) (2,4) 17

  18. THE ALGORITHM R(x1, x2) (1,1) (1,2) (1,4) (-,-,-) (1,8) (1,1) (2,3) (2,1) (1,-,-) (-,-,1) (3,2) (-,1,-) (5,2) (1,2) (2,2) (2,4) (-,2,1) (1,-,1) (-,1,1) (1,-,-) remains H-forbidden (-,1,-) remains H-forbidden (-,-,1) is not 18

  19. THE ALGORITHM R(x1, x2) (1,1) (1,2) (1,4) (-,-,-) (1,8) (1,1) (2,3) (2,1) (1,-,-) (-,-,1) (3,2) (-,1,-) (5,2) (1,2) (2,2) (2,4) (-,2,1) (1,-,1) (-,1,1) (1,4) only the rightmost node needs expansion (1,2,1) 19

  20. THE ALGORITHM R(x1, x2) (1,1) (1,2) (1,4) (-,-,-) (1,8) (1,1) (2,3) (2,1) (1,-,-) (-,-,1) (3,2) (-,1,-) (5,2) (1,2) (2,2) (2,4) (-,2,1) (1,-,1) (-,1,1) (1,4) the tuple (1,8) expands no node (1,2,1) 20

  21. THE ALGORITHM R(x1, x2) (1,1) (1,2) (1,4) (-,-,-) (1,8) (1,1) (2,3) (2,1) (1,-,-) (-,-,1) (3,2) (-,1,-) (2,3) (5,2) (1,2) (2,3) (2,2) (2,4) (-,2,1) (1,2,-) (1,-,3) (2,1,-) (-,1,3) (1,-,1) (-,1,1) (1,3,-) (2,3) (1,4) (2,3) (2,1,1) (1,3,1) (1,2,1) (1,2,1) 21

  22. THE ALGORITHM R(x1, x2) (1,1) (1,2) (1,4) (-,-,-) (1,8) (1,1) (2,3) (2,1) (1,-,-) (-,-,1) (3,2) (-,1,-) (2,3) (5,2) (1,2) (2,3) (2,2) (2,4) (-,2,1) (1,2,-) (1,-,3) (2,1,-) (-,1,3) (1,-,1) (-,1,1) (1,3,-) (2,1) (2,3) (1,4) (2,1) (2,3) (1,2,3) (1,1,3) (2,1,1) (1,3,1) (1,3,1) (1,2,1) (1,2,1) 22

  23. THE ALGORITHM R(x1, x2) (1,1) (1,2) (1,4) (-,-,-) (1,8) (1,1) (2,3) (2,1) (1,-,-) (-,-,1) (3,2) (-,1,-) (2,3) (5,2) (1,2) (2,3) (2,2) (2,4) (-,2,1) (1,2,-) (1,-,3) (2,1,-) (-,1,3) (1,-,1) (-,1,1) (1,3,-) (3,2) (2,1) (3,2) (2,3) (1,4) (2,1) (2,3) (3,1,3) (1,2,3) (1,1,3) (2,1,1) (1,3,1) (1,3,1) (2,1,2) (1,2,1) (1,2,1) (3,2) (3,2) the node should be expanded, but has no space 23

  24. THE ALGORITHM R(x1, x2) (1,1) (1,2) (1,4) (-,-,-) (1,8) (1,1) (2,3) (2,1) (1,-,-) (-,-,1) (3,2) (-,1,-) (2,3) (5,2) (1,2) (2,3) (2,2) (2,4) (-,2,1) (1,2,-) (1,-,3) (2,1,-) (-,1,3) (1,-,1) (-,1,1) (1,3,-) (3,2) (2,1) (3,2) (2,3) (1,4) (2,1) (2,3) (3,1,3) (1,2,3) (1,1,3) (2,1,1) (1,3,1) (1,3,1) (2,1,2) (1,2,1) (1,2,1) (5,2) (5,2) (3,2) (3,2) (5,2) 24

  25. THE ALGORITHM R(x1, x2) (1,1) (1,2) (1,4) (-,-,-) (1,8) (1,1) (2,3) (2,1) (1,-,-) (-,-,1) (3,2) (-,1,-) (2,3) (5,2) (1,2) (2,3) (2,2) (2,4) (-,2,1) (1,2,-) (1,-,3) (2,1,-) (-,1,3) (1,-,1) (-,1,1) (1,3,-) (3,2) (2,1) (3,2) (2,3) (1,4) (2,1) (2,3) (3,1,3) (1,2,3) (1,1,3) (2,1,1) (1,3,1) (1,3,1) (2,1,2) (1,2,1) (1,2,1) (5,2) (5,2) (3,2) (3,2) (5,2) 25

  26. THE ALGORITHM R(x1, x2) (1,1) (1,2) (1,4) (-,-,-) (1,8) (1,1) (2,3) (2,1) (1,-,-) (-,-,1) (3,2) (-,1,-) (2,3) (5,2) (1,2) (2,3) (2,2) (2,4) (-,2,1) (1,2,-) (1,-,3) (2,1,-) (-,1,3) (1,-,1) (-,1,1) (1,3,-) (3,2) (2,1) (3,2) (2,3) (1,4) (2,1) (2,3) (3,1,3) (1,2,3) (1,1,3) (2,1,1) (1,3,1) (1,3,1) (2,1,2) (1,2,1) (1,2,1) (5,2) (5,2) (3,2) (3,2) (5,2) (1,2,-) (1,2,3)(2,1,2) (1,2,1) (1,2,1) 26

  27. ANALYSIS R(x1, x2) (1,1) (1,2) (1,4) relations with the same tree are H-equivalent tuples that do not expand a node can be removed the tree has only f(H) nodes (1,8) (2,3) (2,1) (3,2) (5,2) (2,2) (2,4) EH(R) = constant-size relation that is H-equivalent to R 27

  28. OUTLINE Color Coding The Main Technique Query Plans for Inequalities 28

  29. THEH-PROJECTION Let R(A1, , Am) X subset of A = {A1, ,Am} H a bipartite graph with sets A \ X and some set B the size of the H-projection is at most f(H) times the projection 29

  30. SPJ PLANS D C=C q(w)=R(x,y, a ),S(y,z),T(z,w) I={x z, y w, x w} E= a T(C ,D) C,E inequalities cannot be trivially added to the plan B=B S(B ,C) R(A,B,E) 30

  31. SPJ PLANS: STEPONE push projections to the top of the plan D D C=C C=C E= a E= a T(C ,D) T(C ,D) C,E B=B B=B S(B ,C) S(B ,C) R(A,B,E) R(A,B,E) 31

  32. SPJ PLANS: STEP TWO DH0 add the inequalities after the projection introduce H-projection with empty graph H0 A C,B D,A D C=C E= a T(C ,D) B=B S(B ,C) R(A,B,E) 32

  33. SPJ PLANS: STEP THREE Push projections to initial place DH0 DH0 B D,A D A C,B D,A D C=C C,EH2 C=C T(C ,D) A C H2 E= a A T(C ,D) D E= a B B=B B=B S(B ,C) S(B ,C) R(A,B,E) R(A,B,E) 33

  34. SPJ PLANS: STEP THREE Push projections to initial place DH0 DH0 B D,A D B D,A D C=C C=C E= a C,EH2 T(C ,D) T(C ,D) A C C,EH2 H2 A A C E= a D B B=B B=B S(B ,C) S(B ,C) R(A,B,E) R(A,B,E) 34

  35. MAIN RESULT /Theorem/ Let q be a CQ that can be evaluated in time T(|q|,|D|) using a Select-Project-Join plan. Then, we can compute (q, I) in time The function g depends on the joint structure of the query plan and the inequalities R1 R2 R3 Rk . . . x1 x2 x3 xk xk+1 35

  36. CONCLUSION What is the complexity of computing CQ ? color-coding for any CQ SPJ query plans with inequalities In the paper : analysis of other structural properties Open questions can we apply the technique to arbitrary join algorithms? other classes of queries: UCQs, Datalog 36

  37. Thank you! 37

  38. COLOR CODING: ALGORITHM For any (valid) k-coloring c of the inequality graph, and any hash function h For each relation R, compute the sub-relation Rc,h that satisfies the colors of c Apply the black-box join algorithm on the sub-instance with relations Rc,h Output the union for all possible colorings and hash functions 38

Related


Health Inequalities a partnership approach

Health Inequalities a partnership approach

vladimir
Lewisham Health and Care Partnership – Local Care Plan

Lewisham Health and Care Partnership – Local Care Plan

nova
Addressing Health Inequalities Through Partnership Approaches in Coventry

Addressing Health Inequalities Through Partnership Approaches in Coventry

ivaan
Addressing Health Inequalities and Vaccine Hesitancy in Shirebrook: Findings and Strategies

Addressing Health Inequalities and Vaccine Hesitancy in Shirebrook: Findings and Strategies

saige
Addressing Health Inequalities with Wirral Neighbourhoods Model

Addressing Health Inequalities with Wirral Neighbourhoods Model

poppie
Progress in Prevention and Health Inequalities - Annual Report 2023-24

Progress in Prevention and Health Inequalities - Annual Report 2023-24

jimmy
North Yorkshire Joint Local Health and Wellbeing Strategy 2023-2030 Consultation

North Yorkshire Joint Local Health and Wellbeing Strategy 2023-2030 Consultation

lettie
Addressing Ethnic Inequalities in Access to Psychological Therapies: Insights from NHS Race and Health Observatory Report

Addressing Ethnic Inequalities in Access to Psychological Therapies: Insights from NHS Race and Health Observatory Report

artem
Just Transition to Clean Mobility: Addressing Transport Poverty and Inequalities in the Energy Crisis

Just Transition to Clean Mobility: Addressing Transport Poverty and Inequalities in the Energy Crisis

leda
Addressing Health Inequalities in Humber, Coast, and Vale: Insights from BAME Experience

Addressing Health Inequalities in Humber, Coast, and Vale: Insights from BAME Experience

dudley
Systemic Inequalities Faced by Immigrant Communities in Greater Manchester

Systemic Inequalities Faced by Immigrant Communities in Greater Manchester

tenley
Addressing Inequalities in Physical Activity: Summary of Evidence

Addressing Inequalities in Physical Activity: Summary of Evidence

tammy
Inequalities Through Writing, Solving, and Graphing

Inequalities Through Writing, Solving, and Graphing

mgelst
Solving Linear Equations and Inequalities in Two Variables

Solving Linear Equations and Inequalities in Two Variables

mech_rby
Health Inequalities in Jordan: Social Determinants and Priorities

Health Inequalities in Jordan: Social Determinants and Priorities

anate
Linear Inequalities in Two Variables

Linear Inequalities in Two Variables

gann_5
Compound Inequalities: Solve, Graph, and Interpret

Compound Inequalities: Solve, Graph, and Interpret

gvir
Introduction to Inequalities: Understanding Mathematical Relationships

Introduction to Inequalities: Understanding Mathematical Relationships

zavi_639
COVID-19 Impact on Health Inequalities

COVID-19 Impact on Health Inequalities

pos_lam
Solving Systems of Linear Inequalities Graphically

Solving Systems of Linear Inequalities Graphically

gustavson_d
Research on Hearing Health Inequalities: Insights from Dr. Dalia Tsimpida

Research on Hearing Health Inequalities: Insights from Dr. Dalia Tsimpida

rosa_1
Absolute Value Equations and Inequalities

Absolute Value Equations and Inequalities

rist_jra

More Related Content