26.3.1 A Bit of History

Before the SQL-99 Standard, there was no Standard OUTER JOIN syntax, so you had to construct it by hand with a messy UNION in products like very early versions of DB2 from IBM like this:

SELECT sup_id, sup_name, order_amt -- regular INNER JOIN
FROM Suppliers, Orders
 WHERE Suppliers.sup_id = Orders.sup_id
UNION ALL
SELECT sup_id, sup_name, CAST(NULL AS INTEGER) -- preserved rows
FROM Suppliers
 WHERE NOT EXISTS
 (SELECT *
FROM Orders
WHERE Suppliers.sup_id = Orders.sup_id);

You have to use a NULL with the correct data type to make the UNION work, hence the CAST() functions. Some products are smart enough that just NULL by itself will be given the correct data type, but this is portable and safer.

The other alternative is to insert a constant of some sort to give a more meaningful result. This is easy in the case of a CHARACTER column, where a message like ‘{{NONE}}’ can be quickly understood. It is much harder in the case of a numeric column, where we could have a balance with a supplier that is positive, zero, or negative because of returns and credits. There really is a difference between a vendor that we did not use and a vendor whose returns and credits canceled out its orders.

In the second edition of this book, I described the proprietary OUTER JOIN extensions in detail. Today, they are gone and replaced by the Standard syntax. The vendor extensions were all different in syntax or semantics or both. Since they are mercifully gone, I am not going to tell you about them in this edition.

The name LEFT OUTER JOIN comes from the fact that the preserved table is on the left side of the operator. Likewise, a RIGHT OUTER JOIN would have the preserved table on the right-hand side and the FULL OUTER JOIN preserves both tables.

Here is how OUTER JOINs work in Standard SQL. Assume you are given:

and the OUTER JOIN expression

Table1
LEFT OUTER JOIN
Table2
ON Table1.a = Table2.a -- JOIN condition
 AND Table2.c = 't'; −− single table filter condition

We call Table1 the “preserved table” and Table2 the “unpreserved table” in the query. What I am going to give you is a little different, but equivalent to the ANSI/ISO standards.

(1) We build the CROSS JOIN of the two tables. Scan each row in the result set.

(2) If all search conditions in the ON clause test TRUE for that row, then you keep it.

(3) If the predicate tests FALSE or UNKNOWN for that row, then keep the columns from the preserved table, convert all the columns from the unpreserved table to NULLs and remove the duplicates. So let us execute this by hand:

Let = passed the join search condition

Let = passed the filter search condition

Step One and two:

Table1 CROSS JOIN Table2
a	b	a	c	Notes
1	w	1	r
1	w	2	s
1	w	3	t
2	x	1	r
2	x	2	s
2	x	3	t
3	y	1	r
3	y	2	s
3	y	3	t
4	z	1	r
4	z	2	s
4	z	3	t

Step three:

Table1 LEFT OUTER JOIN Table2
a	b	a	c	Notes
3	y	3	t	row(s)from step two
1	w	NULL	NULL	Sets of duplicates
1	w	NULL	NULL
1	w	NULL	NULL
2	x	NULL	NULL
2	x	NULL	NULL
2	x	NULL	NULL
3	y	NULL	NULL	removed in step two
3	y	NULL	NULL	removed in step two
4	z	NULL	NULL
4	z	NULL	NULL
4	z	NULL	NULL

the final results:

The basic rule is that every row in the preserved table is represented in the results in at least one result row.

Consider the two famous Chris Date tables from his “Suppliers and Parts” database used in his textbooks.

If you write the OUTER JOIN with only the join predicate in the ON clause, like this:

SELECT Suppliers.sup_id, SupParts.part_nbr, SupParts.part_qty
FROM Suppliers
 LEFT OUTER JOIN
 SupParts
 ON Supplier.sup_id = SupParts.sup_id
 WHERE part_qty < 200;

You get:

but if we put the search predicate in the ON clause, we get this result.

SELECT Suppliers.sup_id, SupParts.part_nbr, SupParts.part_qty
 FROM Suppliers
 LEFT OUTER JOIN
 SupParts
 ON Supplier.sup_id = SupParts.sup_id
AND part_qty < 200;

You get:

Another problem was that you could not show the same table as preserved and unpreserved in the proprietary syntax options, but it is easy in Standard SQL. For example, to find the students who have taken Math 101 and might have taken Math 102:

SELECT C1.stud_nbr, C1.math_course, C2.math_course
FROM (SELECT * FROM Courses WHERE math_course = 'Math 101') AS C1
 LEFT OUTER JOIN
 (SELECT * FROM Courses WHERE math_course = 'Math 102') AS C2
 ON C1.stud_nbr = C2.stud_nbr;

