Evaluate Boolean Expression

Evaluate Boolean Expression

An expression like x > y stores its two sides as names (left_operand, right_operand), so you can only evaluate it after replacing each name with its number — and the technique that does this is self-joining the lookup table once per operand: join Variables as v1 to resolve the left name and again as v2 to resolve the right name, giving you two numbers on one row that a CASE on operator can then compare.

The problem

Table Variables(name PK, value INT) stores variables. Table Expressions(left_operand, operator, right_operand) stores boolean expressions where operator is one of <, >, = and both operands are names guaranteed to exist in Variables. For each row, emit true or false.

The one technique worth naming: join the lookup table twice

The whole puzzle reduces to a single recurring SQL pattern. A row in Expressions holds two foreign keys into the same parent table — left_operand and right_operand both point at Variables.name. You cannot resolve both with one join, because one join binds Variables to exactly one of the two columns. So you reference the parent table twice under two aliases: v1 matched on the left name, v2 matched on the right name. Each alias is an independent copy of the same physical table; the aliases are what let the optimizer treat them as two separate inputs to the join.

This is the same shape as resolving manager_id and mentor_id on an employee row, or origin and destination on a flight row. Whenever one row carries two references into the same table, the answer is two aliased joins — not a subquery per column, not a self-join on equality of rows.

The full query

SELECT e.left_operand,
       e.operator,
       e.right_operand,
       CASE e.operator
         WHEN '>' THEN IF(v1.value >  v2.value, 'true', 'false')
         WHEN '<' THEN IF(v1.value <  v2.value, 'true', 'false')
         WHEN '='  THEN IF(v1.value =  v2.value, 'true', 'false')
       END AS value
FROM   Expressions e
       JOIN Variables v1 ON e.left_operand  = v1.name
       JOIN Variables v2 ON e.right_operand = v2.name;

Standard-SQL equivalent if your engine lacks IF: replace IF(cond,'true','false') with CASE WHEN cond THEN 'true' ELSE 'false' END. Note CASE e.operator WHEN ... dispatches on the operator string; the inner test does the actual numeric comparison between the two resolved values.

Worked example, traced step by step

Inputs:

After both joins resolve each name to a number, then the CASE fires:

The last row, x = x, is the case that breaks the naive shortcut below: both operands resolve through the same alias only by coincidence of value — they are still resolved independently by v1 and v2.

Why the naive version is wrong

The tempting mistake is a single join, then comparing against a correlated subquery per operand:

-- WRONG (or at best fragile): one join, subquery for the other side
SELECT e.left_operand, e.operator, e.right_operand,
       IF(v.value > (SELECT value FROM Variables WHERE name = e.right_operand),
          'true','false') AS value   -- only handles '>'
FROM Expressions e
JOIN Variables v ON e.left_operand = v.name;

Two failure modes. First, it only resolves one operand through the join; the other becomes a per-row scalar subquery, so the optimizer often re-scans Variables for every expression row instead of doing one hash/merge join over two aliases. Second, people writing it usually hard-code a single comparison and forget the operator dispatch. The double-aliased join puts both values side by side on one row, so a single CASE operator covers all three operators cleanly and the planner sees two ordinary joins it can optimize.

Pitfalls

• Forgetting the alias and writing a self-join on row equality. JOIN Variables v ON ... referenced once cannot supply both sides. You need two distinct aliases (v1, v2); reusing one name is a syntax error, and Variables JOIN Variables without aliases is ambiguous.
• Using = as assignment instead of comparison. In SQL v1.value = v2.value inside a predicate is a boolean test, which is what you want — but in some dialects double-check you are not accidentally inside a context expecting an update.
• NULL operands. The problem guarantees every operand exists in Variables, so an INNER JOIN is correct. If that guarantee did not hold, an inner join would silently drop the expression row; you would need LEFT JOIN and decide what an unresolved operand evaluates to.
• Missing an operator branch. If the CASE omits one of <, >, =, that row returns NULL for value rather than erroring — an easy silent bug. Cover all enum values or add an ELSE.
• Type coincidence on string compare. Compare v1.value to v2.value (the integers), never the operand names — comparing names would test 'x' = 'y' as strings, which is always the wrong question.

Takeaways

• When one row holds two foreign keys into the same table, resolve them by joining that table once per reference under distinct aliases — this is the reusable pattern, not a trick specific to this puzzle.
• Aliasing makes one physical table behave as two independent join inputs; the optimizer can then do two ordinary joins instead of repeated correlated subqueries.
• Bring both resolved values onto one row first, then let a single CASE operator do the comparison — separating resolution from evaluation keeps the logic flat and complete.
• With a guaranteed-present FK, INNER JOIN is correct and faster; reach for LEFT JOIN only when an operand might be missing.

Based on LeetCode 1440 “Evaluate Boolean Expression”. Mechanism, double-aliased-join framing, traced example, and pitfalls re-authored and deepened for this guide; SQL verified against MySQL 8 semantics (IF/CASE) and ANSI SQL CASE-expression rules. Self-join-on-aliases pattern cross-referenced with Joe Celko, “SQL for Smarties,” and the PostgreSQL documentation on table aliases.