The Relational Model, Keys and Relational Algebra

What this lesson covers

The relational model is the theory underneath every SQL database. E. F. Codd proposed it in 1970: store all data as relations (tables), connect them by matching values, and query them with a small set of mathematical operations. Because the theory is precise, the database can rewrite and optimize your queries safely, which is why SQL is declarative.

Interviewers love this topic because it separates people who have used a database from people who understand one. Expect questions such as "What is the difference between a candidate key and a super key?", "Can a foreign key be NULL?", "What happens on ON DELETE CASCADE?", and written-test questions like "How many super keys does this relation have?" or "Write the relational algebra for employees who work on all projects."

One running example is used throughout, so every term attaches to something concrete.

The running example

A small company has departments, employees, projects, and a record of who works on which project for how many hours a week.

department                     project
+---------+-------------+      +---------+----------+
| dept_id | dept_name   |      | proj_id | title    |
+---------+-------------+      +---------+----------+
| 10      | Engineering |      | 100     | Payments |
| 20      | Sales       |      | 200     | Search   |
| 30      | HR          |      +---------+----------+
+---------+-------------+

employee
+--------+------------+--------------+-------+--------+---------+
| emp_id | pan        | email        | name  | salary | dept_id |
+--------+------------+--------------+-------+--------+---------+
| 1      | ABCDE1234F | asha@ex.com  | Asha  | 90000  | 10      |
| 2      | BCDEF2345G | ravi@ex.com  | Ravi  | 60000  | 20      |
| 3      | CDEFG3456H | meera@ex.com | Meera | 75000  | 10      |
| 4      | DEFGH4567J | kiran@ex.com | Kiran | 50000  | NULL    |
+--------+------------+--------------+-------+--------+---------+

works_on
+--------+---------+-------+
| emp_id | proj_id | hours |
+--------+---------+-------+
| 1      | 100     | 20    |
| 1      | 200     | 10    |
| 3      | 100     | 30    |
| 2      | 200     | 5     |
+--------+---------+-------+

pan is an Indian Permanent Account Number, a tax id that is unique per person. Kiran has just joined and has no department yet, so dept_id is NULL.

Relational terminology

Each formal term has an everyday equivalent. Use the formal ones in written answers.

A few precise points that interviewers check:

• Domain means the set of atomic values an attribute may take. "Atomic" means the DBMS treats the value as indivisible. Two attributes can share a domain (for example, employee.dept_id and department.dept_id), and comparing them is meaningful.
• Degree counts columns and does not change as data is added. Cardinality counts rows and changes with every insert. Do not confuse this "cardinality of a relation" with the "cardinality ratio" (1:N) of a relationship in the ER model.
• A relational database schema is the set of all relation schemas plus the integrity constraints.

Properties of a relation

Because a relation is a mathematical set of tuples, the theory says:

1. No duplicate tuples. A set cannot contain the same element twice.
2. Tuples are unordered. Row order carries no meaning.
3. Attributes are unordered in the theory (each value is identified by its attribute name, not its position).
4. Values are atomic. Each cell holds a single value from the domain. This is first normal form.
5. Each attribute has a distinct name within the relation.

Real SQL tables bend some of these rules: a SQL table without a primary key or unique constraint can contain duplicate rows, SQL columns do have a position (SELECT * returns them in order), and SELECT returns duplicates unless you write DISTINCT. Mentioning this difference between theory (sets) and SQL (bags, or multisets) in an interview is a strong signal.

Keys

A key is a set of attributes whose values identify tuples. Keys are the foundation of integrity, relationships and indexing. Each type below is defined, then shown on the running example.

Super key

A super key is any set of attributes whose values are unique across all tuples, now and in every valid future state. Adding more attributes to a super key gives another super key.

In employee, each of these is a super key:

• {emp_id}
• {pan}
• {email}
• {emp_id, name}
• {pan, salary, dept_id}
• the set of all six attributes (the whole tuple is always a super key, since tuples are distinct)

{name} is not a super key: two employees can share a name. Notice that uniqueness must come from the business rules, not from the four rows we happen to have. Today all salaries are different, but {salary} is not a super key because two people could earn the same.

Candidate key

A candidate key is a minimal super key: a super key from which no attribute can be removed without losing uniqueness.

