<p>I want to discuss a nice series of figures used to teach <a target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Relational_model">relational join</a> semantics in <a target="_blank" rel="nofollow" href="http://r4ds.had.co.nz/"><em>R for Data Science</em> by Garrett Grolemund and Hadley Wickham, O’Reilly 2016</a>. Below is an example from their book illustrating an inner join:</p>
<p><a target="_blank" rel="nofollow" href="http://r4ds.had.co.nz/relational-data.html"><img title="NewImage.png" alt="NewImage" src="https://i0.wp.com/www.win-vector.com/blog/wp-content/uploads/2017/04/NewImage-5.png?resize=338%2C127" border="0" data-recalc-dims="1"></a></p>
<p>Please read on for my discussion of this diagram and teaching joins.<span></span></p>
<h2>Teaching joins</h2>
<p>In the above diagram two tables are laid out at angles, lines are extended from every row in each table, and a subset of the line intersections are marked as obeying the join condition and hence being in the result. It is a great diagram for discussing the meaning of joins. Being able to organize data transforms in terms of joins is a critical data science skill, so there is great value in being able to teach join theory.</p>
<p>I’ve been trying teaching joins as notional expansion followed by selection as shown in my recent <a target="_blank" rel="nofollow" href="https://github.com/WinVector/BigDataRStrata2017/">Strata Spark Workshop</a> (material developed in cooperation with Garrett Grolemend and others):</p>
<p><a target="_blank" rel="nofollow" href="https://github.com/WinVector/BigDataRStrata2017/blob/master/slides/Part01_Lecture.pdf"><img title="join.png" alt="Join" src="https://i1.wp.com/www.win-vector.com/blog/wp-content/uploads/2017/04/join.png?resize=598%2C337" border="0" data-recalc-dims="1"></a></p>
<p>However, de-emphasizing the sequence of operations and the rejected join possibilities is an attractive alternative.</p>
<h2>Deriving the diagram</h2>
<p>Many relational joins can be thought of as conditions (often denoted as “theta”) under an outer or full-join operator “⟗” of appropriately augmented tables (adding “no-match” rows to each table before taking the cross product). The join symbol and theory are supposed to evoke the notion of a cross product, so teaching in terms of that seems sensible.</p>
<p>There are many methods of illustrating a set cross product including:</p>
<ul>
<li>
<p>As a menu of possible combinations:</p>
<p><a target="_blank" rel="nofollow" href="http://warofyesterday.blogspot.com/2009/08/moon-palace.html"><img title="NewImage.png" alt="NewImage" src="https://i2.wp.com/www.win-vector.com/blog/wp-content/uploads/2017/04/NewImage-11.png?w=660" border="0" data-recalc-dims="1"></a><br>
(expanding this was the basis of my diagram).

<li>
As a complete bipartite graph:
<p><a target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Complete_bipartite_graph"><img title="bipartite.png" alt="Bipartite" src="https://i1.wp.com/www.win-vector.com/blog/wp-content/uploads/2017/04/bipartite.png?w=150" border="0" data-recalc-dims="1"></a>

<li>
As a matrix or grid:
<p><a target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Magnetic-core_memory"><img title="bipartite2.png" alt="Bipartite2" src="https://i2.wp.com/www.win-vector.com/blog/wp-content/uploads/2017/04/bipartite2.png?w=200" border="0" data-recalc-dims="1"></a>