A third problem is that the order of execution matters with a chain of OUTER JOINs. That is to say, ((T1 OUTER JOIN T2) OUTER JOIN T3) does not produce the same results as (T1 OUTER JOIN (T2 OUTER JOIN T3)).

26.3.2 NULLs and OUTER JOINs

The NULLs that are generated by the OUTER JOIN can occur in columns derived from source table columns that have been declared to be NOT NULL. Even if you tried to avoid all the problems with NULLs by making every column in every table of your schema NOT NULL, they could still occur in OUTER JOIN and OLAP function results. However, a table can have NULLs and still be used in an OUTER JOIN. Consider different JOINs on the following two tables, which have NULLs in the common column:

A natural INNER JOIN on column x can only match those values that are equal to each other. But NULLs do not match to anything, even to other NULLs. Thus, there is one row in the result, on the value r in column x in both tables.

Now, do a LEFT OUTER JOIN on the tables, which will preserve table T1, and you get

Again, there are no surprises. The original INNER JOIN row is still in the results. The other two rows of T1 that were not in the equi-JOIN do show up in the results, and the columns derived from table T2 are filled with NULLs. The RIGHT OUTER JOIN would also behave the same way. The problems start with the FULL OUTER JOIN, which looks like this:

The way this result is constructed is worth explaining in detail.

First do an INNER JOIN on T1 and T2, using the ON clause condition, and put those rows (if any) in the results. Then all rows in T1 that could not be joined are padded out with NULLs in the columns derived from T2 and inserted into the results. Finally, take the rows in T2 that could not be joined, pad them out with NULLs, and insert them into the results. The bad news is that the original tables cannot be reconstructed from an OUTER JOIN. Look at the results of the FULL OUTER JOIN, which we will call R1, and SELECT the first columns from it:

The created NULLs remain and could not be differentiated from the original NULLs. But you cannot throw out those duplicate rows because they may be in the original table T1. There is now a function, GROUPING (< column name >), used with the CUBE, ROLLUP, and GROUPING SET() options which returns a 1 for original NULLs or data and 0 for created NULLs. Your vendor may allow this function to be used with the OUTER JOINs.

26.3.3 NATURAL Versus Searched OUTER JOINs

It is worth mentioning in passing that Standard SQL has a NATURAL LEFT OUTER JOIN, but it is not implemented in most versions of SQL.

A NATURAL JOIN has only one copy of the common column pairs in its result. The searched OUTER JOIN has both of the original columns, with their table-qualified names. The NATURAL JOIN has to have a correlation name for the result table to identify the shared columns. We can build a NATURAL LEFT OUTER JOIN by using the COALESCE() function to combine the common column pairs into a single column and put the results into a VIEW where the columns can be properly named, thus:

CREATE VIEW NLOJ12 (x, a, b)
AS SELECT COALESCE(T1.x, T2.x), T1.a, T2.b
 FROM T1 LEFT OUTER JOIN T2 ON T1.x = T2.x;

Unlike the NATURAL JOINs, the searched OUTER JOIN does not have to use a simple one-column equality as the JOIN search condition. The search condition can have several search conditions, use other comparisons, and so forth. For example,

as compared to

26.3.4 Self OUTER JOINs

There is no rule that forbids an OUTER JOIN on the same table. In fact, this kind of self-join is a good trick for “flattening” a normalized table into a horizontal report. To illustrate the method, start with a skeleton table defined as

CREATE TABLE Credits
(student_nbr INTEGER NOT NULL,
 course_name CHAR(8) NOT NULL,
 PRIMARY KEY (student_nbr, course_name));

This table represents student ids and a course name for each class they have taken. However, our rules say that students cannot get credit for ‘CS-102’ until they have taken the prerequisite ‘CS-101’ course; they cannot get credit for ‘CS-103’ until they have taken the prerequisite ‘CS-102’ course, and so forth. Let’s first load the table with some sample values.

Notice that student #10 has both courses, student #20 has only the first of the series, and student #3 jumped ahead of sequence and therefore cannot get credit for his ‘CS-102’ course until he goes back and takes ‘CS-101’ as a prerequisite.

What we want is basically a histogram (bar chart) for each student, showing how far he or she has gone in his or her degree programs. Assume that we are only looking at two courses; the result of the desired query might look like this (NULL is used to represent a missing value):

 (1, 'CS-101', 'CS-102')
 (2, 'CS-101', NULL)

Clearly, this will need a self-JOIN, since the last two columns come from the same table, Credits. You have to give correlation names to both uses of the Credits table in the OUTER JOIN operator when you construct a self OUTER JOIN, just as you would with any other SELF-JOIN, thus:

