The gimmick is that you cannot do the puzzle on a plane --it works on a torus (doughnut) or a sphere, but not on a plane. The Planar Graph theorem, which is due to Kasimir Kuratowski, says that a graph is planar if and only if it has no subgraph in it that can be mapped to the two graphs named K(5) and K(3,3). The K(3,3) graph (see Figure 1) is the utility puzzle graph; the K(5) graph looks like a pentagram. (See Figure 2.)
You might remember another puzzle called the Four Color Map theorem from high school. If I give you a map and tell you to color the countries so that no two countries that share a common border have the same color (corners don't count), what is the minimum number of colors you need to use? The answer is always four, if the map is flat (for example, drawn on a plane). You can convert your map into a graph by changing the countries into nodes and their common borders into edges.
Kenneth Appel and Wolfgang Haken proved the Four Color Map theorem in 1976 by trying all possible cases on a DEC minicomputer during off hours at a university; it took over 1,200 hours of computing time.
Now look at your favorite GUI query builder or CASE tool for whatever SQL you are using. They both draw graphs on a flat screen, showing tables as boxes (nodes) and the joins or primary- and foreign-key relationships as lines (edges). They also try to avoid crossing lines (say, to generate planar graphs). This means that some fairly simple database schemas and queries cannot ever be represented by GUI tools. The usual solution is to introduce some language constructs into the GUI (the query box in QBE), which destroys the graphical basis of the tool; to generate bad code; or simply to choke.
This is one reason I hate GUI tools and recommend that people never use them. You can write simple queries fast and get the feeling that you understand SQL. But you will never write anything but simple queries -- and you will do a bad job with a lot of them, too.
Just for kicks, from one of your databases take two totally unrelated tables that both have a date column in them but no direct link between the two. Try to write a query to pair a value in one table with a value in the other table based on a common date -- something like this:
SELECT D1.duty_date, guard_name, missing_cookies
FROM DutyRoster AS D1, Thefts AS T1
WHERE D1.duty_date = T1.theft_date
ORDER BY D1.duty_date;
What you will get instead is a long chain of tables joined together via primary- and foreign-key relationships -- what we would now call a path, having had graph theory lessons.
Puzzle
Frank Langel, an Information Technology student at the University of Bamberg, asked about a problem he was having with a report query. The situation involves three tables. Tables A, B, and C all have a field called amount, and we want to calculate (A.amount -- B.amount -- C.amount).But the gimmick is that not all rows in A have a corresponding row in table B or in table C. When a row does match, there is a one-to-many relationship between A and B, and a one-to-many relationship between A and C.
- CREATE TABLE A
- (keycol INTEGER NOT NULL PRIMARY KEY,
- amount DECIMAL (5,2));
- INSERT INTO A VALUES (1, 2.50);
- INSERT INTO A VALUES (2, 3.50);
- INSERT INTO A VALUES (3, 4.50);
- INSERT INTO A VALUES (4, 5.50);
- INSERT INTO A VALUES (5, 6.50);
- INSERT INTO A VALUES (1, 2.50);
- CREATE TABLE B
- (keycol INTEGER NOT NULL,
- keycolb INTEGER NOT NULL,
- amount DECIMAL (5,2),
- PRIMARY KEY (keycol, keycolb));
- INSERT INTO B VALUES (1, 1, 2.00);
- INSERT INTO B VALUES (1, 2, 2.00);
- amount DECIMAL (5,2),
- CREATE TABLE C
- (keycol INTEGER NOT NULL,
- keycolb INTEGER NOT NULL,
- amount DECIMAL (5,2),
- PRIMARY KEY (keycol, keycolb));
- INSERT INTO C VALUES (5, 1, 2.00);
- INSERT INTO C VALUES (5, 2, 2.00);
- amount DECIMAL (5,2),
SELECT A1.amount - ISNULL (SUM (B.amount), 0) AS total FROM A AS A1 LEFT OUTER JOIN B ON A1.keycol = B.keycol GROUP BY A1.amount;
Results
total
======
-1.50
3.50
4.50
5.50
6.50
SELECT A2.amount - ISNULL (SUM (C.amount), 0) AS total FROM A AS A2 LEFT OUTER JOIN C ON A2.keycol = C.keycol GROUP BY A2.amount;
Results
total
======
2.50
3.50
4.50
5.50
2.50
His problem is that when he executes the two outer joins separately, he always gets five rows (because table A consists of five rows), but when he did the combined query:
SELECT A1.keycol, A1.amount - ISNULL (SUM (B.amount), 0.00) - ISNULL (SUM (C.amount), 0.00), .... FROM A AS A1 LEFT OUTER JOIN B ON A1.keycol = B.keycol, A AS A2 LEFT OUTER JOIN C ON A2.keycol = C.keycol WHERE A1.keycol = A2.keycol GROUP BY A1.keycol;the query did not work. Why? Can you come up with a query that does work? (See Puzzle Answer)
Joe Celko is an Atlanta-based guru with Northern Lights Software Ltd. and a member of the ANSI X3H2 Database Standards Committee. He is also the author of two books on SQL: SQL For Smarties (Morgan-Kaufmann, 1995) and Instant SQL Programming (Wrox Press, 1995). You can contact Joe via CompuServe at 71062,1056 or via email at 71062.1056@compuserve.com.
Figure 1.
--The K(3,3) graph for the utility puzzle. The puzzle works on a torus (doughnut) or a sphere, but not on a plane.
Figure 2.
--The Planar Graph theorem, which is due to Kasimir Kuratowski, says that a graph is planar if and only if it has no subgraph in it that can be mapped to the two graphs named K(5) and K(3,3). The K(3,3) graph is shown in Figure 1; the K(5) graph looks like a pentagram.
ANSWER
The first problem is that the group by syntax is wrong and will not work. A1.keycol is the only grouping column; A1.amount does not appear as either an aggregate or a grouping column.We want to total the (A+B+C) amounts, even when B and C are missing. If we clean out the group by clause, we get:
SELECT A1.keycol, (A1.amount - COALESCE (B.amount, 0.00) - COALESCE (C.amount, 0.00)) AS total FROM A AS A1 LEFT OUTER JOIN B ON A1.keycol = B.keycol, A AS A2 LEFT OUTER JOIN C ON A2.keycol = C.keycol WHERE A1.keycol = A2.keycol;
| Results | |
| keycol | total |
| ================= | |
| 1 | .50 |
| 1 | .50 |
| 2 | 3.50 |
| 3 | 4.50 |
| 4 | 5.50 |
| 5 | 4.50 |
| 5 | 4.50 |
which gives us results with all five rows using this data, as Langel wanted, but this not right yet because it cannot handle the situation where more than one row in B and more than one row in C match the A row. Notice the multiple rows with keycol equal to 1 and 5. The final query looks like this:
SELECT A1.keycol, (A1.amount - SUM (ISNULL (B.amount, 0)) - SUM (ISNULL (C.amount, 0))) AS total FROM A AS A1 LEFT OUTER JOIN B ON A1.keycol = B.keycol, A AS A2 LEFT OUTER JOIN C ON A2.keycol = C.keycol WHERE A1.keycol = A2.keycol GROUP BY A1.keycol, A1.amount;
| Results | |
| keycol | total |
| ================= | |
| 1 | -1.50 |
| 2 | 3.50 |
| 3 | 4.50 |
| 4 | 5.50 |
| 5 | 2.50 |
May 1997 Table of Contents | Other Contents | Article Index | Search | Site Index | Home
DBMS and Internet Systems (http://www.dbmsmag.com)
Copyright © 1997 Miller Freeman, Inc. ALL RIGHTS RESERVED
Redistribution without permission is prohibited.
Please send questions or comments to dbms@mfi.com
Updated Monday, April 14, 1997