Relational CalculusSafe Queries

Safe Queries in Relational Calculus

LevelIntermediate

Duration60 mins

TopicSafe Queries

3 / 5

Safety Conditions

A Practical Test for Query Well-Formedness

We've established that safe queries are domain-independent and produce finite results, while unsafe queries have ambiguous semantics and potentially infinite results. But how do we determine whether a specific query is safe without running it?

The answer lies in safety conditions—syntactic rules that we can check by inspecting the query structure. If a query satisfies these conditions, it is guaranteed to be safe. These conditions provide a practical, mechanical test for query well-formedness.

What You Will Learn

By the end of this page, you will understand the formal safety conditions for both Tuple Relational Calculus and Domain Relational Calculus, be able to verify whether a query satisfies safety conditions, and understand why these syntactic rules guarantee semantic safety.

The Need for Syntactic Conditions

Recall our fundamental problem: determining whether an arbitrary relational calculus expression is domain-independent (equivalently, safe) is undecidable in general. We cannot write an algorithm that correctly answers 'is this query safe?' for all possible queries.

However, we can define sufficient conditions:

Sufficient vs. Necessary Conditions

Safety conditions are sufficient but not necessary. If a query satisfies the conditions, it is definitely safe. However, some semantically safe queries may fail the syntactic check. This is an intentional trade-off: we accept some false negatives (safe queries flagged as potentially unsafe) to guarantee no false positives (unsafe queries incorrectly approved).

Why Syntactic Conditions Work:

The safety conditions are designed to ensure that every variable occurring free in the result is 'range-restricted'—its possible values are limited to those appearing in the database. By checking structural properties of the formula, we can guarantee this semantic property without actually evaluating the query.

The Three-Step Verification:

Identify all free variables (those appearing in the result)
For each free variable, verify it is constrained by positive database predicates
For quantified subformulas, verify bound variables are appropriately restricted

Range-Restricted Variables

The core concept underlying safety conditions is range restriction. A variable is range-restricted if its possible values are confined to the active domain—values actually appearing in the database.

Formal Definition

A variable x is range-restricted in a formula φ if, for any database instance I and underlying domain D ⊇ adom(I), the possible values of x that can satisfy φ are contained in adom(I).

Examples of Range-Restricted Variables:

Range Restriction Examples
Formula	Variable	Range-Restricted?	Reason
R(x)	x	✓ Yes	x must be in relation R
R(x) ∧ S(y)	x, y	✓ Yes	Both bound to database relations
R(x) ∧ x = y	x, y	✓ Yes	y equals x, which is in R
¬R(x)	x	✗ No	x can be any value NOT in R
x = 5	x	✗ No	No database predicate binds x
R(x) ∨ S(y)	x, y	✗ No	Each var may not be bound
R(x) ∧ ¬S(y)	x, y	x:Yes, y:No	x is bound, y is not

The Propagation Rules:

Range restriction propagates through formulas according to specific rules:

Base case: If R(x₁, ..., xₙ) appears positively, all xᵢ are range-restricted by R.
Equality: If x is range-restricted and x = y appears, then y is also range-restricted.
Conjunction (∧): In φ₁ ∧ φ₂, variables range-restricted in either φ₁ or φ₂ are range-restricted in the conjunction.
Disjunction (∨): In φ₁ ∨ φ₂, only variables range-restricted in BOTH φ₁ and φ₂ are range-restricted in the disjunction.
Negation (¬): Variables appearing only under negation are NOT range-restricted by the negation.

Tuple Relational Calculus Safety Conditions

For Tuple Relational Calculus (TRC), the safety conditions ensure that tuple variables appearing in the result are always bound to finite sets from the database.

TRC Safety Conditions

•Condition 1 (Free Variable Restriction): Every free tuple variable in the query must appear in at least one positive, non-negated database predicate in the formula.
•Condition 2 (Existential Quantifier Safety): For each subformula (∃t)(ψ), the variable t must appear in at least one positive database predicate within ψ.
•Condition 3 (Universal Quantifier Safety): For each subformula (∀t)(ψ), rewrite as ¬(∃t)(¬ψ) and verify the existential form satisfies Condition 2. Alternatively: if ψ has form (φ → θ), then t must appear positively in φ.
•Condition 4 (Disjunction Safety): For each disjunction (ψ₁ ∨ ψ₂), every free variable of the disjunction must be range-restricted in BOTH ψ₁ AND ψ₂.
•Condition 5 (Implication Safety): For (ψ → θ), universally quantified variables must appear positively in ψ (the antecedent).

