# Mathematical Explanation of the Difference between SQL Joins: Inner, Outer, Left, Right

### Question

This question calls for a mathematically sound & intuitive explanation of SQL joins that clearly shows the difference between the following:

• Inner Join
• Left Join
• Right Join
• Full Outer Join

The explanation of joins should not misuse Venn diagrams. This is key. It should also be as accessible as possible to a computer programmer or mathematical beginner. We don't want to scare programmers away from mathematical concepts by using too much jargon. Of course, a little bit of maths is always necessary.

### Motivation

The internet is rife with usages of Venn diagrams to explain SQL joins. As pointed out in the following articles, this leads to a grave misunderstanding of either Venn diagrams, SQL joins or both:

As a website that many students of mathematics and computer science consult as a source of truth, it is our responsibility as a community to try everything in our power to propagate truth. Unfortunately, Venn diagram usage to explain a concept which is really Cartesian product at its core is all to rife.

Our own sister site, StackOverflow, is unfortunately part of this problem: https://stackoverflow.com/questions/38549/what-is-the-difference-between-inner-join-and-outer-join/38578#38578. While there are many amazing answers under that question, the prevailing belief on that site appears to be that joins are intersections/unions and Venn diagrams are appropriate to explain them. The top ranked and accepted answer uses Venn diagrams and intersection/union to explain joins.

While there may be some cases where join coincides with intersections and unions, it is not in general the case. I fear that people are simply seeing the special case and accepting the Venn diagram explanation. I fear they are then walking away with improper understanding of SQL joins and set theory.

I am hoping that by posting a question here, even a small percentage of people might be directed here instead of to another site that has SQL joins incorrectly explained using Venn diagrams. I am hoping that at least one of the Stack Exchange websites can have an accepted answer explaining SQL joins that is mathematically accurate, and potentially many other good alternative answers alongside it to provide different perspectives.

To be clear: I think I understand SQL joins myself. The purpose of this question is to create visibility and a source of truth for those new students of computer science and mathematics who might not understand them fully.

### Related

Is Cartesian Product same as SQL Full Outer Join?

• Yes, I asked myself the same questions back when I was a software developer. This may or may not answer your question, but have you heard of relational algebras? Relational algebras are basically the theoretical basis for many of the operations you see in database programming. May 5, 2020 at 9:28
• I give you the wikipedia link, which does have descriptions regarding outer joins, inner joins, and such. There are tons of other references :en.wikipedia.org/wiki/Relational_algebra May 5, 2020 at 9:30
• @LordVader007 I know. I am sickened by these abuses of mathematics. However, I do sympathise that this is not an easy subject for a computer programmer to understand. I think I will start a bounty. I want to contribute in whatever small way I can to propagate truth on this matter. May 7, 2020 at 18:23
• What is your 1 specific question? This post doesn't actually ask a question & is addressing both your particular presentation & requesting others. May 7, 2020 at 18:54
• My question is: an explanation of SQL join that is mathematically sound an intuitive. But I want multiple answers. I posted up my own attempt at an answer which is incomplete. May 7, 2020 at 18:55

Let $$A, B$$ be sets. We think of $$A$$ and $$B$$ as tables, and their elements as rows. Each element of $$x\in A$$ is a list of data entries, one for each column of $$A$$.

(Edit: WLOG assume $$A$$ and $$B$$ do not have duplicate entries. If they do, add a unique index column to each.)

Let $$R$$ be any relation, that is, a subset $$R \subseteq A \times B$$, where we write $$a \sim \, b$$ if $$(a,b) \in R$$. In SQL $$R$$ corresponds to the statement that appears after "ON", e.g., A.name = B.name corresponds to the relation $$x \sim y$$ if and only if the entry in the name column of for a row $$x \in A$$ is the same as the name column in a row of $$y \in A$$.

Then $$A \operatorname{ INNER JOIN } B \operatorname{ON} R = \{(a,b) \in A \times B \, |\, a \sim b\}\, (=R).$$

(Edit: Here $$(a,b)$$ represents the concatenation of the entries of rows $$a$$ and $$b$$, corresponding to SELECT * FROM A JOIN B ON R. Of course the actual output may differ depending on the implementation.)

But here, if $$a \in A$$ is such that there is no corresponding $$b$$ such that $$a \sim b$$, then $$a$$ will not appear in the join. If you take a left join, you want every $$a$$ to appear regardless. So you add a special element $$\operatorname{NULL}$$ and add it to your relation. $$\operatorname{NULL}$$ obeys the rules

$$a \sim \operatorname{NULL}$$ iff there is no $$b \in B$$ with $$a \sim b$$