SELECT student_nbr, C1.course_name, C2.course_name
FROM Credits AS C1
 LEFT OUTER JOIN
 Credits AS C2
 ON C1.stud_nbr_nbr = C2.stud_nbr_nbr
AND C1.course_name = 'CS-101'
AND C2.course_name = 'CS-102';

26.3.5 Two or More OUTER JOINs

Some relational purists feel that every operator should have an inverse, and therefore they do not like the OUTER JOIN. Others feel that the created NULLs are fundamentally different from the explicit NULLs in a base table and should have a special token. SQL uses its general-purpose NULLs and leaves things at that. Getting away from theory, you will also find that vendors have often done strange things with the ways their products work.

A major problem is that OUTER JOIN operators do not have the same properties as INNER JOIN operators. The order in which FULL OUTER JOINs are executed will change the results (a mathematician would say that they are not associative). To show some of the problems that can come up when you have more than two tables, let us use three very simple two column tables. Notice that some of the column values match and some do not match, but the three tables have all possible pairs of column names in them.

 CREATE TABLE T1 (a INTEGER NOT NULL, b INTEGER NOT NULL);
 INSERT INTO T1 VALUES (1, 2);
 CREATE TABLE T2 (a INTEGER NOT NULL, c INTEGER NOT NULL);
 INSERT INTO T2 VALUES (1, 3);
 CREATE TABLE T3 (b INTEGER NOT NULL, c INTEGER NOT NULL);
 INSERT INTO T3 VALUES (2, 100);

Now let’s try some of the possible orderings of the three tables in a chain of LEFT OUTER JOINS. The problem is that a table can be preserved or unpreserved in the immediate JOIN and in the opposite state in the containing JOIN.

SELECT T1.a, T1.b, T3.c
FROM ((T1 NATURAL LEFT OUTER JOIN T2)
 NATURAL LEFT OUTER JOIN T3);
Result

SELECT T1.a, T1.b, T3.c
FROM ((T1 NATURAL LEFT OUTER JOIN T3)
 NATURAL LEFT OUTER JOIN T2);
Result

SELECT T1.a, T1.b, T3.c
FROM ((T1 NATURAL LEFT OUTER JOIN T3)
 NATURAL LEFT OUTER JOIN T2);
Result

Even worse, the choice of column, in the SELECT list can change the output. Instead of displaying T3.c, use T2.c and you will get:

SELECT T1.a, T1.b, T2.c
FROM ((T2 NATURAL LEFT OUTER JOIN T3)
 NATURAL LEFT OUTER JOIN T1);

The compiler should give you error messages about ambiguous column names.

26.3.6 OUTER JOINs and Aggregate Functions

At the start of this chapter, we had a table of orders and a table of suppliers, which were to be used to build a report to tell us how much business we did with each supplier. The query that will do this is

SELECT Suppliers.sup_id, sup_name, SUM(order_amt)
FROM Suppliers
 LEFT OUTER JOIN
 Orders
 ON Suppliers.sup_id = Orders.sup_id
 GROUP BY sup_id, sup_name;

Some suppliers’ totals include credits for returned merchandise, such that our total business with them worked out to zero dollars. Each supplier with which we did no business will have a NULL in its order_amt column in the OUTER JOIN. The usual rules for aggregate functions with NULL values apply, so these suppliers will also show a zero total amount. It is also possible to use a function inside an aggregate function, so you could write SUM(COALESCE(T1.x, T2.x)) for the common column pairs.

If you need to tell the difference between a true sum of zero and the result of a NULL in an OUTER JOIN, use the MIN() or MAX() function on the questionable column. These functions both return a NULL result for a NULL input, so an expression inside the MAX() function could be used to print the message MAX(COALESCE(order_amt, ‘No Orders’)), for example.

Likewise, these functions could be used in a HAVING clause, but that would defeat the purpose of an OUTER JOIN.

26.3.7 FULL OUTER JOIN

The FULL OUTER JOIN is a mix of the LEFT and RIGHT OUTER JOINs, with preserved rows constructed from both tables. The statement takes two tables and puts them in one result table. Again, this is easier to explain with an example than with a formal definition.

26.7.1 Inventory and Orders

The simplest example is filling customer orders from the inventories that we have at various stores. To make life easier, assume that we have only one product, process orders in increasing customer_id order (this could be temporal order as well), and draw from store inventory by increasing store_id (this could be nearest store).

CREATE TABLE Inventory
(store_id INTEGER NOT NULL PRIMARY KEY,
 item_qty INTEGER NOT NULL CHECK (item_qty >=0));
INSERT INTO Inventory (store_id, item_qty)
VALUES (10, 2), (20, 3), (30, 2);
CREATE TABLE Orders
(customer_id CHAR(5) NOT NULL PRIMARY KEY,
 item_qty INTEGER NOT NULL CHECK (item_qty > 0));