TRC Safety Verification Examples

Analysis

-- Example 1: {t | Employee(t) ∧ t.salary > 50000}
--
-- Free variable: t
-- Does t appear in positive predicate? Employee(t) ✓
-- Verdict: SAFE ✓
 
 
-- Example 2: {t | ¬Employee(t)}
--
-- Free variable: t
-- Does t appear in positive predicate? NO (only in negation)
-- Verdict: UNSAFE ✗
 
 
-- Example 3: {t | Employee(t) ∧ (∃d)(Department(d) ∧ t.dept = d.name)}
--
-- Free variable: t
-- Positive predicate for t? Employee(t) ✓
-- Existential variable: d
-- Positive predicate for d in scope? Department(d) ✓  
-- Verdict: SAFE ✓
 
 
-- Example 4: {t | Employee(t) ∧ (∀d)(Department(d) → Works_In(t, d.name))}
--
-- Free variable: t → Employee(t) ✓
-- Universal variable: d
-- Rewrite: ¬(∃d)(Department(d) ∧ ¬Works_In(t, d.name))
-- In ∃ scope: d appears in Department(d) ✓
-- Verdict: SAFE ✓
 
 
-- Example 5: {t | Employee(t) ∨ t.name = 'Unknown'}
--
-- Free variable: t
-- Disjunction: Employee(t) | t.name = 'Unknown'
-- Is t range-restricted in Employee(t)? Yes
-- Is t range-restricted in t.name = 'Unknown'? NO (no relation binds t)
-- Verdict: UNSAFE ✗ (Condition 4 violated)

The Universal Quantifier Trick

For universal quantifiers (∀t)(φ → θ), the safety requirement is that t appears positively in φ. Intuitively, the implication 'for all t, if φ(t) then θ(t)' only needs to check those t satisfying φ. If φ bounds t to database values, the universal is safe.

Domain Relational Calculus Safety Conditions

Domain Relational Calculus (DRC) uses domain variables instead of tuple variables. The safety conditions are analogous but apply to individual domain variables.

DRC Safety Conditions

•Condition 1 (Free Variables): Every free domain variable in the result expression must appear in at least one positive relational atom.
•Condition 2 (Existential Safety): For (∃x)(ψ), x must appear in a positive relational atom within ψ, or be equated to a variable that does.
•Condition 3 (Universal Safety): For (∀x)(ψ), convert to ¬(∃x)(¬ψ) and check existential safety, OR if ψ = (φ → θ), verify x appears positively in φ.
•Condition 4 (Disjunction): In (ψ₁ ∨ ψ₂), every free variable must appear in positive atoms in BOTH disjuncts.
•Condition 5 (Constant Comparison): Comparisons with constants (x = c) alone don't provide range restriction without accompanying relational atoms.

DRC Safety Verification Examples

Analysis

-- Example 1: {<x, y> | Employee(x, y)}
--
-- Free variables: x, y
-- Both appear in Employee(x, y) ✓
-- Verdict: SAFE ✓
 
 
-- Example 2: {<x> | ¬Employee(x, y)}
--
-- Free variable: x
-- Does x appear in positive atom? NO 
-- (Employee appears negated)
-- Verdict: UNSAFE ✗
 
 
-- Example 3: {<x> | (∃y)(Employee(x, y) ∧ y = 'Sales')}
--
-- Free variable: x
-- x appears in Employee(x, y) ✓
-- Existential y: appears in Employee(x, y) ✓
-- Verdict: SAFE ✓
 
 
-- Example 4: {<x, y> | Employee(x, z) ∧ z = y}
--
-- Free variables: x, y
-- x appears in Employee(x, z) ✓
-- y: equals z, and z appears in Employee(x, z) ✓
-- Verdict: SAFE ✓ (equality propagates restriction)
 
 
-- Example 5: {<x> | x > 100}
--
-- Free variable: x
-- x appears only in comparison, not in relational atom
-- No database predicate restricts x
-- Verdict: UNSAFE ✗
 
 
-- Example 6: {<x> | R(x) ∧ x > 100}  
--
-- Free variable: x
-- x appears in R(x) ✓ (then filtered by condition)
-- Verdict: SAFE ✓

DRC vs TRC Subtlety

