Relational model, relational algebra and calculus notes — Unit 2

The Relational Model was introduced by E.F. Codd in 1970. It revolutionized database management by providing a solid mathematical foundation based on set theory and predicate logic. It is the basis for all modern relational databases (MySQL, PostgreSQL, Oracle).

The core concept is brilliantly simple: All data is represented as two-dimensional tables called Relations.

⇒1.1 The Shift from Physical to Logical

In earlier models (Hierarchical, Network), the programmer had to navigate physical pointers to find related data. In the Relational Model, relationships are entirely logical. You relate two tables by ensuring they share a common column (e.g., finding the Department Name for an Employee by matching the `Dept_ID` column in both tables).

The Relational Model uses strict mathematical terminology. While SQL uses the terms 'Table', 'Row', and 'Column', the formal theory uses 'Relation', 'Tuple', and 'Attribute'.

• Relation: A mathematical term for a two-dimensional Table. It is a set of tuples.
• Tuple: A single Row in the table. It represents one specific record (e.g., all data regarding student John Doe).
• Attribute: A single Column in the table. It represents a property (e.g., `Age` or `Salary`).
• Degree (Arity): The number of attributes (columns) in a relation. A table with 5 columns has a degree of 5.
• Cardinality: The number of tuples (rows) in a relation. A table with 1000 employee records has a cardinality of 1000.
• Domain: The set of all permitted, valid values for an attribute. For example, the domain of an `Age` attribute might be integers between 0 and 150. A `Gender` domain might be strictly the set {'M', 'F', 'Other'}.

Not every table is a valid mathematical relation. To be a true relation, a table must adhere to strict mathematical rules based on Set Theory.

⇒3.1 The Rules

• Tuples are Unordered: The rows have no specific mathematical order. Moving row 10 to row 1 does not change the relation in any way. (This is why SQL output order is random unless you use `ORDER BY`).
• Attributes are Unordered: The columns have no specific mathematical order. A table defined as (ID, Name) is logically identical to (Name, ID).
• No Duplicate Tuples: A mathematical Set cannot contain duplicate elements. Therefore, a true relation cannot have two identical rows. Every row must be unique.
• Atomic Values: Every cell at the intersection of a tuple and an attribute must contain exactly ONE atomic value. You cannot put a list or array inside a single cell. (This is known as First Normal Form).
• Same Domain: All values in a specific column must come from the same domain. You cannot mix strings and integers in an `Age` column.

A database must accurately reflect reality. Integrity constraints are strict mathematical rules enforced by the DBMS to prevent users from inserting garbage, invalid, or contradictory data.

⇒4.1 Domain Constraints

Dictates that the value of each attribute must be an atomic value from the attribute's specific domain. If you try to insert "Apple" into an integer `Salary` column, the DBMS rejects it, enforcing domain integrity.

⇒4.2 Entity Integrity Constraint

This rule states: No Primary Key attribute can be NULL.

The Primary Key is the sole mechanism used to uniquely identify individual tuples. If the Primary Key is NULL (unknown or missing), we cannot identify the record, defeating the entire purpose of the relational model. Therefore, the DBMS will instantly reject any `INSERT` operation that leaves the PK blank.

This is the most complex and important constraint. It maintains consistency between two different tables.

⇒5.1 The Foreign Key Concept

A Foreign Key (FK) is an attribute in one table (the Referencing Table) that perfectly matches the Primary Key of another table (the Referenced Table). It acts as the "glue" holding the database together.

Consider an `EMPLOYEE` table and a `DEPARTMENT` table. To indicate which department an employee works for, we add `Dept_ID` as a Foreign Key in the `EMPLOYEE` table, pointing to the Primary Key `Dept_ID` in the `DEPARTMENT` table.

⇒5.2 The Referential Integrity Rule

The rule states: A Foreign Key value must either exist as a Primary Key value in the referenced table, or it must be completely NULL.

This prevents "Orphan Records". If an HR clerk tries to assign an employee to Department 99, but Department 99 does not exist in the `DEPARTMENT` table, the DBMS will aggressively block the operation, throwing a Foreign Key Violation error.

Once an ER Diagram is drawn, it must be mechanically converted into Relational Tables. There is a strict algorithmic process for this.

⇒6.1 Mapping Regular Entities

For each strong entity type, create a table. Include all simple attributes. Choose one of the candidate keys as the Primary Key.

⇒6.2 Mapping Composite Attributes

Because relations must be atomic, composite attributes are "flattened". If an entity has a composite `Address` attribute (Street, City, Zip), you create three separate columns in the table: `Street`, `City`, and `Zip`. The parent attribute name `Address` is discarded.

⇒6.3 Mapping Multi-Valued Attributes