$$\operatorname{NULL} \sim b$$ iff there is no $$a \in A$$ with $$a \sim b$$

Now let $$\hat{A} = A \cup \{\operatorname{NULL}\},$$ $$\hat{B} = B \cup \{\operatorname{NULL}\}.$$

Then we have

$$A \operatorname{ INNER JOIN } B \operatorname{ON} R = \{(a,b) \in A \times B \, | a \sim b\}$$ $$A \operatorname{ LEFT JOIN } B \operatorname{ON} R = \{(a,b) \in A \times \hat{B} \, | a \sim b\}$$ $$A \operatorname{ RIGHT JOIN } B \operatorname{ON} R = \{(a,b) \in \hat{A} \times B \, | a \sim b\}$$ $$A \operatorname{ OUTER JOIN } B \operatorname{ON} R = \{(a,b) \in \hat{A} \times \hat{B} \, | a \sim b\}.$$

Thus we'll have the pairs $$(a, \operatorname{NULL})$$ appear on the left join whenever $$a$$ doesn't match any $$b$$, and $$(\operatorname{NULL}, b)$$ whenever $$b$$ doesn't match any $$a$$ in the right join. (note that we don't have $$\operatorname{NULL} \sim \operatorname{NULL}$$, so we never have $$(\operatorname{NULL}, \operatorname{NULL})$$.)

The reason that Venn diagrams are used to depict joins is that usually joins are usually done on relations as simple as the one given above, $$R$$ corresponding to A.name = B.name. In that case, if $$\text{names}(T)$$ is the set of names that appear in a table $$T$$, that is, $$\text{names}(T)$$ = SELECT DISTINCT names FROM T, then

\begin{align*}\text{names}(A\operatorname{ INNER JOIN } B \operatorname{ON} R) &= \text{names}(A)\cap \text{names}(B) \\ \text{names}(A\operatorname{ LEFT JOIN } B \operatorname{ON} R) &= \text{names}(A)\\ \text{names}(A\operatorname{ RIGHT JOIN } B \operatorname{ON} R) &= \text{names}(B)\\ \text{names}(A\operatorname{ OUTER JOIN } B \operatorname{ON} R) &= \text{names}(A)\cup \text{names}(B).\end{align*}

However, this completely loses sight of the fact that joins may be one-to-one, many-to-one, or many-to-many, and personally I've found those Venn diagrams more confusing than helpful when learning about joins.

• This is not clear. Its formalization does not reflect the objects & operators involved. SQL tables are not relations & are not sets, this is part of the problem with trying to define its operators, and this post does not address all the relevant issues. Also DB tables/relations including those that ON conditions can be taken to denote are n-ary, not binary, and results of join are not Cartesian products of inputs. Even if tables were sets, the definitions would be wrong. Cardinality is not "lost sight of", it is irrelevant to the general case. Your Venn exposition is not clear. Etc. May 7, 2020 at 23:03
• Where are the definitions wrong? Can you be more specific? May 7, 2020 at 23:07
• @philipxy Inside my brain I find the explanation given here completely consistent with any example I can think of. I sense though that you have a counter-example in mind. So join the community and show it to us! You might help me/others learn. May 8, 2020 at 17:30
• @philipxy I worked through an example and I found that the information given in this answer is correct. If you think that working through an example will reveal a problem with this answer, please tell us which example to work through and what the problem is. May 12, 2020 at 4:50
• @philipxy The first thing Microsoft's Azure docs say in defining the cross join is: "A cross join returns the Cartesian product of rows from the rowsets in the join." A relation in math is described exactly as a subset of the Cartesian product. Specifying the actual grammatical structure of allowed formulas is not necessary to understand the abstract join. May 12, 2020 at 7:15

Jair Taylor has given us a precise mathematical formalism of the four type of joins in his answer, as called for. This answer supplements that one with a concrete example.

Suppose we have two tables, BuildingPrice and Buyers: And suppose we want to know which buildings can be afforded by which buyers. We can do a SQL join. Here is the inner join SQL:

SELECT * FROM BuildingPrice JOIN Buyers ON AccountBalance >= Price


The ON condition characterises the relation Jair talks about in his answer. We can then visualise all four joins (with the same ON condition), in the following diagram: In this diagram, we flip the Buyers table on its side so that its rows are now columns, i.e. we transpose it. We also add the special NULL element that Jair describes. This gives us the cross product, which is the rectangular area achieved by multiplying the columns in the transposed Buyers table, plus NULL, with the rows in the BuildingPrice table, plus NULL. All joins start with the inner join, the green area. The left, right and outer joins add extra elements as required.