In employee, the candidate keys are {emp_id}, {pan} and {email}. {emp_id, name} is a super key but not a candidate key, because you can remove name and it is still unique.

A candidate key can have several attributes. In works_on, neither emp_id nor proj_id is unique alone (Asha works on two projects; Payments has two employees), but {emp_id, proj_id} is unique, and neither part can be dropped. So {emp_id, proj_id} is a candidate key.

"Minimal" means you cannot remove an attribute; it does not mean "has the fewest attributes". A relation can have one candidate key of size 1 and another of size 3.

Primary key

The primary key (PK) is the one candidate key the designer chooses as the main identifier. Rules:

• Exactly one primary key per table (it may span several columns).
• Its values must be unique and not NULL (entity integrity, below).
• It should be stable: it should rarely or never change, since other tables reference it.

For employee, emp_id is the natural choice: short, never changes, contains no personal information. email changes when people change addresses, and pan is sensitive data you do not want copied into every referencing table.

Alternate key

An alternate key (or secondary key in some books) is a candidate key that was not chosen as primary. Here: {pan} and {email}. You declare them with UNIQUE so the database still enforces their uniqueness.

Composite key

A composite key (compound key) is a key made of two or more attributes. {emp_id, proj_id} in works_on is a composite primary key. Junction tables for many-to-many relationships usually have one.

Foreign key

A foreign key (FK) is a set of attributes in one relation (the referencing or child table) whose values must match the primary key, or a unique key, of another relation (the referenced or parent table), or be NULL.

• employee.dept_id references department.dept_id.
• works_on.emp_id references employee.emp_id.
• works_on.proj_id references project.proj_id.

Facts that come up in interviews:

• A foreign key can be NULL (unless declared NOT NULL). Kiran's NULL dept_id means "no department yet", and it does not violate the constraint.
• A foreign key need not be unique. Many employees share dept_id = 10; that is what makes the relationship one-to-many.
• A foreign key can reference its own table (a self-referencing key), such as employee.manager_id referencing employee.emp_id.
• A foreign key can be part of the primary key, as in works_on.
• The referenced columns must be a primary key or have a unique constraint.

Surrogate key versus natural key

A natural key comes from the real world and has business meaning: PAN, email, ISBN, vehicle registration number.

A surrogate key is an artificial identifier with no business meaning, generated by the database: an auto-increment integer (emp_id) or a UUID (a 128-bit randomly generated identifier).

The common practice: use a surrogate primary key, and keep a UNIQUE constraint on the natural key. Without that unique constraint, a surrogate key lets the same person be inserted twice with two different ids.

Counting super keys: a worked problem

A common written-test question: relation R(A, B, C, D) has candidate keys {A} and {B, C}. How many super keys does it have?

A super key is any superset of at least one candidate key. Count with inclusion-exclusion.

Step 1. Supersets of {A}: A is fixed, and each of the other 3 attributes is in or out, so 2³ = 8.

Step 2. Supersets of {B, C}: B and C are fixed, A and D free, so 2² = 4.

Step 3. Supersets of both, that is of {A, B, C}: only D free, so 2¹ = 2.

Step 4. Total = 8 + 4 − 2 = 10.

Check by listing: A, AB, AC, AD, ABC, ABD, ACD, ABCD (8 containing A), plus BC, BCD (the 2 containing BC but not A). Ten.

General shortcuts for a relation with n attributes:

• One candidate key with k attributes: 2^(n−k) super keys.
• Every single attribute is a candidate key: 2ⁿ − 1 super keys (every non-empty subset).

A second example: R(A, B, C, D, E) with candidate keys {A, B} and {C, D}. Supersets of AB: 2³ = 8. Supersets of CD: 2³ = 8. Supersets of ABCD: 2¹ = 2. Total = 8 + 8 − 2 = 14.

Integrity constraints

An integrity constraint is a rule every valid database state must satisfy. The DBMS checks it on every insert, update and delete and rejects any change that breaks it.

Domain constraints

Each attribute value must come from its domain: the right type, and any extra rule declared with NOT NULL, CHECK or DEFAULT.

salary  INTEGER NOT NULL CHECK (salary > 0)
hours   INTEGER NOT NULL CHECK (hours BETWEEN 1 AND 40)

