DBMS & SQL›Level 5
PART 1 • FORMAL QUERY LANGUAGE

Build Queries by Transforming Relations Step by Step

Use a small set of precise operators to express what data is required, then trace every intermediate relation instead of guessing the final answer.

Level 05 of 18Foundation100–130 minutesLevel 4 recommended
BY THE END, YOU CAN
  • Classify unary and binary operators.
  • Execute selection and projection.
  • Check union compatibility.
  • Trace products and joins.
  • Explain relational division.
  • Read and construct query trees.
01 • UNDERSTAND THE ALGEBRA

Every Operator Accepts Relations and Produces a Relation

This closure property lets us connect operations into larger expressions.

Input relation(s)→Relational operator→Result relation→ can become another input
PROCEDURAL

It describes how to obtain the result

An expression specifies an ordered combination of operations, unlike a purely declarative request.

SET ORIENTED

It transforms whole relations

The basic unit is not one record at a time; an operator consumes and returns sets of tuples.

FORMAL FOUNDATION

It supports reasoning and optimization

Equivalent expressions allow a DBMS to choose a cheaper execution strategy.

UNARY — ONE INPUTσ Selectionπ Projectionρ Rename
BINARY — TWO INPUTS∪ Union− Difference× Product⋈ Join÷ Division
02 • FILTER, SHAPE AND NAME

Unary Operators Change One Relation

σ

Selection — choose rows

σbranch='AIML' ∧ cgpa≥8(STUDENT)

Keeps the same attributes but returns only tuples satisfying the predicate. It is a horizontal subset.

π

Projection — choose columns

πstudent_id,name(STUDENT)

Keeps selected attributes. Duplicate result tuples are removed under mathematical set semantics. It is a vertical subset.

ρ

Rename — remove ambiguity

ρS(sid,sname,branch,cgpa)(STUDENT)

Renames a relation and/or its attributes, especially before self-joins or when combining similar schemas.

03 • APPLY SET OPERATIONS

Union, Intersection and Difference Need Compatible Relations

UNION COMPATIBLE WHEN

Same degree + corresponding compatible domains

Attribute names may be aligned by renaming. Position and meaning must correspond.

CS_STUDENT(sid, name)AIML_STUDENT(sid, name)✓ CompatibleCOURSE(code, credits, title)✕ Different degree
R ∪ S

Union

Tuples found in R, S or both. Duplicates appear once.

R ∩ S

Intersection

Tuples found in both compatible relations. It can be derived from difference.

R − S

Difference

Tuples in R but not S. Direction matters: R − S generally differs from S − R.

04 • COMBINE RELATED DATA

A Join Is a Controlled Combination

CARTESIAN PRODUCT

R × S pairs every tuple of R with every tuple of S

If R has m tuples and S has n tuples, the product has m × n tuples and degree degree(R) + degree(S).

3 students × 4 courses = 12 pairs
θ JOIN

R ⋈condition S

Product followed by selection using any comparison condition.

EQUIJOIN

Equality-based θ join

Matches equal values but can retain both join attributes.

NATURAL JOIN

R ⋈ S

Matches equally named compatible attributes and keeps one copy of them.

OUTER JOIN

Preserves unmatched tuples

Left, right and full variants use NULLs for missing partner attributes.

SEMIJOIN

Return matching tuples from one side

Useful when only one relation's attributes are required.

SELF-JOIN

Join a relation with a renamed copy

Models relationships such as employee supervises employee.

STUDENT ⋈STUDENT.student_id = ENROLMENT.student_id ENROLMENT

Only student–enrolment pairs satisfying the ID equality survive. This avoids the unrelated pairs produced by the full Cartesian product.

05 • EXPRESS “FOR ALL”

Division Finds Values Related to Every Required Value

ENROLMENT(student, course)
AnuDBMS
AnuC
BharatDBMS
CharanDBMS
CharanC
CharanPython
÷
REQUIRED(course)
DBMS
C
=
RESULT(student)
Anu
Charan

Anu and Charan appear because each is related to every course in REQUIRED. Bharat is excluded because C is missing. Division is the classic operator for “all required skills,” “all compulsory courses” or “all supplied parts.”

06 • EXECUTE OPERATIONS

Interactive Relational Operation Visualizer

Choose an operation and inspect the input, expression, output schema and result tuples.

07 • TRACE COMPLETE EXPRESSIONS

Query-Tree Visualizer

Select a natural-language question. Read the tree from its leaves upward.

RELATIONAL ALGEBRA EXPRESSION
QUERY TREE
08 • REASON ABOUT EQUIVALENT EXPRESSIONS

Push Selective Work Down the Tree

ORIGINALσbranch='AIML'(STUDENT ⋈ ENROLMENT)

Join all matching rows, then discard non-AIML results.

≡
OFTEN CHEAPER(σbranch='AIML'(STUDENT)) ⋈ ENROLMENT

Reduce STUDENT first, so the join processes fewer tuples.

Cascade selections

σc1∧c2(R) ≡ σc1(σc2(R))

Selection commutes

σc1(σc2(R)) ≡ σc2(σc1(R))

Join commutes

R ⋈ S ≡ S ⋈ R

Join associates

(R ⋈ S) ⋈ T ≡ R ⋈ (S ⋈ T)
09 • CHECK YOUR UNDERSTANDING

Seven Formative Concept Checks

1. Which operator selects rows?

2. Projection primarily chooses:

3. Union compatibility requires:

4. If |R|=5 and |S|=4, then |R × S| is:

5. Which operator naturally expresses “completed every required course”?

6. A natural join normally removes:

7. A query tree is normally evaluated:

Answered correctly: 0 of 7
10 • EXPLAIN & PREPARE

University and Interview Questions

2-MARK QUESTIONS
  1. State the closure property.
  2. Define selection and projection.
  3. What is union compatibility?
  4. Define natural join.
  5. What type of query uses division?
5-MARK QUESTIONS
  1. Explain fundamental relational algebra operators.
  2. Compare product, theta join and natural join.
  3. Explain division with an example.
  4. Draw a query tree for a selection–join–projection expression.
INTERVIEW / PROBLEM SOLVING
  1. Why push selection below a join?
  2. Difference between SQL SELECT and algebraic selection?
  3. Can R − S equal S − R?
  4. How do you find students with no enrolment?
  5. How is intersection derived using difference?
Show the expression-solving method
  1. Write the output attributes requested by the question.
  2. Identify the relations containing those attributes.
  3. Add join conditions that connect the relations.
  4. Add selections for row conditions.
  5. Project the final required attributes.
  6. For “none,” consider difference; for “all,” consider division.
  7. Trace intermediate schemas and tuples from inside outward.
LEVEL 5 SUMMARY • PART 1 COMPLETE

You Can Now Express and Trace Formal Queries

  • Closure allows relational operations to be composed.
  • Selection filters tuples, projection chooses attributes and rename resolves naming.
  • Set operations require compatible relation schemas.
  • Product creates every pair; joins retain meaningful combinations.
  • Division expresses “related to all required values.”
  • Query trees reveal execution order and optimization opportunities.
COURSE CHECKPOINT

Mark this level when you can write, trace and explain multi-operator expressions without guessing.

Saved in this browser only.