SQL Challenge: Are You Smarter Than a Fifth-Grader?
There’s a TV game show called “Are You Smarter Than a Fifth-Grader?” in which celebrities compete against fifth-graders. My friend Ravi Kulkarni who is a volunteer math coach for a math club at a middle school in Phoenix sent me a math problem that the little tykes had solved and—I have to confess—I could not solve it without his help. Just for fun, I rewrote it as an SQL challenge. It’s not as difficult as the First International NoCOUG SQL Challenge won by Alberto Dell’Era though.
A certain SQL query—the text of which is unavailable to us—has exactly 1000 tables listed in the FROM clause. No table name is repeated and there are no views involved. Call the tables T1, T2, T3, …, T1000; that is, the FROM clause is “FROM T1, T2, T3, …, T1000.” On inspecting the WHERE clause next, we find that every table in the FROM clause is joined to at least one other table listed in the FROM clause and, obviously, each table is joined to no more than 999 other tables. Let’s say that T1 is joined to J1 other tables, T2 is joined to J2 other tables, T3 is joined to J3 other tables, …, and T1000 is joined to J1000 other tables. Prove that there must be at least two tables that are joined to the same number of tables; that is, there must be at least one pair of tables—say Tx and Ty—in the SQL query such that Jx and Jy are equal.
Can you solve it? Are you smarter than a fifth-grader?