Each element in the diagram that's included in the diagram is a pair of rows: one from BuildingPrice and one from Buyers. Of course, what's actually returned by a join is not a set of pairs of rows but a set of rows. So for any given pair, we convert it to a single row of the result table by simply taking the union of all the column to value mappings. For the NULL case, those mappings will all have a value of NULL. So for example, our LEFT join would result in this table: ## A Note on NULL

It is important that we have the correct, precise interpretation of NULL here, and what it means for the resulting records in the joined table. WLOG we'll just consider the LEFT JOIN case. Suppose we have an element $$x$$ of the left table which has no right table elements associated to it. This will, in Jair's characterisation, give rise to the pair $$(x,$$NULL$$)$$ being included in the join.

For the actual joined table though, we have to go a step further and convert that pair to a record i.e. a row in the resultant table. For that to work, we need to convert NULL to a column-mapping in the right table, where the value of each mapped column is NULL. So in this case, NULL is actually the map:

As correctly pointed out in the comments, the two tables will not in general have the same set of columns or even the same number of columns, so the meaning of NULL in the LEFT and RIGHT cases is different. WLOG, we're just considering the left case, in which the NULL actually means this mapping representing a row of the right table:

$$($$Buyers.Name$$\rightarrow$$NULL$$,$$ AccountBalance$$\rightarrow$$NULL$$)$$

• This is unclear. You don't actually present how to read that diagram. Write a complete concise legend for the diagram including relating it to inputs & outputs of an operator. Give a tutorial separately. Argue pro/con separately. PS Yes a square is misleading vs a rectangle. Ideally better would be smaller, say 5x4. Explain white & pink. Suggest 2 lines to separate inner cells from margins. The "NULL" & its colour & its cell are just clutter. L & R are better than x & y. PS It's not clear just what rows are from input & are in output. (Consider putting the xi/y outside all cells.) May 7, 2020 at 20:47
• When & why Venns are & are not helpful is a separate issue from a presentation of & justification for this diagram. PS The clearer the diagram gets the more it looks like the Venn diagram for the correct use of a Venn diagram for illustrating output differences between the 4 joins for the special case of input sets. Because output rows are 1:1 with cells of certain colours. (The "2 lines" get extended to 2 rectangles = 2 sets.) May 7, 2020 at 20:59
• I can see how one would suspect one might want labels running vertically & horizontally that are input row values plus an all-null row. Having one shared "NULL" is probably not a clear way to do that. In general the axes use subrows of nulls of different lengths. I don't expect having one "NULL" standing in for both null subrows is going to work. PS It may turn out that most helpful is for each row & column to be labelled both by an input row value & a null. All-pink horizontal or vertical strips choose the null row for incorporation into output. (Details & "best" to be determined.) May 7, 2020 at 23:44
• Please use text, not images/links, for text--including tables & ERDs. Use images only for what cannot be expressed as text or to augment text. Include a legend/key & explanation with an image. May 9, 2020 at 19:10

An alternative characterisation of joins starts with LEFT JOIN and defines everything from there. It is equivalent to Jair Taylor's formalism, just a different perspective. This definition is very formal so it should definitely be supplemented by other answers / concrete examples for a good intuition of JOIN.

## Definition: Values

Let's define the set $$V$$ as the set of all possible values in any possible SQL cell. So $$V$$ would be the union of all possible SQL types. The reason for doing this is so that we don't get bogged down in type-system considerations.

No matter what our universe of values is, we always assume a null value, call it $$NULL$$.

## Definition: Record(s)

Let's say we have a set of columns $$C$$. A record for $$C$$ is just a function from $$C$$ onto $$V$$. In computer science terms, imagine a dictionary or a map. Let's denote the set of all records for a column set $$C$$ as $$R_C$$:

$$R_C = C \rightarrow V$$

## Definition: Null Record

Let's say we have a set of columns $$C$$. We can define the null record for $$C$$, $$NULL_C : R_C$$ as follows:

$$NULL_C = \lambda c \mapsto NULL$$

That is, it is the function which maps every column $$c : C$$ to the value $$NULL$$.

## Definition: Table

Let's say we have a set of columns $$C$$. A table for $$C$$ is just a set of records for $$C$$. Let's denote the set of all such tables as $$T_C$$. Then:

$$T_C = \mathcal P(R_C)$$

Where $$\mathcal P$$ is just the symbol for the powerset, i.e. the set of all subsets, of a given set. So a table is just a subset of all possible records for a given set of columns.