In DRC, each attribute position is a separate domain variable. A query {<x, y> | R(x) ∧ S(y)} might seem safe at first glance, but if within a disjunction, each must be independently restricted in both branches. Pay careful attention to variable scoping.

Systematic Safety Verification

Let's formalize the safety verification process into a systematic algorithm. This provides a mechanical procedure for checking any TRC expression.

Safety Verification Algorithm

Pseudocode

function isSafe(query Q = {t | φ(t)}):
    -- Step 1: Identify all free variables
    freeVars = extractFreeVariables(φ)
    
    -- Step 2: For each free variable, verify range restriction
    for each var v in freeVars:
        if not isRangeRestricted(v, φ):
            return UNSAFE
    
    -- Step 3: Recursively verify subformulas
    return isFormulaSafe(φ)
 
 
function isRangeRestricted(var v, formula φ):
    case φ of:
        R(t):                    -- Base relation
            return (v occurs in t)
            
        ¬ψ:                      -- Negation
            return false         -- Negation alone doesn't restrict
            
        ψ₁ ∧ ψ₂:                 -- Conjunction
            return isRangeRestricted(v, ψ₁) OR isRangeRestricted(v, ψ₂)
            
        ψ₁ ∨ ψ₂:                 -- Disjunction  
            return isRangeRestricted(v, ψ₁) AND isRangeRestricted(v, ψ₂)
            
        x = y:                   -- Equality
            if v = x and isRangeRestricted(y, context):
                return true
            if v = y and isRangeRestricted(x, context):
                return true
            return false
            
        x = c:                   -- Constant comparison
            return false         -- Constants don't provide range
 
 
function isFormulaSafe(formula φ):
    case φ of:
        R(t):
            return SAFE
            
        ¬ψ:
            return isFormulaSafe(ψ)
            
        ψ₁ ∧ ψ₂:
            return isFormulaSafe(ψ₁) AND isFormulaSafe(ψ₂)
            
        ψ₁ ∨ ψ₂:
            -- Verify all free vars are restricted in BOTH
            for each v in freeVariables(ψ₁ ∨ ψ₂):
                if not (isRangeRestricted(v, ψ₁) AND isRangeRestricted(v, ψ₂)):
                    return UNSAFE
            return isFormulaSafe(ψ₁) AND isFormulaSafe(ψ₂)
            
        (∃t)(ψ):
            if not isRangeRestricted(t, ψ):
                return UNSAFE
            return isFormulaSafe(ψ)
            
        (∀t)(ψ):
            -- Rewrite as ¬(∃t)(¬ψ) and check
            -- OR if ψ = (φ₁ → φ₂), verify t is restricted in φ₁
            return isFormulaSafe(transformed_formula)

Algorithm Properties:

Soundness: If the algorithm returns SAFE, the query is definitely safe.
Completeness (limited): Some safe queries may be flagged as potentially unsafe. This is acceptable—we prefer false negatives to false positives.
Complexity: The algorithm runs in polynomial time with respect to formula size—much faster than attempting to evaluate the query.
Decidability: Unlike semantic safety checking, this syntactic algorithm always terminates.

Common Patterns and Pitfalls

Let's examine common query patterns and understand why they pass or fail safety conditions.

Safe Query Patterns

TRC

-- PATTERN 1: Simple Selection
-- "Employees in Engineering"
{t | Employee(t) ∧ t.dept = 'Engineering'}
-- Safe: t bound by Employee ✓
 
 
-- PATTERN 2: Join with Selection
-- "Employees and their departments"
{t | (∃e)(∃d)(Employee(e) ∧ Department(d) ∧ 
              e.dept_id = d.id ∧ t = <e.name, d.name>)}
-- Safe: e, d bound by relations; t composed from them ✓
 
 
-- PATTERN 3: Negation with Positive Guard
-- "Employees not in Sales"  
{t | Employee(t) ∧ ¬(t.dept = 'Sales')}
-- Safe: t bound by Employee, then filtered ✓
 
 
-- PATTERN 4: NOT EXISTS (Anti-Join)
-- "Employees with no projects"
{t | Employee(t) ∧ ¬(∃p)(Project(p) ∧ p.emp_id = t.id)}
-- Safe: t bound by Employee ✓
-- The ∃p is inside negation, and p is bound by Project ✓
 
 
-- PATTERN 5: Universal with Implication
-- "Managers managing all departments"
{t | Manager(t) ∧ (∀d)(Department(d) → Manages(t.id, d.id))}
-- Safe: t bound by Manager ✓
-- Universal d: appears in Department(d) in antecedent ✓
 
 
-- PATTERN 6: Double Negation (Division-like)
-- "Students enrolled in all courses"
{s | Student(s) ∧ ¬(∃c)(Course(c) ∧ ¬Enrolled(s.id, c.id))}
-- Safe: s bound by Student ✓
-- Inner ∃c: c bound by Course ✓