INSERT INTO Orders (customer_id, item_qty)
VALUES ('Bill', 4), ('Fred', 2);

What we want to do is fill Bill’s order for 4 units by taking 2 units from store #10, and 2 units from store #20. Next, we process Fred’s order with the 1 unit left in store #10 and 1 unit from store #3.

SELECT I.store_id, O.customer_id,
 (CASE WHEN O.end_running_qty <= I.end_running_qty
 THEN O.end_running_qty
 ELSE I.end_running_qty END
 - CASE WHEN O.start_running_qty >=I.start_running_qty
 THEN O.start_running_qty
 ELSE I.start_running_qty END)
 AS items_consumed_tally
 FROM (SELECT I1.store_id,
 SUM(I2.item_qty) - I1.item_qty,
 SUM(I2.item_qty)
 FROM Inventory AS I1, Inventory AS I2
 WHERE I2.store_id <= I1.store_id
 GROUP BY I1.store_id, I1.item_qty)
AS I (store_id, start_running_qty, end_running_qty)
 INNER JOIN
 (SELECT O1.customer_id,
 SUM(O2.item_qty) - O1.item_qty,
 SUM(O2.item_qty) AS end_running_qty
 FROM Orders AS O1, Orders AS O2
 WHERE O2.customer_id <= O1.customer_id
GROUP BY O1.customer_id, O1.item_qty)
 AS O(customer_id, start_running_qty, end_running_qty)
 ON O.start_running_qty < I.end_running_qty
 AND O.end_running_qty > I.start_running_qty;

This can also be done with ordinal functions.

26.7.2 Stable Marriages

This is a classic programming problem from procedural language classes. The set up is fairly simple; you have a set of potential husbands and an equal sized set of potential wives. We want to pair them up into stable marriages.

What is a stable marriage? In 25 words or less, a marriage in which neither partner can do better. You have a set of n men and a set of n women. All the men have a preference scale for all the women that ranks them from 1 to n without gaps or ties. The women have the same ranking system for the men. The goal is to pair off the men and women into n marriages such that there is no pair in your final arrangement where Mr. X and Ms. Y are matched to each other when they both would rather be matched to someone else.

For example, let’s assume the husbands are (‘Joe Celko,’ ‘Brad Pitt’) and the wives are (‘Jackie Celko,’ ‘Angelina Jolie’). If Jackie got matched to Mr. Pitt, she would be quite happy. And I would enjoy Ms. Jolie’s company. However, Mr. Pitt and Ms. Jolie can both do better than us. Once they are paired up, they will stay that way, leaving Jackie and me still wed.

The classic Stable Marriage algorithms usually are based on backtracking. These algorithms try a combination of couples and then attempt to fix any unhappy matches. When the algorithm hits on a situation where nobody can improve their situation, they stop and give an answer.

Two important things to know about this problem: (1) there is always a solution and (2) there is often more than one solution. Remember that a stable marriage is not always a happy marriage. In fact, in this problem, while there is always at least one arrangement of stable marriages in any set, you most often find many different pairings that produce a set of stable marriages. Each set of marriages will tend to maximize either the happiness of the men or the women.

CREATE TABLE Husbands
(man CHAR(2) NOT NULL,
 woman CHAR(2) NOT NULL,
 PRIMARY KEY (man, woman),
 ranking INTEGER NOT NULL);
CREATE TABLE Wives
(woman CHAR(2) NOT NULL,
 man CHAR(2) NOT NULL,
 PRIMARY KEY (woman, man),
 ranking INTEGER NOT NULL);
CREATE TABLE Wife_Perms
(perm INTEGER NOT NULL PRIMARY KEY,
 wife_name CHAR(2) NOT NULL);