A cell cannot hold multiple values. If `EMPLOYEE` has a multi-valued `Phone_Number` attribute, you must create an entirely New Table. This new table has two columns: the Phone Number itself, and a Foreign Key pointing back to the Employee's Primary Key. The PK of this new table is the combination of both columns.

How relationships are mapped depends entirely on their Cardinality Ratio.

⇒7.1 Mapping 1:N (One-to-Many)

Identify the "Many" side of the relationship. Take the Primary Key of the "One" side, and insert it as a Foreign Key into the table of the "Many" side.

Example: Department (1) to Employee (N). Place the `Dept_ID` inside the `EMPLOYEE` table.

⇒7.2 Mapping M:N (Many-to-Many)

You cannot simply place a Foreign Key in either table, because one row would need to point to multiple rows, violating atomic values.

You MUST create an entirely New Table (a Junction Table / Linking Table).
Example: Student (M) to Course (N). Create an `ENROLLMENT` table. Its columns will be the Primary Key of Student (`Student_ID`) and the Primary Key of Course (`Course_ID`). The Primary Key of this new table is the combination of both.

Before SQL was invented, E.F. Codd designed a pure mathematical query language: Relational Algebra. It is a procedural language; it specifies exactly how to perform operations step-by-step using mathematical symbols.

It forms the absolute backbone of query processing. When you write an SQL query, the DBMS compiler translates it into a Relational Algebra expression tree to execute it.

⇒8.1 The Closure Property

A fundamental property of Relational Algebra: Every operation takes one or two relations as input, and always produces a new relation as output. Because the output is always a relation, operations can be nested indefinitely (e.g., joining two tables, then filtering the result, then selecting columns from that result).

⇒9.1 SELECT Operation ($\sigma$ - Sigma)

Filters the rows (tuples) of a relation based on a specific boolean condition. It slices the table horizontally.

Syntax: $\sigma_{condition}(Relation)$

Example: To find all employees earning more than $50k:$\sigma_{Salary > 50000}(EMPLOYEE)$

(Equivalent SQL: `SELECT FROM EMPLOYEE WHERE Salary > 50000`)*

⇒9.2 PROJECT Operation ($\pi$ - Pi)

Selects specific columns (attributes) from a relation and discards the rest. It slices the table vertically. Crucially, because the output must be a mathematical set, the PROJECT operation automatically eliminates any duplicate rows.

Syntax: $\pi_{attribute\_list}(Relation)$

Example: To get a list of all employee names:
$\pi_{Name}(EMPLOYEE)$

Nesting: To get the names of employees earning > $50k:$\pi_{Name}(\sigma_{Salary > 50000}(EMPLOYEE))$

Because relations are sets, standard set theory operations apply. However, to use them, the two relations must be Union Compatible (Type Compatible): they must have the exact same number of columns, and corresponding columns must have the same data types.

⇒10.1 UNION ($\cup$)

Combines all tuples from relation R and relation S, removing duplicates.
$R \cup S$

⇒10.2 INTERSECTION ($\cap$)

Returns only the tuples that exist in BOTH relation R and relation S.
$R \cap S$

⇒10.3 SET DIFFERENCE ($-$)

Returns all tuples that exist in R, but do NOT exist in S. (Order matters!).
$R - S$

⇒10.4 CARTESIAN PRODUCT ($\times$)

Does not require Union Compatibility. It combines every single row of R with every single row of S. If R has 10 rows and S has 5 rows, the output will be a massive table of 50 rows. Rarely used alone; it is the mathematical foundation for the JOIN operation.

The JOIN operator ($\bowtie$) is the most critical operation for combining related data from different tables.

Mathematically, a JOIN is a Cartesian Product followed immediately by a SELECT operation to filter out the nonsense combinations.

⇒11.1 Theta Join ($\bowtie_\theta$)

A join based on a general boolean condition ($\theta$).
$EMPLOYEE \bowtie_{EMPLOYEE.Dept\_ID = DEPARTMENT.Dept\_ID} DEPARTMENT$

⇒11.2 Equi-Join and Natural Join

• Equi-Join: A Theta join where the condition only uses equality operators (`=`). The resulting table will have two identical columns (one from each table).
• Natural Join ($\bowtie$): The ultimate, cleanest join. It automatically finds columns in both tables that have the exact same name, performs an Equi-Join on them, and then automatically strips out the duplicate column in the output. This is what we intuitively mean when we "join" tables.

⇒12.1 Outer Joins

A standard Natural Join drops any tuples that don't find a match in the other table. If an Employee hasn't been assigned a Department yet, they disappear from the output.

Outer Joins preserve these unmatched tuples, filling the missing data with NULLs.

• Left Outer Join ($\mathrel{=\kern{-0.5em}\bowtie}$