Safety Conditions and SQL Design

SQL was deliberately designed so that its syntax enforces safety conditions automatically. Understanding this connection illuminates both SQL's design and why certain queries that seem natural in calculus are awkward in SQL.

How SQL Enforces Safety:

FROM Clause Requirement: Every SELECT must specify source tables. Variables (aliases) are always bound to table contents—satisfying the positive binding requirement.
Column References: You can only reference columns from tables in the FROM clause. This prevents free variables from appearing without bindings.
Subquery Correlation: Subqueries access outer query columns through explicit correlation. The outer variable is already bound.
NOT EXISTS Pattern: SQL's way to express negation. The correlated subquery checks for absence within a bounded context.
EXCEPT/MINUS: Set difference operates on explicit result sets, not against an infinite domain.

Unsafe Calculus

TRC

-- Cannot be expressed in SQL:
 
-- "All non-employees"
{t | ¬Employee(t)}
 
-- "All values not in R"  
{x | ¬R(x)}
 
-- "Any x where there exists 
-- no y such that..."
{x | ¬(∃y)(P(x,y))}
-- (when x has no positive source)

Safe SQL Equivalents
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
-- Requires defining the universe:
 
-- "People who aren't employees"
SELECT * FROM Person p
WHERE p.id NOT IN 
  (SELECT e.id FROM Employee e);
 
-- "Values in S but not R"
SELECT x FROM S
EXCEPT
SELECT x FROM R;
 
-- "x where no matching y exists"
SELECT x FROM Source s
WHERE NOT EXISTS (
  SELECT 1 FROM Other o 
  WHERE condition(s.x, o.y)
);

The Key Insight

Every SQL query implicitly satisfies safety conditions because the FROM clause establishes positive bindings for all referenced tables, and all column references must trace back to these sources. You cannot accidentally write an unsafe query in standard SQL.

Summary: Safety Conditions

Safety conditions provide a mechanical, syntactic test for determining whether a relational calculus query is safe—without needing to evaluate it.

Key Takeaways

•Safety conditions are sufficient, not necessary — Passing the test guarantees safety; failing doesn't prove unsafety.
•Range restriction is the core concept — Variables must be bound to database relations, not the infinite domain.
•Conjunction propagates restriction — If a variable is restricted in one conjunct, it's restricted in the conjunction.
•Disjunction requires both branches — Variables must be independently restricted in every disjunct.
•Quantifiers need guards — Existential and universal variables must be bound within their scope.
•SQL enforces safety by design — The FROM clause syntax makes unsafe queries syntactically impossible.

What's Next:

We've established the syntactic rules for safety. Next, we'll explore the finite result guarantee—the fundamental theorem that connects safety conditions to the assurance that query evaluation will terminate with a finite result.

Page Complete

You can now verify whether relational calculus expressions satisfy safety conditions. This practical skill enables you to analyze query well-formedness and understand why certain calculus expressions cannot be translated to SQL.

3 / 5

Loading learning content...

Relational CalculusSafe Queries

Safe Queries in Relational Calculus

LevelIntermediate

Duration60 mins

TopicSafe Queries

3 / 5

Safety Conditions

A Practical Test for Query Well-Formedness

What You Will Learn

The Need for Syntactic Conditions

However, we can define sufficient conditions:

Sufficient vs. Necessary Conditions

Why Syntactic Conditions Work:

The Three-Step Verification:

Identify all free variables (those appearing in the result)
For each free variable, verify it is constrained by positive database predicates
For quantified subformulas, verify bound variables are appropriately restricted

Range-Restricted Variables

Formal Definition

A variable x is range-restricted in a formula φ if, for any database instance I and underlying domain D ⊇ adom(I), the possible values of x that can satisfy φ are contained in adom(I).

Examples of Range-Restricted Variables:

Range Restriction Examples
Formula	Variable	Range-Restricted?	Reason
R(x)	x	✓ Yes	x must be in relation R
R(x) ∧ S(y)	x, y	✓ Yes	Both bound to database relations
R(x) ∧ x = y	x, y	✓ Yes	y equals x, which is in R
¬R(x)	x	✗ No	x can be any value NOT in R
x = 5	x	✗ No	No database predicate binds x
R(x) ∨ S(y)	x, y	✗ No	Each var may not be bound
R(x) ∧ ¬S(y)	x, y	x:Yes, y:No	x is bound, y is not

The Propagation Rules:

Range restriction propagates through formulas according to specific rules:

Base case: If R(x₁, ..., xₙ) appears positively, all xᵢ are range-restricted by R.
Equality: If x is range-restricted and x = y appears, then y is also range-restricted.
Conjunction (∧): In φ₁ ∧ φ₂, variables range-restricted in either φ₁ or φ₂ are range-restricted in the conjunction.
Disjunction (∨): In φ₁ ∨ φ₂, only variables range-restricted in BOTH φ₁ and φ₂ are range-restricted in the disjunction.
Negation (¬): Variables appearing only under negation are NOT range-restricted by the negation.

Tuple Relational Calculus Safety Conditions

For Tuple Relational Calculus (TRC), the safety conditions ensure that tuple variables appearing in the result are always bound to finite sets from the database.

TRC Safety Conditions

•Condition 1 (Free Variable Restriction): Every free tuple variable in the query must appear in at least one positive, non-negated database predicate in the formula.
•Condition 2 (Existential Quantifier Safety): For each subformula (∃t)(ψ), the variable t must appear in at least one positive database predicate within ψ.
•Condition 3 (Universal Quantifier Safety): For each subformula (∀t)(ψ), rewrite as ¬(∃t)(¬ψ) and verify the existential form satisfies Condition 2. Alternatively: if ψ has form (φ → θ), then t must appear positively in φ.
•Condition 4 (Disjunction Safety): For each disjunction (ψ₁ ∨ ψ₂), every free variable of the disjunction must be range-restricted in BOTH ψ₁ AND ψ₂.
•Condition 5 (Implication Safety): For (ψ → θ), universally quantified variables must appear positively in ψ (the antecedent).

TRC Safety Verification Examples

Analysis

-- Example 1: {t | Employee(t) ∧ t.salary > 50000}
--
-- Free variable: t
-- Does t appear in positive predicate? Employee(t) ✓
-- Verdict: SAFE ✓
 
 
-- Example 2: {t | ¬Employee(t)}
--
-- Free variable: t
-- Does t appear in positive predicate? NO (only in negation)
-- Verdict: UNSAFE ✗
 
 
-- Example 3: {t | Employee(t) ∧ (∃d)(Department(d) ∧ t.dept = d.name)}
--
-- Free variable: t
-- Positive predicate for t? Employee(t) ✓
-- Existential variable: d
-- Positive predicate for d in scope? Department(d) ✓  
-- Verdict: SAFE ✓
 
 
-- Example 4: {t | Employee(t) ∧ (∀d)(Department(d) → Works_In(t, d.name))}
--
-- Free variable: t → Employee(t) ✓
-- Universal variable: d
-- Rewrite: ¬(∃d)(Department(d) ∧ ¬Works_In(t, d.name))
-- In ∃ scope: d appears in Department(d) ✓
-- Verdict: SAFE ✓
 
 
-- Example 5: {t | Employee(t) ∨ t.name = 'Unknown'}
--
-- Free variable: t
-- Disjunction: Employee(t) | t.name = 'Unknown'
-- Is t range-restricted in Employee(t)? Yes
-- Is t range-restricted in t.name = 'Unknown'? NO (no relation binds t)
-- Verdict: UNSAFE ✗ (Condition 4 violated)

The Universal Quantifier Trick

Domain Relational Calculus Safety Conditions

Domain Relational Calculus (DRC) uses domain variables instead of tuple variables. The safety conditions are analogous but apply to individual domain variables.

DRC Safety Conditions

