Three-valued logic (TRUE, FALSE, UNKNOWN) in SQL - Time & Space Complexity

Time Complexity: Three-valued logic (TRUE, FALSE, UNKNOWN)

O(n)

Understanding Time Complexity

When working with SQL, conditions can be TRUE, FALSE, or UNKNOWN. Understanding how this affects query checks helps us see how much work the database does.

We want to know how the database handles these three logic values when filtering rows.

Scenario Under Consideration

Analyze the time complexity of the following SQL WHERE clause using three-valued logic.

SELECT *
FROM employees
WHERE salary > 50000 AND department IS NOT NULL;
    

This query selects employees with salary over 50000 and a known department value, using TRUE, FALSE, and UNKNOWN logic.

Identify Repeating Operations

Look at what repeats as the database checks each row.

• Primary operation: Evaluating the WHERE condition for each row.
• How many times: Once per row in the employees table.

How Execution Grows With Input

As the number of rows grows, the database checks each row's condition once.

Input Size (n)	Approx. Operations
10	10 condition checks
100	100 condition checks
1000	1000 condition checks

Pattern observation: The work grows directly with the number of rows, checking each once.

Final Time Complexity

Time Complexity: O(n)

This means the database checks each row one time, so the work grows in a straight line with the number of rows.

Common Mistake

[X] Wrong: "The UNKNOWN results cause extra repeated checks or loops."

[OK] Correct: The database treats UNKNOWN as a simple result like TRUE or FALSE and moves on, so it does not add extra work per row.

Interview Connect

Understanding how SQL handles TRUE, FALSE, and UNKNOWN helps you explain how queries filter data efficiently, a useful skill in many database tasks.

Self-Check

What if we added an OR condition instead of AND? How would the time complexity change?

Practice

1. In SQL's three-valued logic, what is the result of comparing a column value to NULL using the = operator?

easy

A. TRUE

B. NULL

C. FALSE

D. UNKNOWN

Solution

1. Step 1: Understand comparison with NULL

   In SQL, any comparison with NULL using = does not return TRUE or FALSE but UNKNOWN.

2. Step 2: Recall three-valued logic rules

   Since NULL means unknown, the comparison result is UNKNOWN, not TRUE or FALSE.

3. Final Answer:

   UNKNOWN -> Option D

4. Quick Check:

   Comparison with NULL = UNKNOWN [OK]

Hint: Comparing with NULL using '=' always yields UNKNOWN [OK]

Common Mistakes:

• Assuming NULL equals NULL returns TRUE
• Thinking NULL comparison returns FALSE
• Confusing NULL with a string 'NULL'

2. Which of the following SQL WHERE clause conditions correctly checks if a column col contains NULL values?

easy

A. WHERE col = NULL

B. WHERE col != NULL

C. WHERE col IS NULL

D. WHERE col = 'NULL'

Solution

1. Step 1: Identify correct NULL check syntax

   In SQL, to check for NULL values, you must use IS NULL because = NULL does not work.

2. Step 2: Evaluate each option

   WHERE col IS NULL uses IS NULL, which is the correct syntax. Others compare with NULL using = or treat NULL as a string, which is incorrect.

3. Final Answer:

   WHERE col IS NULL -> Option C

4. Quick Check:

   Use IS NULL to check NULL values [OK]

Hint: Use IS NULL, not = NULL, to check for NULL values [OK]

Common Mistakes:

• Using = NULL instead of IS NULL
• Comparing NULL as a string 'NULL'
• Using != NULL to find non-NULL values

3. Given a table Employees with a column Bonus that can be NULL, what will the query SELECT * FROM Employees WHERE Bonus > 1000; return for rows where Bonus is NULL?

medium

A. Rows with NULL Bonus are excluded

B. Rows with NULL Bonus are included

C. Query returns an error

D. Rows with NULL Bonus are returned as FALSE

Solution

1. Step 1: Understand comparison with NULL in WHERE clause

   Comparing NULL with any value using > results in UNKNOWN, which is treated as FALSE in WHERE filtering.

2. Step 2: Determine which rows are returned

   Rows where Bonus is NULL do not satisfy Bonus > 1000 condition, so they are excluded from the result.

3. Final Answer:

   Rows with NULL Bonus are excluded -> Option A

4. Quick Check:

   NULL comparison in WHERE excludes rows [OK]

Hint: WHERE excludes rows with NULL in condition comparisons [OK]

Common Mistakes:

• Assuming NULL > 1000 returns TRUE
• Expecting NULL rows to appear in results
• Thinking query throws error due to NULL

4. You wrote this query: SELECT * FROM Orders WHERE Status = 'Shipped' OR Status <> 'Shipped'; but it returns fewer rows than expected. What is the likely cause?

medium

A. Rows with NULL Status are excluded due to three-valued logic

B. Syntax error in the query

C. The OR operator is invalid here

D. The query returns all rows regardless of Status

Solution

1. Step 1: Analyze the WHERE clause logic

   The condition checks if Status equals 'Shipped' OR Status not equals 'Shipped'.

2. Step 2: Consider NULL values in Status

   For rows where Status is NULL, both comparisons return UNKNOWN, so those rows are excluded.

3. Final Answer:

   Rows with NULL Status are excluded due to three-valued logic -> Option A

4. Quick Check:

   NULL comparisons exclude rows in OR conditions [OK]

Hint: NULL in OR conditions can exclude rows unexpectedly [OK]

Common Mistakes:

• Assuming NULL rows satisfy OR condition
• Thinking query has syntax error
• Believing OR always returns all rows

5. You want to select all rows from Products where Discount is either greater than 20 or unknown (NULL). Which WHERE clause correctly implements this using three-valued logic?

hard

A. WHERE Discount > 20 OR Discount = NULL

B. WHERE Discount > 20 OR Discount IS NULL

C. WHERE Discount > 20 AND Discount IS NULL

D. WHERE Discount >= 20 OR Discount IS NOT NULL

Solution

1. Step 1: Identify correct NULL check syntax

   To check for NULL values, use IS NULL, not = NULL.

2. Step 2: Combine conditions correctly

   You want rows where Discount is greater than 20 OR Discount is NULL, so use OR with Discount > 20 and Discount IS NULL.

3. Final Answer:

   WHERE Discount > 20 OR Discount IS NULL -> Option B

4. Quick Check:

   Use IS NULL with OR for NULL checks [OK]

Hint: Use IS NULL with OR to include NULLs in conditions [OK]

Common Mistakes:

• Using = NULL instead of IS NULL
• Using AND instead of OR
• Checking IS NOT NULL instead of IS NULL