Graph Homomorphism and GYO Reduction Techniques
Learn about graph homomorphism, which is a function mapping vertices of one graph to another, and GYO reduction technique for efficient join tree construction. Understand the concepts with examples and definitions provided in this comprehensive lecture material.
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.
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
L13: Conjunctive query containment L13: Conjunctive query containment Disclaimer: These notes have not been subjected to the usual scrutiny reserved for formal publications. They may be distributed outside this class only with the permission of the Instructor. Scribe: ??? CS7240 Principles of scalable data management (sp21) https://northeastern-datalab.github.io/cs7240/sp21/ Lecturer: Wolfgang Gatterbauer Version Jan 17, 2021 1
Example strong and weak entity sets Section Course sec_id semester year course_id title credits sec_course Course Section course_id title credits sec_id semester year sec_course Version Oct 23, 2020 2
Graph Homomorphism beyond graphs Definition Definition : : Let G and H be graphs. A homomorphism of G to H is a function f: V(G) V(H) such that xy E(G) f(x) f(y) E(H). (G H) if there is a homomorphism (no H) if there is a homomorphism (no We sometimes write We sometimes write G H homomorphism) of G to H homomorphism) of G to H G H (G Definition of a homomorphism naturally extends to: Definition of a homomorphism naturally extends to: digraphs digraphs edge edge- -colored graphs colored graphs relational systems relational systems constraint satisfaction problems ( constraint satisfaction problems (CSPs CSPs) ) 3
[Chandra and Merlin 1977] If there is a homomorphism hfrom q2 to q1 , then q1 q2 1. Given h=h2 1, we will show that for any D: q1(D) q2(D) 2. For q1(D) to hold, there is a valuation v s.t. v(q1) D 3. We will show that the composition g = v h is a valuation for q2 3a. By definition of h, for every R(x1,x2,...) in q2, R(h(x1),h(x2),...) in q1 3b. By definition of v, for every R(x1,x2,...) in q2, R(v(h(x1)),v(h(x2)),...) in D g(x)=v(h(x)) Example q1() :- R(x,y), R(y,y), R(y,z) q2() :- R(s,u), R(u,w), R(s,v), R(u,w), R(u,v) R(u,v): R(h(u),h(v)) = R(y,y) R A B x y y y y z v={(x,'x'),(y,'y'),(z,'z')} y z v w q2(x) h={(s,x),(u,y),(v,y),(w,z)} q1(x) g={(s,'x'),(u,'y'),(v,'y'),(w,'z')} x u s 4
GYO reduction (Graham-Yu-Ozsoyoglu) GYO Ear removal - remove ears (= edges) 1. remove isolated nodes (variables) 2. remove consumed or empty edges (atoms) (An ear is a hyperedge H such that we can divide its nodes into two groups: - those that appear in H and no other hyperedge, and - those that are contained in another hyperedge G.) - Reduction sequence allows to build a join tree efficiently R(y,u,w),S(z,p,w),T(x,u,p),U(u,p,w) Background: - Atom R(z) is empty if |z|=0 - Atom R1(z1) is contained in R2(z2) if z1 z2 5