•Condition 1 (Free Variables): Every free domain variable in the result expression must appear in at least one positive relational atom.
•Condition 2 (Existential Safety): For (∃x)(ψ), x must appear in a positive relational atom within ψ, or be equated to a variable that does.
•Condition 3 (Universal Safety): For (∀x)(ψ), convert to ¬(∃x)(¬ψ) and check existential safety, OR if ψ = (φ → θ), verify x appears positively in φ.
•Condition 4 (Disjunction): In (ψ₁ ∨ ψ₂), every free variable must appear in positive atoms in BOTH disjuncts.
•Condition 5 (Constant Comparison): Comparisons with constants (x = c) alone don't provide range restriction without accompanying relational atoms.

DRC Safety Verification Examples

Analysis

-- Example 1: {<x, y> | Employee(x, y)}
--
-- Free variables: x, y
-- Both appear in Employee(x, y) ✓
-- Verdict: SAFE ✓
 
 
-- Example 2: {<x> | ¬Employee(x, y)}
--
-- Free variable: x
-- Does x appear in positive atom? NO 
-- (Employee appears negated)
-- Verdict: UNSAFE ✗
 
 
-- Example 3: {<x> | (∃y)(Employee(x, y) ∧ y = 'Sales')}
--
-- Free variable: x
-- x appears in Employee(x, y) ✓
-- Existential y: appears in Employee(x, y) ✓
-- Verdict: SAFE ✓
 
 
-- Example 4: {<x, y> | Employee(x, z) ∧ z = y}
--
-- Free variables: x, y
-- x appears in Employee(x, z) ✓
-- y: equals z, and z appears in Employee(x, z) ✓
-- Verdict: SAFE ✓ (equality propagates restriction)
 
 
-- Example 5: {<x> | x > 100}
--
-- Free variable: x
-- x appears only in comparison, not in relational atom
-- No database predicate restricts x
-- Verdict: UNSAFE ✗
 
 
-- Example 6: {<x> | R(x) ∧ x > 100}  
--
-- Free variable: x
-- x appears in R(x) ✓ (then filtered by condition)
-- Verdict: SAFE ✓

DRC vs TRC Subtlety

Systematic Safety Verification

Let's formalize the safety verification process into a systematic algorithm. This provides a mechanical procedure for checking any TRC expression.

Safety Verification Algorithm

Pseudocode

function isSafe(query Q = {t | φ(t)}):
    -- Step 1: Identify all free variables
    freeVars = extractFreeVariables(φ)
    
    -- Step 2: For each free variable, verify range restriction
    for each var v in freeVars:
        if not isRangeRestricted(v, φ):
            return UNSAFE
    
    -- Step 3: Recursively verify subformulas
    return isFormulaSafe(φ)
 
 
function isRangeRestricted(var v, formula φ):
    case φ of:
        R(t):                    -- Base relation
            return (v occurs in t)
            
        ¬ψ:                      -- Negation
            return false         -- Negation alone doesn't restrict
            
        ψ₁ ∧ ψ₂:                 -- Conjunction
            return isRangeRestricted(v, ψ₁) OR isRangeRestricted(v, ψ₂)
            
        ψ₁ ∨ ψ₂:                 -- Disjunction  
            return isRangeRestricted(v, ψ₁) AND isRangeRestricted(v, ψ₂)
            
        x = y:                   -- Equality
            if v = x and isRangeRestricted(y, context):
                return true
            if v = y and isRangeRestricted(x, context):
                return true
            return false
            
        x = c:                   -- Constant comparison
            return false         -- Constants don't provide range
 
 
function isFormulaSafe(formula φ):
    case φ of:
        R(t):
            return SAFE
            
        ¬ψ:
            return isFormulaSafe(ψ)
            
        ψ₁ ∧ ψ₂:
            return isFormulaSafe(ψ₁) AND isFormulaSafe(ψ₂)
            
        ψ₁ ∨ ψ₂:
            -- Verify all free vars are restricted in BOTH
            for each v in freeVariables(ψ₁ ∨ ψ₂):
                if not (isRangeRestricted(v, ψ₁) AND isRangeRestricted(v, ψ₂)):
                    return UNSAFE
            return isFormulaSafe(ψ₁) AND isFormulaSafe(ψ₂)
            
        (∃t)(ψ):
            if not isRangeRestricted(t, ψ):
                return UNSAFE
            return isFormulaSafe(ψ)
            
        (∀t)(ψ):
            -- Rewrite as ¬(∃t)(¬ψ) and check
            -- OR if ψ = (φ₁ → φ₂), verify t is restricted in φ₁
            return isFormulaSafe(transformed_formula)

Algorithm Properties:

Soundness: If the algorithm returns SAFE, the query is definitely safe.
Completeness (limited): Some safe queries may be flagged as potentially unsafe. This is acceptable—we prefer false negatives to false positives.
Complexity: The algorithm runs in polynomial time with respect to formula size—much faster than attempting to evaluate the query.
Decidability: Unlike semantic safety checking, this syntactic algorithm always terminates.

Common Patterns and Pitfalls

Let's examine common query patterns and understand why they pass or fail safety conditions.

Safe Query Patterns

TRC

-- PATTERN 1: Simple Selection
-- "Employees in Engineering"
{t | Employee(t) ∧ t.dept = 'Engineering'}
-- Safe: t bound by Employee ✓
 
 
-- PATTERN 2: Join with Selection
-- "Employees and their departments"
{t | (∃e)(∃d)(Employee(e) ∧ Department(d) ∧ 
              e.dept_id = d.id ∧ t = <e.name, d.name>)}
-- Safe: e, d bound by relations; t composed from them ✓
 
 
-- PATTERN 3: Negation with Positive Guard
-- "Employees not in Sales"  
{t | Employee(t) ∧ ¬(t.dept = 'Sales')}
-- Safe: t bound by Employee, then filtered ✓
 
 
-- PATTERN 4: NOT EXISTS (Anti-Join)
-- "Employees with no projects"
{t | Employee(t) ∧ ¬(∃p)(Project(p) ∧ p.emp_id = t.id)}
-- Safe: t bound by Employee ✓
-- The ∃p is inside negation, and p is bound by Project ✓
 
 
-- PATTERN 5: Universal with Implication
-- "Managers managing all departments"
{t | Manager(t) ∧ (∀d)(Department(d) → Manages(t.id, d.id))}
-- Safe: t bound by Manager ✓
-- Universal d: appears in Department(d) in antecedent ✓
 
 
-- PATTERN 6: Double Negation (Division-like)
-- "Students enrolled in all courses"
{s | Student(s) ∧ ¬(∃c)(Course(c) ∧ ¬Enrolled(s.id, c.id))}
-- Safe: s bound by Student ✓
-- Inner ∃c: c bound by Course ✓

Safety Conditions and SQL Design

How SQL Enforces Safety:

FROM Clause Requirement: Every SELECT must specify source tables. Variables (aliases) are always bound to table contents—satisfying the positive binding requirement.
Column References: You can only reference columns from tables in the FROM clause. This prevents free variables from appearing without bindings.
Subquery Correlation: Subqueries access outer query columns through explicit correlation. The outer variable is already bound.
NOT EXISTS Pattern: SQL's way to express negation. The correlated subquery checks for absence within a bounded context.
EXCEPT/MINUS: Set difference operates on explicit result sets, not against an infinite domain.

Unsafe Calculus

TRC

-- Cannot be expressed in SQL:
 
-- "All non-employees"
{t | ¬Employee(t)}
 
-- "All values not in R"  
{x | ¬R(x)}
 
-- "Any x where there exists 
-- no y such that..."
{x | ¬(∃y)(P(x,y))}
-- (when x has no positive source)

Safe SQL Equivalents
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
-- Requires defining the universe:
 
-- "People who aren't employees"
SELECT * FROM Person p
WHERE p.id NOT IN 
  (SELECT e.id FROM Employee e);
 
-- "Values in S but not R"
SELECT x FROM S
EXCEPT
SELECT x FROM R;
 
-- "x where no matching y exists"
SELECT x FROM Source s
WHERE NOT EXISTS (
  SELECT 1 FROM Other o 
  WHERE condition(s.x, o.y)
);

The Key Insight

Summary: Safety Conditions

Safety conditions provide a mechanical, syntactic test for determining whether a relational calculus query is safe—without needing to evaluate it.

Key Takeaways

•Safety conditions are sufficient, not necessary — Passing the test guarantees safety; failing doesn't prove unsafety.
•Range restriction is the core concept — Variables must be bound to database relations, not the infinite domain.
•Conjunction propagates restriction — If a variable is restricted in one conjunct, it's restricted in the conjunction.
•Disjunction requires both branches — Variables must be independently restricted in every disjunct.
•Quantifiers need guards — Existential and universal variables must be bound within their scope.
•SQL enforces safety by design — The FROM clause syntax makes unsafe queries syntactically impossible.

What's Next:

Page Complete

3 / 5