Inserting hours = 50 is rejected. Note: SQLite uses flexible typing (a column declared INTEGER will still accept the text 'abc' unless the table is declared STRICT), so in SQLite the CHECK constraints do most of the domain work. PostgreSQL and MySQL in strict mode reject wrong types outright.

Key constraints

Values of every candidate key must be unique across tuples. Declared with PRIMARY KEY and UNIQUE.

Entity integrity

No primary key attribute may be NULL. The primary key identifies the tuple; a NULL would mean "this row's identity is unknown", and you could never refer to it reliably. Note the difference: a UNIQUE column may hold NULLs (in most systems, several NULLs, since NULL is not equal to NULL), but a primary key may not.

Referential integrity

Every non-NULL foreign key value must match an existing value in the referenced key. You cannot assign an employee to department 99 if department 99 does not exist, and you cannot record work on project 300 if there is no project 300.

Two kinds of operations can break referential integrity:

1. Inserting or updating a child row with a foreign key that has no matching parent. The DBMS simply rejects it.
2. Deleting or updating a parent row that children still reference. Here you choose the behavior with referential actions.

ON DELETE and ON UPDATE options

The same options exist for ON UPDATE (what happens if the parent's key value changes). ON UPDATE CASCADE is useful with natural keys that can change; with surrogate keys you rarely need it. MySQL's InnoDB treats NO ACTION the same as RESTRICT and does not support SET DEFAULT there; PostgreSQL distinguishes them.

Here is the running example with constraints, tested in SQLite:

PRAGMA foreign_keys = ON;

CREATE TABLE department (
  dept_id   INTEGER PRIMARY KEY,
  dept_name TEXT NOT NULL UNIQUE
);

CREATE TABLE employee (
  emp_id  INTEGER PRIMARY KEY,
  pan     TEXT NOT NULL UNIQUE,
  email   TEXT NOT NULL UNIQUE,
  name    TEXT NOT NULL,
  salary  INTEGER NOT NULL CHECK (salary > 0),
  dept_id INTEGER REFERENCES department(dept_id) ON DELETE SET NULL
);

CREATE TABLE project (
  proj_id INTEGER PRIMARY KEY,
  title   TEXT NOT NULL
);

CREATE TABLE works_on (
  emp_id  INTEGER NOT NULL REFERENCES employee(emp_id) ON DELETE CASCADE,
  proj_id INTEGER NOT NULL REFERENCES project(proj_id) ON DELETE RESTRICT,
  hours   INTEGER NOT NULL CHECK (hours BETWEEN 1 AND 40),
  PRIMARY KEY (emp_id, proj_id)
);

INSERT INTO department VALUES (10, 'Engineering'), (20, 'Sales'), (30, 'HR');
INSERT INTO employee VALUES
  (1, 'ABCDE1234F', 'asha@ex.com',  'Asha',  90000, 10),
  (2, 'BCDEF2345G', 'ravi@ex.com',  'Ravi',  60000, 20),
  (3, 'CDEFG3456H', 'meera@ex.com', 'Meera', 75000, 10),
  (4, 'DEFGH4567J', 'kiran@ex.com', 'Kiran', 50000, NULL);
INSERT INTO project VALUES (100, 'Payments'), (200, 'Search');
INSERT INTO works_on VALUES (1, 100, 20), (1, 200, 10), (3, 100, 30), (2, 200, 5);

Now watch each action (run these in order on a copy of the data):

DELETE FROM department WHERE dept_id = 20;
  -> succeeds; Ravi's dept_id becomes NULL     (SET NULL)

DELETE FROM employee WHERE emp_id = 1;
  -> succeeds; Asha's two works_on rows vanish (CASCADE)

DELETE FROM project WHERE proj_id = 100;
  -> FOREIGN KEY constraint failed             (RESTRICT:
     Meera still works on project 100)

INSERT INTO works_on VALUES (99, 100, 5);
  -> FOREIGN KEY constraint failed             (no employee 99)

INSERT INTO works_on VALUES (NULL, 100, 5);
  -> NOT NULL constraint failed                (entity integrity)

Other constraints

• Semantic or general constraints span tables or rows, such as "a manager earns more than their reports". SQL's CREATE ASSERTION was meant for these, but almost no major DBMS implements it; you use triggers or application code instead.
• Functional dependencies are constraints between attribute sets; they drive normalization.

Relational algebra

Relational algebra is a procedural query language: a set of operators that each take one or two relations and return a new relation. Because every result is again a relation, operators can be combined into expressions, just like arithmetic. It matters for two reasons. First, it is the theory SQL is built on, so written tests ask for it. Second, the query optimizer converts your SQL into an algebra tree and rewrites that tree to find a cheaper plan; see query processing and optimization.

Notation: since Greek letters are standard, this lesson uses them. σ is sigma, π is pi, ρ is rho, ⋈ is the join symbol, × is cross product, ∪ ∩ − are union, intersection and difference, and ÷ is division. In text you can also write SELECT[cond], PROJECT[cols] and so on.

The fundamental operators

Six operators are fundamental: every other operator can be built from them. They are select, project, union, set difference, Cartesian product and rename.

Select (σ)

Select keeps the tuples that satisfy a condition. It filters rows; it does not choose columns (a classic naming trap, because SQL's SELECT keyword chooses columns).

σ_{salary > 70000 ∧ dept_id = 10}(employee)

∧ means AND, ∨ means OR, ¬ means NOT.

SELECT * FROM employee WHERE salary > 70000 AND dept_id = 10;

emp_id | pan        | email        | name  | salary | dept_id
-------+------------+--------------+-------+--------+--------
1      | ABCDE1234F | asha@ex.com  | Asha  | 90000  | 10
3      | CDEFG3456H | meera@ex.com | Meera | 75000  | 10

Properties: the result has the same degree as the input, and its cardinality is at most the input's. Select is commutative: σ_c1(σ_c2(R)) = σ_c2(σ_c1(R)) = σ_{c1 ∧ c2}(R).

Project (π)

Project keeps the listed attributes and removes the rest. Since the result is a set, duplicate tuples are removed.

π_{dept_id}(employee) gives {10, 20, NULL}: three tuples, not four, because 10 appears twice.

In SQL, duplicates are kept unless you ask, so the equivalent is:

SELECT DISTINCT dept_id FROM employee;

dept_id
-------
10
20
NULL

(The theory has no NULLs; SQL shows NULL as one of the distinct values.)

Union (∪), intersection (∩) and difference (−)

These are ordinary set operations. They need union-compatible relations: same degree, and corresponding attributes with compatible domains.

Employees in department 10 or working on project 200:

π_{emp_id}(σ_{dept_id=10}(employee)) ∪ π_{emp_id}(σ_{proj_id=200}(works_on))

SELECT emp_id FROM employee WHERE dept_id = 10
UNION
SELECT emp_id FROM works_on WHERE proj_id = 200;

Result: {1, 2, 3}. Department 10 gives {1, 3}; project 200 gives {1, 2}; the union removes the duplicate 1.

Employees working on no project (difference):

π_{emp_id}(employee) − π_{emp_id}(works_on)

SELECT emp_id FROM employee
EXCEPT
SELECT emp_id FROM works_on;

Result: {4} (Kiran). Oracle calls EXCEPT MINUS; MySQL added EXCEPT and INTERSECT in version 8.0.31.

Intersection is not fundamental, because R ∩ S = R − (R − S). Employees in department 10 and on project 200: {1, 3} ∩ {1, 2} = {1}.

Union and intersection are commutative; difference is not (R − S is generally not S − R).

Cartesian product (×)

The Cartesian product (cross product) pairs every tuple of R with every tuple of S. If R has degree d1 and cardinality n1, and S has d2 and n2, the result has degree d1 + d2 and cardinality n1 × n2.

employee × department has degree 6 + 2 = 8 and cardinality 4 × 3 = 12.

SELECT COUNT(*) FROM employee CROSS JOIN department;   -- 12

On its own the product is rarely useful: most of the 12 rows pair an employee with a department they are not in. Combined with select, it becomes a join.

Rename (ρ)

Rename gives a relation or its attributes a new name. You need it when a relation is used twice in one expression, such as comparing employees to other employees.

ρ_e2(employee) renames the relation; ρ_{e2(id, p, m, n, s, d)}(employee) also renames attributes. In SQL, rename is the alias: FROM employee AS e2, or SELECT salary AS pay.

Joins

A join combines related tuples from two relations. It is a derived operator: a product followed by a select.

Theta join: R ⋈_θ S = σ_θ(R × S), where θ is any condition (<, =, >=, and so on).

Equi-join: a theta join that uses only equality. Both copies of the joined column stay in the result.

employee ⋈_{employee.dept_id = department.dept_id} department

Natural join (⋈ with no condition): an equi-join on all attributes with the same name, keeping only one copy of each. employee ⋈ department joins on dept_id, the only shared name.

SELECT e.name, d.dept_name
FROM employee e
JOIN department d ON e.dept_id = d.dept_id;

name  | dept_name
------+------------
Asha  | Engineering
Ravi  | Sales
Meera | Engineering

Kiran is missing: her dept_id is NULL, which matches nothing. HR is missing: no employee is in it. Inner joins drop non-matching tuples on both sides.

Outer joins keep the non-matching tuples, filling the missing side with NULLs.

• Left outer join (⟕): all tuples of the left relation.
• Right outer join (⟖): all tuples of the right relation.
• Full outer join (⟗): all tuples of both.

SELECT e.name, d.dept_name
FROM employee e
LEFT JOIN department d ON e.dept_id = d.dept_id;

name  | dept_name
------+------------
Asha  | Engineering
Ravi  | Sales
Meera | Engineering
Kiran | NULL

Outer joins are not part of the original algebra but are standard extensions. All join types, with full result tables, are worked through in SQL fundamentals.

Semi-join (⋉) returns the tuples of R that have at least one match in S, with only R's attributes; SQL expresses it with EXISTS or IN. Anti-join (▷) returns tuples of R with no match; SQL uses NOT EXISTS.

Division (÷)

Division answers "for all" questions: which employees work on all projects? If R(A, B) and S(B), then R ÷ S is the set of A values that are paired in R with every B value in S.

Here R = π_{emp_id, proj_id}(works_on) and S = π_{proj_id}(project) = {100, 200}.

Step by step:

1. Group R by employee: 1 → {100, 200}, 3 → {100}, 2 → {200}.
2. Keep employees whose set contains all of {100, 200}.
3. Only employee 1 qualifies. R ÷ S = {1}.

Division is a derived operator. Using only fundamental operators:

T1 = pi_A(R) x S              every possible (emp, project) pair
T2 = pi_A(T1 - R)             emps missing at least one project
R / S = pi_A(R) - T2          emps missing none

Worked: π_A(R) = {1, 2, 3}. T1 = 3 × 2 = 6 pairs. T1 − R removes the 4 real pairs and leaves (3, 200) and (2, 100). T2 = {3, 2}. Answer = {1, 2, 3} − {2, 3} = {1}.

SQL has no division operator. Two standard ways to write it:

-- "There is no project this employee does not work on"
SELECT e.emp_id, e.name
FROM employee e
WHERE NOT EXISTS (
  SELECT p.proj_id FROM project p
  WHERE NOT EXISTS (
    SELECT 1 FROM works_on w
    WHERE w.emp_id = e.emp_id AND w.proj_id = p.proj_id
  )
);

-- Count the projects each employee works on and compare
SELECT emp_id
FROM works_on
GROUP BY emp_id
HAVING COUNT(DISTINCT proj_id) = (SELECT COUNT(*) FROM project);

Both return employee 1 (Asha). The double NOT EXISTS reads as "there is no project for which there is no works_on row". The counting version relies on every proj_id in works_on being a real project, which the foreign key guarantees.

More worked queries

Query 1. Names of employees who work on the Payments project.

π_name(employee ⋈ works_on ⋈ σ_{title='Payments'}(project))

SELECT e.name
FROM employee e
JOIN works_on w ON w.emp_id = e.emp_id
JOIN project  p ON p.proj_id = w.proj_id
WHERE p.title = 'Payments';

Result: Asha, Meera.

Notice the selection on project is applied before the join in the algebra. The result is the same as joining first and filtering later, but cheaper. Pushing selections down the tree is the most important optimization rule.

Query 2. The highest salary, without using MAX.

A salary is not the highest if some other salary is bigger. So take all salaries and subtract those that are smaller than some salary.

pi_salary(employee)
  - pi_e1.salary( sigma_{e1.salary < e2.salary}
                  ( rho_e1(employee) x rho_e2(employee) ) )

SELECT salary FROM employee
EXCEPT
SELECT e1.salary
FROM employee e1 JOIN employee e2 ON e1.salary < e2.salary;

Result: 90000. Every salary except 90000 is smaller than at least one other salary. This trick, a self-join plus difference, is a favorite written-test question and shows why rename is needed.

Query 3. Departments with no employees.

π_{dept_id}(department) − π_{dept_id}(employee) = {10, 20, 30} − {10, 20, NULL} = {30} (HR). In SQL, use NOT EXISTS rather than NOT IN here, because NOT IN with a subquery that contains a NULL returns no rows at all. The SQL fundamentals lesson explains why.

Summary of operators

Relational calculus (brief)

Relational algebra is procedural: the expression describes a sequence of operations. Relational calculus is declarative: you describe the properties of the result and say nothing about how to compute it. SQL borrows its declarative style from calculus and its operations from algebra.

Tuple relational calculus (TRC)

Variables range over tuples. A query has the form { t | P(t) }: the set of tuples t for which predicate P is true.

Employees earning over 70000:

{ t | t ∈ employee ∧ t.salary > 70000 }

Names of employees who work on some project (uses the existential quantifier ∃, "there exists"):

{ t.name | t ∈ employee ∧ ∃ w ( w ∈ works_on ∧ w.emp_id = t.emp_id ) }

Employees who work on all projects (uses the universal quantifier ∀, "for all"):

{ t | t ∈ employee ∧ ∀ p ( p ∈ project ⇒
        ∃ w ( w ∈ works_on ∧ w.emp_id = t.emp_id
                           ∧ w.proj_id = p.proj_id ) ) }

Compare this with the double NOT EXISTS SQL: "for all p, there exists w" is logically the same as "there is no p for which no w exists".

Domain relational calculus (DRC)

Variables range over attribute values (domains) instead of whole tuples. Employees earning over 70000, with one variable per column:

{ <i, p, e, n, s, d> | <i, p, e, n, s, d> ∈ employee ∧ s > 70000 }

DRC is the basis of QBE (Query By Example), where you fill example values into a grid.

Safety and expressive power

A calculus expression is safe if it is guaranteed to produce a finite result. { t | ¬(t ∈ employee) }, "all tuples that are not employees", is unsafe: the set of all possible tuples is infinite. Restricting calculus to safe expressions, Codd's theorem states that relational algebra, safe tuple calculus and safe domain calculus have the same expressive power. A language that can express every query those can is called relationally complete. SQL is relationally complete and goes further with aggregation, grouping, ordering and recursion, which pure algebra lacks.

Interview questions

Q1. What is the difference between a super key, a candidate key and a primary key?

A super key is any set of attributes that uniquely identifies tuples. A candidate key is a minimal super key, from which no attribute can be removed without losing uniqueness. The primary key is the one candidate key the designer chooses as the main identifier; it must be unique and not NULL. For an employee table, {emp_id, name} is a super key, {emp_id} and {pan} are candidate keys, and emp_id is the primary key.

Q2. Can a foreign key be NULL? Can it have duplicates?

Yes to both, unless you add NOT NULL or UNIQUE. A NULL foreign key means the relationship does not exist for that row, like an employee not yet assigned to a department. Duplicates are normal: many employees share the same department id, which is what makes the relationship one-to-many. A foreign key with a UNIQUE constraint models a one-to-one relationship.

Q3. What is the difference between a primary key and a unique key?

Both enforce uniqueness. A table has exactly one primary key, and its columns cannot be NULL. A table can have many unique keys, and in most databases a unique column can hold NULLs (often several, since NULLs are not equal to each other; SQL Server is an exception and allows only one NULL in a unique index by default). In MySQL InnoDB and SQL Server, the primary key also usually decides the physical (clustered) order of rows.

Q4. Surrogate key or natural key: which do you prefer?

Usually a surrogate primary key plus a unique constraint on the natural key. Surrogates are small, stable and fast to join, and they never need to change when real-world data changes, such as an email address. The unique constraint on the natural key still stops duplicate real-world entities. A natural key can be fine as the primary key when it is truly stable and compact, like an ISO country code.

Q5. Explain entity integrity and referential integrity.

Entity integrity says no part of a primary key may be NULL, because the primary key is how a row is identified. Referential integrity says every non-NULL foreign key value must match an existing key in the referenced table. Together they guarantee every row can be identified and every reference points to something real.

Q6. What do ON DELETE CASCADE, SET NULL and RESTRICT do?

They decide what happens to child rows when a referenced parent row is deleted. CASCADE deletes the child rows too, which suits dependent data like order items. SET NULL keeps the child rows but sets their foreign key to NULL, which suits optional links. RESTRICT (and the default NO ACTION) refuses the delete while children exist, which protects important records.

Q7. R(A, B, C, D) has candidate keys {A} and {B, C}. How many super keys are there?

Supersets of A: 2³ = 8. Supersets of BC: 2² = 4. Supersets of both, ABC: 2¹ = 2. By inclusion-exclusion the answer is 8 + 4 − 2 = 10.

Q8. What is the difference between selection and projection?

Selection (σ) filters rows using a condition and keeps all columns; it corresponds to SQL's WHERE. Projection (π) keeps chosen columns and removes duplicate rows; it corresponds to the column list in SQL's SELECT, plus DISTINCT. The naming is confusing because SQL's SELECT keyword does projection.

Q9. Which relational algebra operators are fundamental?

Select, project, union, set difference, Cartesian product and rename. Intersection, all joins and division can be expressed using these six. For example, intersection is R − (R − S), and a theta join is a selection over a Cartesian product.

Q10. What is division used for, and how do you write it in SQL?

Division answers "for all" queries, such as students who took every course or employees who work on all projects. SQL has no division operator, so you write a double NOT EXISTS ("there is no project this employee does not work on") or group and compare counts with HAVING COUNT(DISTINCT proj_id) = (SELECT COUNT(*) FROM project).

Q11. What is the difference between a natural join and an equi-join?

An equi-join joins on equality conditions you specify and keeps both copies of the join columns. A natural join automatically joins on all columns with the same name and keeps one copy of each. Natural joins are risky in real code because adding a same-named column to either table silently changes the join condition.

Q12. What are the degree and cardinality of R × S?

If R has degree d1 and cardinality n1, and S has degree d2 and cardinality n2, then R × S has degree d1 + d2 and cardinality n1 × n2. With a 6-column, 4-row employee table and a 2-column, 3-row department table, the product has 8 columns and 12 rows.

Q13. What is the difference between relational algebra and relational calculus?

Algebra is procedural: an expression is a sequence of operations that produce the result. Calculus is declarative: you state what the result must satisfy. Tuple calculus uses variables over tuples, domain calculus uses variables over attribute values. By Codd's theorem, algebra and safe calculus are equally expressive.

Q14. How do relations in theory differ from tables in SQL?

A relation is a set, so it has no duplicate tuples and no row order, and in theory no column order or NULLs. SQL tables are bags: without a key they can hold duplicates, queries return duplicates unless you use DISTINCT, columns have a position, and NULL is allowed with three-valued logic. Knowing this explains why UNION removes duplicates but UNION ALL does not.

Key takeaways

• A relation is a set of tuples over named attributes, each drawn from a domain; degree counts columns, cardinality counts rows.
• Super key: unique. Candidate key: minimal super key. Primary key: the chosen candidate key. Alternate keys: the other candidates.
• Foreign keys can be NULL and repeat; they enforce referential integrity against a primary or unique key.
• Prefer a surrogate primary key plus a UNIQUE constraint on the natural key.
• Choose ON DELETE actions deliberately: CASCADE for dependent data, SET NULL for optional links, RESTRICT for important parents.
• Six fundamental algebra operators: σ, π, ∪, −, ×, ρ. Joins, intersection and division are derived.
• Division answers "for all" questions; write it in SQL with double NOT EXISTS or a count comparison.
• Algebra is procedural, calculus is declarative, and both are equally expressive when calculus is safe.

Next lesson

Continue with SQL fundamentals.