Relational Algebra: Select, Project, and Joins

7.1 Why Relational Algebra Exists

7.1.1 Data at the Heart of Every Application

This session is practical, and it starts from the premise of technology itself. As computer science students we want to influence people and add value to their lives. In person, one person can help a limited number of others. With the power of technology, one person can influence, impact, and add value to an order of magnitude more people — that is the entire premise of the subject. The applications we build come in many shapes: desktop applications, mobile applications, enterprise applications, and so on. In every one of them, data plays a central role in the heart of the application, whether the app directly solves a problem or simply delivers a personalized user experience.

Real-world: think of supply chains, railways, airlines, banking applications, agriculture, automobiles, or edtech — every one of them runs on data. An application is a complete architecture: there are microservices and APIs, many languages, test cases, a front end with a visual experience, something to be deployed somewhere, and integration between front end, back end, services, and APIs. The database is one particular component inside that architecture, and it has its own role to play.

7.1.2 From a Good Schema to a Language for Retrieval

Before we touch any symbols, fix the three words that describe the layers of a database system. A database is primarily the schema and the data together — the blueprint (schema) plus the actual stored rows (data). A database management system (DBMS) is the application that helps us store and retrieve data. The database system is the complete package — the database, the real-time data, and the DBMS applications taken together.

The design journey is already familiar: a user gives a requirement ("this is what I want to create, this is what I want to store"), we create an ER diagram (entity relationship diagram), and we convert it into a basic relational schema. At a basic level, that is good enough — for a startup in its prototype phase that wants to raise money and go commercial, an ER diagram and a relational schema are fine to go ahead with.

Real-world: as soon as we want a commercial-level application that really scales, we need a good database schema. "Good" rests on the four properties discussed earlier: proper semantics (anyone working with the data knows what the database means), least redundancies and anomalies, least null entries, and minimum spurious tuples created. The entire science of normalization — first normal form, second normal form, third normal form, BCNF, 4NF — makes sure there is less and less redundancy, which means fewer and fewer functional dependencies in a relation.

Now the schema is proper, so we need to store data in it and retrieve data from it. That requires a proper language to talk to the data. That science is relational algebra — the mathematics for it — and SQL, the programming part for it.

7.1.3 Why Mathematics, and Why Relational Algebra Specifically

In relational algebra we mathematically represent what the user wants to retrieve. It is not about storage; it is mostly about the retrieval part. Why relational algebra and not just SQL? SQL is the programming part; relational algebra is the mathematical part, and mathematics is the basis of most of computer science, if not all of it.

Relational algebra specifically matters because when we want to optimize SQL queries, ultimately we think about them and use them in a relational algebra manner. Even if many of us will not write relational algebra day to day, the way relational algebra correlates with SQL can be useful in other areas of life — management, sales, or any field where the logic of retrieval applies.

7.1.4 A Vocabulary Warning

7.1.5 The Operator Roadmap

Relational algebra primarily works with these symbols: select, project, rename, union, Cartesian product, intersection, set difference, joins, and division. Besides these, there are aggregation functions such as minimum and maximum, and some outer joins, which we will discuss too.

The session is organized in three stages: information, education, and skill. The handout you already have provides the information — if you know how the symbols work, that is exactly the information being provided. Education follows in the few minutes where we explain how select works, how project works, how rename works. And when you practice from the lab sheets, that adds skill. The instructor takes you from zero level to the next level, and you are asked to participate and practice while the session runs. If you are left behind, or if you have errors you want resolved, type them in the chat box. The prerequisite is that you should not know anything. And those who are well versed in SQL programming are asked to help others — whatever we give, we will get; when we encourage others to learn, we learn heavily as well.

Real-world: when you run a slow SQL query in a production system and the DBA shows you the "execution plan", what you are looking at is a relational algebra expression that the DBMS rewrote and priced. Understanding this topic is exactly what makes those plans readable — and why this science is taught before SQL is written by hand.

7.2 Select

7.2.1 What Select Does

The select operation is a row filter. Think of a sieve held over the table: it lets some rows fall through and keeps the rest out. We start with a relation $R$ — for example, a student relation. The student relation has attributes such as ID and name (it may also have phone number, email ID, and address), and it is populated data: the relation contains many tuples, many entries in row format or record format. Now we want only those tuples in which the ID number is 1234, and we do not want to remove any column. The predicate (the condition) says that ID is equal to 1234:

$${\sigma }_{ID=1234}(\text{Student})$$

The professor's own words: "This particular expression would take a relation from student and result into all the rows which satisfy this particular condition — that ID number is equal to 1234." That is all select does: it keeps rows that satisfy the predicate, and every column stays.

7.2.2 Worked Examples on the Company Schema

For the rest of the session we practice on one particular schema, which we use every time: the employee relation has first name, middle name, last name, and other attributes (including social security number, salary, department number, and supervisor's social security number), and there are other relations such as department, project, dependent, and department locations. The lines in the schema represent the foreign keys.

The thought process for relational algebra and SQL is mostly the same: understand the user's requirement, go back to the relational schema, see which attributes and which relations are involved, realize in English what we want to do, and then express it in relational algebra or in SQL. The way of thinking remains the same; only the expression language changes.

7.2.3 Student Questions and Answers

Real-world: in SQL, the select operation is written as the WHERE clause — SELECT * FROM Employee WHERE Dno = 4 is the SQL spelling of ${\sigma }_{Dno=4}(\text{Employee})$. Every time a banking app shows "your transactions this month" or a railway system filters trains by departure station, some optimizer has translated a WHERE condition into exactly this relational algebra operator.

7.3 Project

7.3.1 What Project Does

The project operation works on the attributes. It is the operation you may already have guessed, the pi symbol $\pi$. We list the attributes we want to reduce the relation to, and the result contains only those attributes:

$${\pi }_{ID}(\text{Student})$$

This expression results in only one attribute — the ID — from the student relation. It may be possible that ID is unique, or it may not be unique; but whatever starts off with this relation ends off with a relation, and everything is unique in a relation. That is a basic property: there is no repetition in the final relation. Project reduces the number of columns; select reduces the number of rows.

7.3.2 Worked Examples

We discussed the other option earlier: project first and select later. Both are expressible. The key property that makes composition possible: whatever we get at the end of this portion is a relation, and just like any other relation, we can apply any operation on it — project, select, or anything else. What we get is a relation, and we apply the project with attributes to it exactly as if it were a plain relation.

7.3.3 Student Questions and Answers

Real-world: every report a business runs is a projection — "give me customer name and order date", "list product and price" — followed by a selection of the rows that qualify. When a dashboard shows a filtered, narrowed table, it is executing a select-then-project chain that an optimizer will later reorder to do the filtering first, for exactly the reason discussed here: fewer rows flowing through is cheaper.

7.4 Rename

7.4.1 Renaming Relations and Attributes

The rename operation has the symbol rho $\rho$. There are three levels of use.

First, we can rename the relation itself. If we want to rename relation $R$ to $S$, we write ${\rho }_S(R)$, and from that point onwards the relation is named $S$ — every further query uses $S$ instead of $R$. For example, if the relation is student and we want to call it persons:

$${\rho }_{\text{persons}}(\text{Student})$$

Second, we can rename the attributes. If the student relation has two attributes, ID number and name, and we want the first one to be called ID number and the second one to be called actual name, we write the new attribute list inside the parentheses with the new relation name:

$${\rho }_{\text{persons(ID number, actual name)}}(\text{Student})$$

From that point onwards these attributes are renamed.

Third, we can capture an expression under a name even without writing $\rho$. When we apply an operation and name the result — result one, result two, result three — we can use that name later in further queries (such as applying a project on the named result). This is quite important when the same relation is applied twice in one expression: renaming lets us refer to the two copies separately.

7.4.2 Student Questions and Answers

Real-world: every SQL query that writes FROM Employee E, Employee M or uses aliases like AS E and AS M is doing a rename — database engines cannot join a table to itself any more than relational algebra can, so the two copies must carry distinct names. Renaming is also the standard trick for making two differently named attributes match before a natural join, which every reporting join in a data warehouse leans on.

7.5 Union, Intersection, and Set Difference

7.5.1 The Compatibility Condition

The union $R\cup S$ requires that $R$ and $S$ be compatible relations: the same number of attributes, the attributes in the same order, and the same domains. For example, if the student relation has two attributes — ID number and name — and the employee relation has two attributes — say employee number and name — and the domains of both are the same and the names of the attributes are the same, then we can take their union. The same compatibility requirement applies to intersection and set difference.

7.5.2 Worked Example: Department-Five Employees or Their Supervisors

The requirement: find all the employees' SSNs who work in department number 5, or the SSNs of the supervisors who work in department number 5. The employee relation stores first name, middle name, last name, social security number, supervisor social security number, salary, and the department in which the employee works.

Someone might ask why we cannot simply project both SSN and Super_ssn in one projection. Because that returns pairs of values (each employee with their supervisor's number), not the single set of "either the employee's own SSN or the supervisor's SSN" that the user asked for — the either-or requirement is exactly what the union expresses. Note also that the attribute names do not matter for the union itself, but when we join later, renaming keeps the names consistent and hygienic, so it is better to rename the supervisor SSN to make it match.

7.5.3 Intersection and Set Difference

Intersection $R\cap S$ keeps only the tuples that are common to both relations. Set difference $R-S$ keeps the tuples that are in the first relation and not in the second.

The professor's analogy: "four minus two means four minus the two in the four, and we get two as the output" — but in a homogeneous set the result looks simple to compute, while in relations the subtraction removes only the shared tuples. Set difference subtracts the elements common to both and keeps only what is left on the first relation's side. Even though it is 4 − 2 = 2 in numbers, the idea here is subtract the things that are common in instructor and student, and get only the output from the student side.

7.5.4 Student Questions and Answers

Real-world: "give me customers who bought product A or product B" is a union in every CRM system; "customers who bought A but not B" is a set difference; "employees who are also managers" is an intersection. SQL spells these as UNION, INTERSECT, and EXCEPT — the same three operators, the same compatibility requirement, and the same duplicate-free results.

7.6 Cartesian Product

7.6.1 Definition and Sizes

The Cartesian product (also called the cross product) is the brute-force way to use two relations: take the first relation and the second relation and join them in every possible combination. If the first relation has three attributes and the second relation has two attributes, and the first has four tuples and the second has five tuples, then:

• The number of attributes in the result is the sum: $3+2=5$.
• The number of tuples is the product: every tuple of the first relation pairs with every tuple of the second, so $4\times 5=20$ tuples.

In general, if relation $R$ has attributes $A_1,A_2,\dots ,A_n$ and relation $S$ has attributes $B_1,B_2,\dots ,B_m$, the result relation has attributes $A_1$ through $A_n$ followed by $B_1$ through $B_m$, and the number of tuples is the multiplication of the two counts — every tuple on the $R$ side combines with every tuple on the $S$ side. That is the basic idea of the cross product.

7.6.2 A Not-So-Meaningful Cross Product

Here is an example that makes little sense, deliberately: we want the cross product of employee names and dependents. Suppose we select all employees of female gender and project their first name, last name, and SSN, and then take the cross product with the dependent relation:

$${\pi }_{\text{Fname, Lname, Ssn}}({\sigma }_{\text{Sex}=\text{’F’}}(\text{Employee}))\times \text{Dependent}$$

Whether it makes sense or not, the cross product works exactly like that — it pairs everything with everything. The cross product is not, by itself, a meaningful relation; it produces a lot of combinations, many of them useless. What we actually want is the join operation, which turns the cross product into something meaningful — and that is the next topic.

Real-world: SQL has a CROSS JOIN that does precisely this, and database engines warn about it because a forgotten join condition silently produces one — the classic cause of queries that return absurdly many rows. When a scheduler pairs every delivery van with every route to find all possible assignments, it is running a Cartesian product and then selecting the feasible pairs.

7.7 Natural Join

7.7.1 Natural Join as a Refined Cross Product

The natural join $\bowtie$ is the meaningful version of the cross product. The professor's verbal recipe: "There is a common attribute, let's say A. I am doing select on R1.A is equal to R2.A on R1 cross R2. Then I am projecting all of the attributes of R1 and all of the attributes of R2 — but the common attribute A only once." Reconstructed:

$$R_1\bowtie R_2={\pi }_{\text{all attributes of }{R}_1,\text{all attributes of }{R}_2\text{ except the common }A}({\sigma }_{R_1.A=R_2.A}(R_1\times R_2))$$

So: take the cross product, keep only the rows where the common attribute matches, and project the common attribute only once while keeping everything else. Whatever is common is matched between the two relations, the values must be equal, and the common attribute appears exactly once in the output. This is the meaningful way to join two different relations without creating spurious tuples or new extra entries.

7.7.2 Worked Example: Students with CGPA above 9

The setup: the student relation has ID number and name; the CGPA relation has ID number and grade. We want the names of the students whose CGPA is more than 9. If we have only the cross product to work with, we build the answer step by step.

The matching behavior: if the CGPA relation has an entry for ID 1234 with CGPA 9.5 and the student relation has ID 1234 for Anand, then only Anand's name results, as the person with more than 9 CGPA. If a CGPA row exists for ID 7895 with CGPA 9.5 but no student carries that ID, the row is excluded — it does not become part of the output. The cross product creates many extra tuples, and that is exactly why the natural join exists: it was designed for this matching purpose. We did one extra step — the special step — of matching the common attribute.

7.7.3 Natural Join on the Company Schema

On the company schema, take the department relation and the employee relation, and join on department number. The common attribute is department number — only one common attribute. The final output takes all the attributes of the department side and all the attributes of the employee side, minus one attribute, because the department number appears only once. How many actual tuples result depends on how many times each department number appears on one side paired with the corresponding tuples on the other side: a department with four employees contributes four joined rows, a department with no employees contributes none.

A natural join works naturally when there is one common attribute, and generally that attribute's name is also the same on both sides, so that the joining is clear. We will not involve inner join or outer join here — those terms belong to the SQL side, so we wait for SQL to come in rather than mixing the words.

7.7.4 Student Questions and Answers

7.7.5 The Manager Question

Here is a very important and exciting question: retrieve the name of the manager of each department. The department relation carries the manager's social security number in the attribute Mgr_ssn (the company-schema convention: Mgr_ssn is a foreign key on the department side that references the Ssn of the employee who manages it). We want the name that belongs to that SSN.

Try it for yourself; we will discuss it next time.

Two more questions from the practice sheet show where the topic is heading. "Retrieve all the supervisors" — if you try it, you will get something very exciting and interesting: there is a limit to relational algebra as well, which the rename-and-join machinery reveals. A supervisor's supervisor is found by joining the employee relation with itself (the self-join that rename enables); but "all supervisors at every level, up and up" would need an unknown number of self-joins — one per level — and no single expression of fixed length can express an arbitrary number of levels. That is a genuine limit of the basic relational algebra. And "retrieve the name of all the employees who work in the research department" — that one needs a join between employee and department on the department number, then a selection on the department name. All of these you can do comfortably and very nicely in relational algebra.

Real-world: joins are the workhorse of every business query — order lines joined to orders, bookings joined to flights, transactions joined to accounts. Every such SQL join is a natural join (or a renamed variant of it), and a database that joins well-indexed tables in milliseconds is doing precisely the match-on-common-value idea above, executed by an optimizer that first reorders the joins to keep intermediate results small.

7.8 The Practice Sheet, MySQL Workbench, and Next Steps

7.8.1 The Practice Sheet and Homework

A practice sheet (RA PDF) sits in the files folder under supplementary reading. You can attempt these questions very comfortably in relational algebra: select the employee tuples whose department number is 4; select employee tuples with salary greater than a given value; retrieve the first, middle, and last name; retrieve the social security number; retrieve the name of the manager of each department (the very important question); retrieve all the supervisors; and retrieve the name of all the employees who work in the research department.

The best part: all the solutions are already there in the shared handout, and the handout is already uploaded. A clever person who wants shortcuts can read the handout, do the questions, and then go back to the practice sheet and actually answer it. Attempt the sheet even if you are not 100% correct — the idea is not to be correct; the idea is to be doing something, practicing, and being there, with a commitment that you want to practice. That is more than enough.

7.8.2 Student Questions and Answers

7.8.3 MySQL Workbench: Setup and First Commands

To practice SQL hands-on, install two things: the MySQL Community Server and MySQL Workbench. Go to your browser, open mysql.com, go to downloads, and download the community server and the workbench. The workbench is the place where we type in the queries; the server is what connects to the database — you need a server to connect to and a workbench to work with, both installed. If you are on a Mac, go to System Settings, find MySQL, and start the server from there.

Once the server is running, open Workbench. There is a query tab — the place where you write the queries, the place where you get the answer for your queries, and the place where you see whether the query is successful or there is an error. The first command lists the databases currently in your system:

SHOW DATABASES;

Select the text and press the run button. To use an existing database, for example the Sakila sample database, write:

USE sakila;

Then you can ask for the tables in this particular database. Lab sheet 0 talks about exactly this: the query space, the query result space, and how to get started. Don't worry if you do not understand anything at all — it will be revised. The plan for the next session is to practice with the lab sheets, starting from lab sheet 0, then lab sheets 1, 2, 3, as far as you want to go. Before the next session, have SQL Workbench installed on your system so that when the instructor practices, you can practice side by side.

7.8.4 Student Questions: Workbench and Lab Access

Real-world: MySQL Community Server and MySQL Workbench are the same open-source stack that powers millions of small and mid-sized web applications — every SHOW DATABASES; and USE sakila; you run on your laptop executes on the same engine family that serves production traffic, so the skills from this lab sheet carry straight into real systems after the course.

7.9 Domain Relational Calculus (DRC)

7.9.1 From Procedural to Declarative

Relational algebra is procedural: a query says step by step how to compute the answer — select these rows, project those columns, join these two tables. The relational calculus is the declarative alternative: a query says what the answer is, and the system figures out how to compute it. SQL, the practical query language, is closer in spirit to the calculus than to the algebra, and the syllabus specifically names the domain calculus variant, so this supplement develops it fully.

There are two dialects of relational calculus. The tuple relational calculus (TRC) uses variables that range over whole tuples — a variable stands for a complete row of a relation. The domain relational calculus (DRC) uses variables that range over domains — individual attribute values — so a row is described by a collection of single-value variables, one per attribute. Historically, DRC underlies the QBE (Query-By-Example) language developed at IBM Research: a user sketches a table with example values, and the system translates the sketch into a domain calculus expression.

7.9.2 The Shape of a DRC Query

A DRC query is written as a set comprehension:

$$\{⟨x_1,x_2,\dots ,x_n⟩\mid P(x_1,x_2,\dots ,x_n)\}$$

The answer is the set of all combinations of domain values $⟨x_1,x_2,\dots ,x_n⟩$ that make the predicate $P$ true. The predicate is built from two kinds of atoms, combined with $\wedge$ (and), $\vee$ (or), $\neg$ (not), and the two quantifiers:

• Membership atom: $⟨x_1,x_2,\dots ,x_k⟩\in R$ — the values $x_1,\dots ,x_k$ form a tuple of relation $R$. This is the DRC way of saying "there is a row of $R$ with these values."
• Comparison atom: $x\text{op}y$ or $x\text{op}c$, where $\text{op}$ is $=,\ne ,<,\le ,>,\ge$, $x$ and $y$ are domain variables, and $c$ is a constant — e.g., salary > 30000.

To work the examples, fix a small schema in the style of the course: $\text{EMP}(\text{ssn},\text{ename},\text{salary},\text{dno})$ and $\text{DEPT}(\text{dno},\text{dname})$.

7.9.3 Quantifiers: Existential and Universal

The existential quantifier $\exists$ ("there exists") and the universal quantifier $\forall$ ("for all") bind variables in a predicate, and a variable that is not bound by any quantifier is a free variable — the free variables are exactly the ones that appear in the answer list $⟨x_1,\dots ,x_n⟩$. For readability, a quantified variable that ranges over a relation is often written in the quantified form $\exists ⟨x_1,\dots ,x_k⟩\in R$.

• $\exists$: the formula is TRUE if at least one assignment of values to the bound variables makes it TRUE. This is the DRC spelling of "some row exists that ...".
• $\forall$: the formula is TRUE if every possible assignment makes it TRUE. This is the DRC spelling of "for all rows, ...".

A universal claim about the interesting rows is almost always written as an implication: "for all rows $x$: if $x$ is in department 5, then $e$'s salary is larger". In logic, the implication $P\to Q$ is equivalent to $\neg P\vee Q$ — so the DRC form becomes $\forall x(\neg P(x)\vee Q(x))$. The trick matters: the universal quantifier ranges over everything, so every row that is not in the group we care about must be made harmless by making the clause true for it automatically.

7.9.4 Worked Examples

7.9.5 Safety and Relational Completeness

Two facts to hold onto for the exam: first, every query expressible in relational algebra is expressible in DRC (and vice versa) — Codd's equivalence result — but the safe-expression condition must hold: the answer must be built only from values appearing in the database, never from quantifiers ranging over infinite domains. Second, of the two calculus dialects, SQL's SELECT ... FROM ... WHERE ... is syntactically nearest to the domain calculus — each table alias is a quantified tuple, the WHERE is the predicate, and the SELECT list is the free variables — which is why "relational calculus" is named as examinable material in the course's own syllabus recap.

Real-world: every ORM (object-relational mapper) and every AI query generator works in the calculus mindset — it describes what data is wanted and lets the engine decide how. The WHERE clauses, IN (SELECT ...) subqueries, and NOT EXISTS conditions that appear in production SQL are all, under the hood, membership atoms, comparison atoms, and quantifiers of exactly the kinds written above.

7.10 Heuristic Query Optimization

The lecture closed with the promise that query optimization is taught theoretically, through relational algebra. This supplement supplies that theory: given one SQL query, a DBMS can generate many equivalent relational algebra expressions, and optimization is the science of picking the cheapest one. The syllabus names two ingredients — equivalence rules and cost models — and the heuristic strategy uses the first without needing the second in detail.

7.10.1 Equivalence Rules for Relational Algebra

Two expressions are equivalent when they always produce the same result on every database instance. The equivalence rules are the rewrite toolkit of the optimizer. The core rules (standard, from every database textbook):

1. Cascading selections: ${\sigma }_{c_1\wedge c_2}(E)\equiv {\sigma }_{c_1}({\sigma }_{c_2}(E))$ — a conjunctive selection can be split into a sequence of selections, and the order of two consecutive selections may be swapped: ${\sigma }_{c_1}({\sigma }_{c_2}(E))\equiv {\sigma }_{c_2}({\sigma }_{c_1}(E))$.
2. Cascading projections: ${\pi }_{L_1}({\pi }_{L_2}(E))\equiv {\pi }_{L_1}(E)$ when $L_1\subseteq L_2$ — projecting away attributes twice is the same as projecting once to the smaller list.
3. Commutativity and associativity of joins and products: $E_1\bowtie E_2\equiv E_2\bowtie E_1$; $(E_1\bowtie E_2)\bowtie E_3\equiv E_1\bowtie (E_2\bowtie E_3)$ — the optimizer may join relations in any order, which is the freedom the join-ordering heuristics exploit. The same holds for the Cartesian product.
4. Selection with product becomes join: ${\sigma }_c(E_1\times E_2)\equiv E_1{\bowtie }_c{E}_2$ — a Cartesian product immediately followed by a selection is a theta join, and joins are far cheaper than products.
5. Selection distributes over joins and products: ${\sigma }_c(E_1\bowtie E_2)\equiv {\sigma }_c(E_1)\bowtie E_2$ when the selection condition $c$ mentions only attributes of $E_1$ — filtering one side before the join shrinks the input. The same rule applies to the product.
6. Selection and projection distribute over union: ${\sigma }_c(E_1\cup E_2)\equiv {\sigma }_c(E_1)\cup {\sigma }_c(E_2)$, ${\pi }_L(E_1\cup E_2)\equiv {\pi }_L(E_1)\cup {\pi }_L(E_2)$ — and selection also distributes over intersection and set difference.

7.10.2 The Heuristic Strategy

A heuristic optimizer does not enumerate every plan and price it — it applies a fixed set of common-sense rewrite rules that almost always reduce cost. The canonical strategy, in order:

1. Push selections down as far as possible (rule 5, applied repeatedly). A selection shrinks the number of tuples flowing up the operator tree, and everything above the selection does less work. This single rule is the biggest win in practice.
2. Push projections down as far as possible (rule 2, applied to keep only needed attributes). A projection shrinks tuple width, so more tuples fit in a block and in memory.
3. Combine a Cartesian product with a following selection into a join (rule 4) — and never execute a bare product followed by a separate selection when they can merge.
4. Reorder joins to join the smallest relations first — since joins associate and commute (rule 3), the optimizer joins the relation expected to produce the fewest tuples earliest.
5. Cascade selections, then commute and reorder the remaining operators using the rules until the tree is in canonical form.

7.10.3 Cost Models: Block Accesses and CPU

The heuristic rules improve almost any query, but the decision rules of a real optimizer need a numeric yardstick: a cost model. The standard model counts the two resources that the storage lectures made central:

$$\text{cost}=\text{(number of block transfers)}\times c_B+\text{(number of seeks)}\times c_S+\text{CPU cost}$$

Block transfers and seeks dominate everything — the access-time discussion of the storage session showed seek plus rotational latency is an order of magnitude above transfer time, so seeks are weighted correspondingly heavily. Each plan is priced by estimating the size of the intermediate results at every step, using the statistics a DBMS keeps (number of tuples per relation, number of distinct values per attribute, and the selectivity factor of each condition — the fraction of tuples a predicate is expected to pass).

The worked numerical from the indexing session is exactly this arithmetic: a full scan of 300,000 records in blocks of 40 records costs 7,500 block transfers, while the primary index cuts the lookup to 4 block accesses — the optimizer would be choosing between plans priced in precisely these units. Course-level exam questions expect this qualitative-and-numerical level: enumerate the plans, count block accesses for each, pick the cheapest, and justify with the rules.

Real-world: real optimizers (MySQL's, PostgreSQL's, Oracle's) do exactly this — they translate SQL to a relational algebra tree, rewrite it with equivalence rules, estimate the cost of each candidate plan from statistics, and execute the cheapest. The course's theoretical treatment is the same science; the practical tuning, as the lecture noted, needs administrative privileges on a real system.

Exam Guidance Summary

• Coverage so far: roughly 80% of relational algebra is complete. The aggregation operation (minimum, maximum) and some joins are still pending and will be covered next session, together with a revision. Spreading the topic over two weeks means you revise twice — the stated goal is better performance in the final exams.
• Correctness over efficiency: in relational algebra answers, every correct option is accepted; query optimization and efficiency is a separate topic. When the attribute survives the projection, select-then-project and project-then-select both fetch full marks.
• Relations are duplicate-free: the final result of any operation — select, project, union, intersection, set difference, Cartesian product, join — is a relation, so expect duplicate-elimination questions (union of overlapping sets, projection of non-key attributes, distinct supervisors).
• Important question: "retrieve the name of the manager of each department" (rename the manager SSN, join, project names) was flagged as very important. "Retrieve all the supervisors" exposes a limit of relational algebra.
• Reading the requirement: the department number lives in four relations (department locations, department, project, employee); the user's phrasing decides which relation you operate on.
• Homework: the RA practice sheet in the files folder; solutions are in the shared handout. Attempt the questions even if not fully correct; share attempts on WhatsApp or email. The instructor acts as an accountable partner.
• Assignment: a common requirement specification will be shared so submissions can be evaluated fairly.
• Tooling: install MySQL Community Server and MySQL Workbench before the next session; lab sheet 0 covers the query space, result space, and status area.

Key Industry Applications

• Every application category — supply chain, railways, airlines, banking, agriculture, automobile, edtech — runs on data; storing and retrieving data well, with concurrent access for many users, is what lets an application scale. A prototype-stage startup can live on an ER diagram and a basic relational schema, but a commercial application needs a normalized schema (semantics, minimal redundancy, minimal nulls, minimal spurious tuples).
• Real-world: SQL query optimization is done in relational algebra terms — the DBMS's query optimizer thinks in exactly this mathematics.
• Real-world: MySQL Workbench and MySQL Community Server are free, open-source tools you keep after the course; SHOW DATABASES, USE, and the query/result/status areas are the everyday work surface for practicing SQL from the lab sheets.
• Real-world: organizations block third-party software installs on office machines because of backdoor/security risk; software is provisioned through labs instead.
• Real-world: the relational algebra ↔ SQL correlation is useful beyond programming — the same retrieval logic shows up in management and sales thinking.