Note: As Jair points out in his answer, although tables are in reality bags, not sets of records, we can always add an invisible column to the column set $$C$$ that must be unique, forcing a set representation. So WLOG, we'll continue with sets, which are easier to handle.

## Definition: Left Set Selector

Suppose we have two sets of columns $$C$$ and $$D$$. WLOG let's assume these sets are disjoint (in SQL, we can force column names to be disjoint by prepending the table name to get a fully qualified name). And suppose we have two tables $$t_C : T_C$$ and $$t_D : T_D$$. And suppose we are given any binary relation $$R : \mathcal P(t_C \times t_D)$$.

Then we can define a precursor to the left join. Define $$S : t_C \rightarrow \mathcal P(t_C \times t_D)$$:

$$S(r_C) = \{r_D : t_D | r_C R r_D\}$$

And then define our set selector $$LS : \mathcal P(t_c \times (t_d \cup NULL_D))$$

$$LS(r_C) = \begin{cases} S(r_C) & \text{if }S(r_C) \neq \emptyset \\ NULL_D & \text{if }S(r_C) = \emptyset \end{cases}$$

## Definition: Left Join Precursor

Given column sets $$C, D$$, and a relation $$R : \mathcal P(t_C \times t_D)$$. The left join precursor $$LJP : T_C \times T_D \rightarrow \mathcal P(T_C \times (T_D \cup \{NULL_D\}))$$ can be defined as follows:

$$LJP(t_c, t_d) = \bigcup_{r_C : T_C} LS(r_C)$$

## Record Join

Suppose we have two records $$r_C$$ and $$r_D$$ on column sets $$C$$ and $$D$$ respectively. Then we can define the joined record on the set $$C \cup D$$ as:

$$J(r_C, r_D) = \lambda x \mapsto \begin{cases} r_C(x) & x : C \\ r_D(x) & x : D \end{cases}$$

## Definition: Left Join

Given column sets $$C, D$$, and a relation $$R : \mathcal P(t_C \times t_D)$$. The left join $$L : T_C \times T_D \mapsto T_{C \cup D}$$ can be defined as:

$$L(t_C, t_D) = \{J(r_C, r_D) : R_{C \cup D}| (r_C, r_D) : LJP(t_C, t_D)\}$$

## Definition: Right Join

The right join $$RJ$$ can be defined using symmetry and the left join:

$$RJ(t_C, t_D) = LJ(t_D, t_C)$$

## Definition: Inner Join

$$I(t_C, t_D) = RJ(t_C, t_D) \cap L(t_C, t_D)$$

## Definition: Outer Join

$$O(t_C, t_D) = RJ(t_C, t_D) \cup L(t_C, t_D)$$

## Venn Diagram Relating all Four Joins The outer join is not labelled in the picture but it is the union of the areas of the two circles.

NB: THE CIRCLES IN THIS VENN DIAGRAM ARE NOT THE ORIGINAL TABLES THAT WERE JOINED. PLEASE DO NOT GLANCE OVER THIS IMAGE AND MISTAKE THEM AS SUCH.

• "we can always add an invisible column to the column set C that must be unique" That doesn't work. Eg: The output of full join can be ((null,null),(null,null)). Explain how the row-values get put in the right zones/(sub)sets of the diagram. Don't forget to account for the fact that different inputs put the row-values in different places. Note also that this can be where inputs are sets yet the output is not, so even your (& the accepted answer's) argument assuming sets on input & output is wrong. PS There is no reason to expect answers within days of posting on SE. May 10, 2020 at 23:46
• @philipxy I'll address your last point first. I am assuming that my acceptance of Jair's answer has prompted you to think that I expect speedy answers to my question? The approach I take is to give it a window of a couple of days and accept an answer that, in my opinion, achieves the bulk of what the question is looking for. However, I would be delighted if more answers came. May 11, 2020 at 8:45
• @philipxy I can't see yet where this formalism (and Jair's equivalent one) break down in the sense that you are pointing out. I think that you really need the space of an answer to flesh it out. I'm not doubting you, I just don't have enough brain power to visualise what you're saying. You're going to have to help me. And to echo the last point, I'm in no hurry for such an answer, so take your time. May 11, 2020 at 8:47
• @philipxy For now, can you give me an SQL query I can run that will return the pair of pairs of nulls that you reference? I'm intrigued... (Of course I don't expect it to be a pair of pairs in SQL, which I expect to flatten it out into a single record, but you get my point I hope) May 11, 2020 at 9:32
• I agree certain Q&As like you are talking about would be helpful. Moreover, web, SO, dba.SE & SE relational model content is atrocious. May 12, 2020 at 20:10