<p>If you flip the grid to an angle where both sets of source nodes have equivalent roles then you are getting back to the diagram of Grolemund and Wickham:</p>
<p><img title="bipartite3.png" alt="Bipartite3" src="https://i1.wp.com/www.win-vector.com/blog/wp-content/uploads/2017/04/bipartite3-1.png?w=325" border="0" data-recalc-dims="1"></p>
<p>The idea is that the very many pairs induced by the full cross product are illustrated, but they are decorations on the crossing lines. This makes it easy to believe these induced nodes are <em>notional</em>, and (as is the case with real databases) only the ones needed are actually produced.</p>
<h2>Other diagrams</h2>
<p>I looked around for a short while for common SQL diagrams. </p>
<p>Venn diagrams are typically over-promoted as join mnemonics:</p>
<p><a target="_blank" rel="nofollow" href="https://blog.jooq.org/2016/07/05/say-no-to-venn-diagrams-when-explaining-joins/"><img title="NewImage.png" alt="NewImage" src="https://i1.wp.com/www.win-vector.com/blog/wp-content/uploads/2017/04/NewImage-9.png?resize=416%2C376" border="0" data-recalc-dims="1"></a></p>
<p>(Also discussed <a target="_blank" rel="nofollow" href="http://datamonkey.pro/blog/why_venn_diagram_is_a_bad_choice/">here</a>.) </p>
<p>However there were some interesting illustrations trying both the grid and bipartite graph styles.</p>
<h3>Grids</h3>
<p><a target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Cartesian_product"><img title="NewImage.png" alt="NewImage" src="https://i2.wp.com/www.win-vector.com/blog/wp-content/uploads/2017/04/NewImage-1.png?w=660" border="0" data-recalc-dims="1"></a></p>
<p><a target="_blank" rel="nofollow" href="http://www.sqlservercentral.com/articles/T-SQL/61539/"><img title="NewImage.png" alt="NewImage" src="https://i1.wp.com/www.win-vector.com/blog/wp-content/uploads/2017/04/NewImage-4.png?resize=146%2C146" border="0" data-recalc-dims="1"></a></p>
<p><a target="_blank" rel="nofollow" href="https://www.slideshare.net/MinsubYim/theta-join-mbucketi-algorithm-explained"><img title="NewImage.png" alt="NewImage" src="https://i2.wp.com/www.win-vector.com/blog/wp-content/uploads/2017/04/NewImage-2.png?resize=279%2C209" border="0" data-recalc-dims="1"></a></p>
<p><a target="_blank" rel="nofollow" href="http://www.dcs.ed.ac.uk/home/tz/phd/thesis/node20.htm"><img title="NewImage.png" alt="NewImage" src="https://i2.wp.com/www.win-vector.com/blog/wp-content/uploads/2017/04/NewImage-3.png?resize=208%2C164" border="0" data-recalc-dims="1"></a></p>
<h3>Bipartite Graphs</h3>
<p><a target="_blank" rel="nofollow" href="http://www.w3resource.com/sql/joins/cross-join.php"><img title="NewImage.png" alt="NewImage" src="https://i2.wp.com/www.win-vector.com/blog/wp-content/uploads/2017/04/NewImage-8.png?resize=293%2C177" border="0" data-recalc-dims="1"></a></p>
<h3>Hybrids</h3>
<p><a target="_blank" rel="nofollow" href="https://discourse.codinghorror.com/t/a-visual-explanation-of-sql-joins/455/199"><img title="NewImage.png" alt="NewImage" src="https://i2.wp.com/www.win-vector.com/blog/wp-content/uploads/2017/04/NewImage-6.png?resize=237%2C232" border="0" data-recalc-dims="1"></a></p>
<h2>Conclusion</h2>
<p>I like the idea of teaching all joins as filters (or theta-conditions) of the outer join. The Grolemund/Wickham diagrams are a good tool and have a style that reminds me of diagrammatic proofs of classic geometric theorems.</p>
<p><a target="_blank" rel="nofollow" href="http://www.maa.org/book/export/html/658088"><img title="NewImage.png" alt="NewImage" src="https://i2.wp.com/www.win-vector.com/blog/wp-content/uploads/2017/04/NewImage.png?resize=309%2C437" border="0" data-recalc-dims="1"></a></p>
<p><a target="_blank" rel="nofollow" href="http://www.cut-the-knot.org/pythagoras/index.shtml"><img title="NewImage.png" alt="NewImage" src="https://i1.wp.com/www.win-vector.com/blog/wp-content/uploads/2017/04/NewImage-10.png?w=660" border="0" data-recalc-dims="1"></a></p>
<img height="1" alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/7Q9IDZjacK4"></ul>