-- The men's preferences
INSERT INTO Husbands -- husband #10
VALUES ('h1', 'w1', 5), ('h1', 'w2', 2),
('h1', 'w3', 6), ('h1', 'w4', 8),
('h1', 'w5', 4), ('h1', 'w6', 3),
('h1', 'w7', 1), ('h1', 'w8', 7);
INSERT INTO Husbands -- husband #20
VALUES ('h2', 'w1', 6), ('h2', 'w2', 3),
('h2', 'w3', 2), ('h2', 'w4', 1),
('h2', 'w5', 8), ('h2', 'w6', 4),
('h2', 'w7', 7), ('h2', 'w8', 5);
INSERT INTO Husbands -- husband #3
VALUES ('h3', 'w1', 4), ('h3', 'w2', 2),
('h3', 'w3', 1), ('h3', 'w4', 3),
('h3', 'w5', 6), ('h3', 'w6', 8),
('h3', 'w7', 7), ('h3', 'w8', 5);
INSERT INTO Husbands -- husband #4
VALUES ('h4', 'w1', 8), ('h4', 'w2', 4),
('h4', 'w3', 1), ('h4', 'w4', 3),
('h4', 'w5', 5), ('h4', 'w6', 6),
('h4', 'w7', 7), ('h4', 'w8', 2);
INSERT INTO Husbands -- husband #5
VALUES ('h5', 'w1', 6), ('h5', 'w2', 8),
('h5', 'w3', 2), ('h5', 'w4', 3),
('h5', 'w5', 4), ('h5', 'w6', 5),
('h5', 'w7', 7), ('h5', 'w8', 1);
INSERT INTO Husbands -- husband #6
VALUES ('h6', 'w1', 7), ('h6', 'w2', 4),
('h6', 'w3', 6), ('h6', 'w4', 5),
('h6', 'w5', 3), ('h6', 'w6', 8),
('h6', 'w7', 2), ('h6', 'w8', 1);
INSERT INTO Husbands -- husband #7
VALUES ('h7', 'w1', 5), ('h7', 'w2', 1),
('h7', 'w3', 4), ('h7', 'w4', 2),
('h7', 'w5', 7), ('h7', 'w6', 3),
('h7', 'w7', 6), ('h7', 'w8', 8);
INSERT INTO Husbands -- husband #8
VALUES ('h8', 'w1', 2), ('h8', 'w2', 4),
('h8', 'w3', 7), ('h8', 'w4', 3),
('h8', 'w5', 6), ('h8', 'w6', 1),
('h8', 'w7', 5), ('h8', 'w8', 8);
-- The women's preferences
INSERT INTO Wives -- wife #1
VALUES ('w1', 'h1', 6), ('w1', 'h2', 3),
 ('w1', 'h3', 7), ('w1', 'h4', 1),
('w1', 'h5', 4), ('w1', 'h6', 2),
 ('w1', 'h7', 8), ('w1', 'h8', 5);
INSERT INTO Wives -- wife #2
VALUES ('w2', 'h1', 4), ('w2', 'h2', 8),
 ('w2', 'h3', 3), ('w2', 'h4', 7),
 ('w2', 'h5', 2), ('w2', 'h6', 5),
 ('w2', 'h7', 6), ('w2', 'h8', 1);
INSERT INTO Wives -- wife #3
VALUES ('w3', 'h1', 3), ('w3', 'h2', 4),
 ('w3', 'h3', 5), ('w3', 'h4', 6),
 ('w3', 'h5', 8), ('w3', 'h6', 1),
 ('w3', 'h7', 7), ('w3', 'h8', 2);
INSERT INTO Wives -- wife #4
VALUES ('w4', 'h1', 8), ('w4', 'h2', 2),
 ('w4', 'h3', 1), ('w4', 'h4', 3),
 ('w4', 'h5', 7), ('w4', 'h6', 5),
 ('w4', 'h7', 4), ('w4', 'h8', 6);
INSERT INTO Wives -- wife #5
VALUES ('w5', 'h1', 3), ('w5', 'h2', 7),
 ('w5', 'h3', 2), ('w5', 'h4', 4),
 ('w5', 'h5', 5), ('w5', 'h6', 1),
 ('w5', 'h7', 6), ('w5', 'h8', 8);
INSERT INTO Wives -- wife #6
VALUES ('w6', 'h1', 2), ('w6', 'h2', 1),
 ('w6', 'h3', 3), ('w6', 'h4', 6),
 ('w6', 'h5', 8), ('w6', 'h6', 7),
 ('w6', 'h7', 5), ('w6', 'h8', 4);
INSERT INTO Wives -- wife #7
VALUES ('w7', 'h1', 6), ('w7', 'h2', 4),
 ('w7', 'h3', 1), ('w7', 'h4', 5),
 ('w7', 'h5', 2), ('w7', 'h6', 8),
 ('w7', 'h7', 3), ('w7', 'h8', 7);
INSERT INTO Wives -- wife #8
VALUES ('w8', 'h1', 8), ('w8', 'h2', 2),
 ('w8', 'h3', 7), ('w8', 'h4', 4),
 ('w8', 'h5', 5), ('w8', 'h6', 6),
 ('w8', 'h7', 1), ('w8', 'h8', 3);
-- This auxiliary table helps us create all permutations of the wives.
INSERT INTO Wife_Perms
VALUES (1, 'w1'), (2, 'w2'), (4, 'w3'), (8, 'w4'),
(16, 'w5'), (32, 'w6'), (64, 'w7'), (128, 'w8'),

The query builds all permutation of wives and then filters them for blocking pairs in an elaborate NOT EXISTS() predicate.

SELECT A.wife_name AS h1, B.wife_name AS h2,
C.wife_name AS h3, D.wife_name AS h4,
E.wife_name AS h5, F.wife_name AS h6,
G.wife_name AS h7, H.wife_name AS h8
 FROM Wife_Perms AS A, Wife_Perms AS B,
Wife_Perms AS C, Wife_Perms AS D,
Wife_Perms AS E, Wife_Perms AS F,
Wife_Perms AS G, Wife_Perms AS H
 WHERE A.perm + B.perm + C.perm + D.perm
 + E.perm + F.perm + G.perm + H.perm = 255
AND NOT EXISTS
 (SELECT *
 FROM Husbands AS W, Husbands AS X, Wives AS Y, Wives AS Z
WHERE W.man = X.man
AND W.ranking > X.ranking
AND X.woman = Y.woman
AND Y.woman = Z.woman
AND Y.ranking > Z.ranking
AND Z.man = W.man
AND W.man||W.woman
 IN ('h1'||A.wife_name, 'h2'||B.wife_name,
'h3'||C.wife_name, 'h4'||D.wife_name,
'h5'||E.wife_name, 'h6'||F.wife_name,
h7'||G.wife_name, 'h8'||H.wife_name)
 AND Y.man||Y.woman
IN ('h1'||A.wife_name, 'h2'||B.wife_name,
 'h3'||C.wife_name, 'h4'||D.wife_name,
 'h5'||E.wife_name, 'h6'||F.wife_name,
 'h7'||G.wife_name, 'h8'|| H.wife_name))

The results look like this:

This booklet, which reproduces seven expository lectures given by the author in November 1975, is a gentle introduction to the analysis of algorithms using the beautiful theory of stable marriages as a vehicle to explain the basic paradigms of that subject.

Wirth, Nicklaus; Algorithms + Data Structures = Programs. Section 3.6. ISBN 0-13-022418-9

This section gives an answer in Pascal and a short analysis of the algorithm. In particular, I used his data for my example. He gives several answers which give a varying “degrees of happiness” for husbands and wives.

26.7.3 Ball and Box Packing

This example was taken from the BeyondRelational Website SQL Challenge #22 in 2010 January. We have got some boxes and balls. Our job is to put balls into those boxes. But, wait a second. The balls should be filled into the boxes based on some rules and preferences configured by the user. Here are the rules.

1. A box can have only one ball

2. A ball can be placed only in one box

3. Number of balls and number of boxes will always be the same.

4. All boxes should be filled and all balls should be used

5. There will be a configuration table where the preferences of the user will be stored. The preference setting should be followed when putting a ball into a box.

CREATE TABLE Boxes
(box_nbr INTEGER NOT NULL PRIMARY KEY,
 box_name VARCHAR(20) NOT NULL);
INSERT INTO Boxes (box_nbr, box_name)
VALUES (1, 'Box 1'), (2, 'Box 2'), (3, 'Box 3'),
(4, 'Box 4'), (5, 'Box 5'), (6, 'Box 6'),
CREATE TABLE Balls
(ball_nbr INTEGER NOT NULL PRIMARY KEY,
 ball_name VARCHAR(20) NOT NULL);
INSERT INTO Balls (ball_name)
VALUES (1, 'Ball 1'), (2, 'Ball 2'), (3, 'Ball 3'),
(4, 'Ball 4'), (5, 'Ball 5'), (6, 'Ball 6'),
CREATE TABLE Preferences
(box_nbr INTEGER NOT NULL
REFERENCES Boxes (box_nbr),
 ball_nbr INTEGER NOT NULL
REFERENCES Balls (ball_nbr),
 PRIMARY KEY (box_nbr, ball_nbr));
INSERT INTO Preferences (box_nbr, ball_nbr)
VALUES (1, 1),
(2, 1), (2, 3),
(3, 2), (3, 3),
(4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6),
(5, 4), (5, 5),
(6, 5);
Results

This answer is done in parts to expose the logic via CTEs. The Balls_In_Boxes CTE gives us all the possible arrangements of six balls in six boxes. This is passed to the Preferred_Balls_In_Boxes CTE to apply the preference rules but allow duplicate balls if two or more boxes want them. Finally, the main query makes sure that we keep only the rows with unique balls.

The use of the IN() predicates to assure that the row has no duplicate columns is easy to extend to any number of items, but a bit bulky to read. But it is remarkably fast in the SQL engines where we tested it.

WITH
Balls_In_Boxes (bx1, bx2, bx3, bx4, bx5, bx6)
AS
(SELECT B1.ball_nbr, B2.ball_nbr, B3.ball_nbr,
B4.ball_nbr, B5.ball_nbr, B6.ball_nbr
FROM Balls AS B1, Balls AS B2, Balls AS B3,
Balls AS B4, Balls AS B5, Balls AS B6
WHERE B1.ball_nbr NOT IN (B2.ball_nbr, B3.ball_nbr, B4.ball_nbr, B5.ball_nbr, B6.ball_nbr)
AND B2.ball_nbr NOT IN (B3.ball_nbr, B4.ball_nbr, B5.ball_nbr, B6.ball_nbr)
AND B3.ball_nbr NOT IN (B4.ball_nbr, B5.ball_nbr, B6.ball_nbr)
AND B4.ball_nbr NOT IN (B5.ball_nbr, B6.ball_nbr)
AND B5.ball_nbr NOT IN (B6.ball_nbr)),
Preferred_Balls_In_Boxes (bx1, bx2, bx3, bx4, bx5, bx6)
AS
(SELECT bx1, bx2, bx3, bx4, bx5, bx6
 FROM Balls_In_Boxes AS BB
 WHERE BB.bx1
IN (SELECT ball_nbr
FROM Preferences AS P
 WHERE box_nbr = 1)
AND BB.bx2
IN (SELECT ball_nbr
FROM Preferences AS P
 WHERE box_nbr = 2)
AND BB.bx3
IN (SELECT ball_nbr
FROM Preferences AS P
 WHERE box_nbr = 3)
AND BB.bx4
IN (SELECT ball_nbr
FROM Preferences AS P
 WHERE box_nbr = 4)
AND BB.bx5
IN (SELECT ball_nbr
FROM Preferences AS P
 WHERE box_nbr = 5)
AND BB.bx6
IN (SELECT ball_nbr
FROM Preferences AS P
 WHERE box_nbr = 6))
SELECT bx1, bx2, bx3, bx4, bx5, bx6
FROM Preferred_Balls_In_Boxes AS PBB1
 WHERE PBB1.bx NOT IN (PBB2.bx, PBB3.bx, PBB4.bx, PBB5.bx, PBB6.bx)
 AND PBB2.bx NOT IN (PBB3.bx, PBB4.bx, PBB5.bx, PBB6.bx)
 AND PBB3.bx NOT IN (PBB4.bx, PBB5.bx, PBB6.bx)
 AND PBB4.bx NOT IN (PBB5.bx, PBB6.bx)
 AND PBB5.bx NOT IN (PBB6.bx);

26.8.1 A Procedural Approach

The place to start is with all the possible legal room assignments for a class. We have already seen this query:

SELECT R.room_nbr, C.class_nbr
FROM Rooms AS R, Classes AS C
 WHERE C.class_size <= R.room_size
 ORDER BY R.room_nbr, C.class_nbr;

At the extreme, if all the rooms and classes are the same size, then your have (n!) solutions. If all the rooms are different sizes, we can save ourselves combinatorial explosions, so let us agree that we will juggle the data to get that condition. This query will give us the pairs that are an exact fit, but we know that there will not be any ties for room size.

SELECT R.room_nbr, C.class_nbr
FROM Rooms AS R, Classes AS C
 WHERE C.class_size <= R.room_size
 GROUP BY R.room_nbr, C.class_nbr
HAVING MIN(R.room_size - C.class_size) = 0;

This leaves us with class {c1} and rooms {r4, r5} yet to be used. We can then repeat a limited version of the basic Pairs query.

SELECT R.room_nbr, C.class_nbr
FROM Rooms AS R, Classes AS C
 WHERE C.class_size <= R.room_size
 AND R.room_nbr IN ('r4', 'r5')
 AND C.class_nbr IN ('c1'),

We can now union these result sets and have an answer. I took some extra time to show the details to demonstrate how we can implement a best-fit, greedy algorithm. Let us get a bigger data set and work with it.

INSERT INTO Classes (class_nbr, class_size)
VALUES
('c01', 106), ('c02', 105), ('c03', 104), ('c04', 100), ('c05', 99),
('c06', 90), ('c07', 89), ('c08', 88), ('c09', 83), ('c10', 82),
('c11', 81), ('c12', 65), ('c13', 50), ('c14', 49), ('c15', 30),
('c16', 29), ('c17', 28), ('c18', 20), ('c19', 19);
INSERT INTO Rooms (room_nbr, room_size)
VALUES
('r01', 102), ('r02', 101), ('r03', 95), ('r04', 94), ('r05', 85),
('r06', 70), ('r07', 55), ('r08', 54), ('r09', 35), ('r10', 34),
('r11', 25), ('r12', 18);

To see how this will work, let’s add another column to the table of legal (class_nbr, room_nbr) pairs to see how well they fit.

WITH Pairs (room_nbr, class_nbr, fit)
AS
(SELECT R.room_nbr, C.class_nbr,
(R.room_size - C.class_size)
FROM Rooms AS R, Classes AS C
 WHERE C.class_size <= R.room_size)
 SELECT P1.room_nbr, P1.class_nbr, fit
 FROM Pairs AS P1
WHERE P1.fit
= (SELECT MIN(P2.fit)
FROM Pairs AS P2
 WHERE P1.room_nbr = P2.room_nbr);

This time we did not have an exact fit, so let’s look for (fit = 1) into a working table and remove ‘r02’ and ‘c04’ from their tables. The second step is

We can now remove the best fit rooms and classes and look the next set of remaining best fits.

WITH Pairs (room_nbr, class_nbr, fit)
AS
(SELECT R.room_nbr, C.class_nbr,
(R.room_size - C.class_size)
 FROM Rooms AS R, Classes AS C
 WHERE C.class_size <= R.room_size)
(SELECT P1.room_nbr, P1.class_nbr, fit
 FROM Pairs AS P1
WHERE P1.fit = 2);

Here is the step for a fit of 3, 4, 5, and 6

At this point, the original tables of rooms and classes cannot be paired. Notice that as we removed rooms and classes, the fit numbers changed. This is a characteristic of greedy algorithms; taking the “big bites” can leave sub-optimal leftovers on the plate.

26.9.1 Last Known Value

The number of NULL (unknown) values between known values is not consistently the same. I arranged them on the same line to make it easy to see which values would be carried over which rows.

SELECT reading_nbr, foo_reading,
MAX(foo_reading)
OVER (PARTITION BY reading_cnt) AS prior_foo_reading
FROM (SELECT reading_nbr, foo_reading,
COUNT(foo_reading)
OVER (ORDER BY reading_nbr) AS reading_cnt
 FROM Foo_Meters)
AS prior_foo_reading;

26.9.2 Sequence Missing Readings

Suppose we want something slightly different filling in the NULL values, for example, a sequence of the same PARTITION we constructed can be used in this case, and so can the ROW_NUMBER in the preceding example.

SELECT reading_nbr, foo_reading,
COALESCE(foo_reading,
ROW_NUMBER()
OVER (PARTITION BY c
ORDER BY reading_nbr) -1) AS s
 FROM (SELECT reading_nbr, foo_reading,
COUNT(foo_reading) OVER (ORDER BY reading_nbr) AS c
 FROM Foo_Meters) AS A;

26.9.3 Smoothed Result

Suppose we want a bit smoother transition from our trailing value to our following value. This could be particularly appealing if we have many NULL rows between sparse data points. Let’s illustrate this by looking at the first four rows of the above results set.

First let’s look at some intermediate results using ROW_NUMBER() and the COUNT window aggregate.

SELECT reading_nbr, foo_reading, s, m, x
 FROM (SELECT reading_nbr, foo_reading,
MAX(foo_reading)
 OVER (PARTITION BY c) AS s,
ROW_NUMBER()
 OVER (PARTITION BY c ORDER BY reading_nbr DESC) AS n,
ROW_NUMBER()
 OVER (PARTITION BY c ORDER BY reading_nbr) – 1 AS m,
1 + COUNT(CASE WHEN foo_reading IS NULL THEN 1 END)
 OVER (PARTITION BY c) AS x
 FROM (SELECT reading_nbr, foo_reading,
 COUNT(foo_reading) OVER (ORDER BY reading_nbr) AS c
 FROM Foo_Meters) AS A
) AS A;

Our intermediate results look pretty useful:

You can see that all three of our calculated columns are what we need to produce the smoothing calculation shown prior. The first, s, is of course our original smear. The columns m and x, when m is divided by x, produce the multiplier we need. We have omitted the LEAD result, but in the end, we’ll use that also (so n is likewise still required).

Putting that all together, we get this.

SELECT reading_nbr, foo_reading,
CASE
WHEN foo_reading IS NOT NULL
THEN foo_reading
ELSE s + (1.0 * m / x)
 * (LEAD(foo_reading, n, s)
OVER (ORDER BY reading_nbr) - s)
 END AS computed_foo_reading
FROM (SELECT reading_nbr, foo_reading, (MAX(foo_reading) OVER (PARTITION BY c)) AS s,
 (ROW_NUMBER() OVER (PARTITION BY c ORDER BY reading_nbr DESC)) AS n,
 (ROW_NUMBER() OVER (PARTITION BY c ORDER BY reading_nbr) - 1) AS m,
 1 + COUNT(CASE WHEN foo_reading IS NULL
 THEN 1 ELSE NULL END)
 OVER (PARTITION BY c) AS x
FROM (SELECT reading_nbr, foo_reading,
(COUNT(foo_reading) OVER (ORDER BY reading_nbr)) AS c
FROM Foo_Meters) AS F1
) AS F2;

We have just done a simple linear interpolation in T-SQL!