Join algorithms (nested loop, sort-merge, hash join) in DBMS Theory - Mini Project: Build & Apply

Join Algorithms: Nested Loop, Sort-Merge, and Hash Join

📖 Scenario: You are working with two small tables in a database: Employees and Departments. You want to understand how different join algorithms combine these tables based on the department_id field.This project will guide you through creating simple data sets and applying three common join methods used in databases.

🎯 Goal: Build simple representations of the Employees and Departments tables and then apply the nested loop join, sort-merge join, and hash join algorithms conceptually to combine them on department_id.

📋 What You'll Learn

Create two small tables: Employees and Departments with exact data

Set up a join key variable for department_id

Write pseudocode or simple code lines to perform nested loop join

Add steps to perform sort-merge join and hash join

💡 Why This Matters

🌍 Real World

Join algorithms are fundamental in databases to combine data from multiple tables efficiently. Understanding these helps in optimizing queries and improving database performance.

💼 Career

Database administrators and developers use knowledge of join algorithms to write efficient SQL queries and troubleshoot performance issues in real-world applications.

1

Create the Employees and Departments tables

Create two tables called Employees and Departments with these exact rows:

Employees: (1, 'Alice', 10), (2, 'Bob', 20), (3, 'Charlie', 10)
Departments: (10, 'HR'), (20, 'Engineering'), (30, 'Marketing')

Use the format Employees = [(1, 'Alice', 10), (2, 'Bob', 20), (3, 'Charlie', 10)] and Departments = [(10, 'HR'), (20, 'Engineering'), (30, 'Marketing')]

DBMS Theory

# Create Employees and Departments tables with exact data
# Your code here

Need a hint?

Use lists of tuples to represent each table exactly as shown.

2

Set the join key variable

Create a variable called join_key and set it to the string 'department_id' to represent the field used for joining the tables.

DBMS Theory

Employees = [(1, 'Alice', 10), (2, 'Bob', 20), (3, 'Charlie', 10)]
Departments = [(10, 'HR'), (20, 'Engineering'), (30, 'Marketing')]
# Create join_key variable
# Your code here

Need a hint?

Just assign the string 'department_id' to the variable join_key.

3

Write nested loop join pseudocode

Write a nested loop join using for emp in Employees and for dept in Departments to find matching department_id values (third element in Employees tuple and first element in Departments tuple). Store matching pairs in a list called nested_loop_result as tuples of employee name and department name.

DBMS Theory

Employees = [(1, 'Alice', 10), (2, 'Bob', 20), (3, 'Charlie', 10)]
Departments = [(10, 'HR'), (20, 'Engineering'), (30, 'Marketing')]
join_key = 'department_id'
# Write nested loop join to create nested_loop_result
# Your code here

Need a hint?

Use two loops to compare department IDs and collect matching employee and department names.

4

Add sort-merge and hash join steps

Add code to perform a sort-merge join and a hash join on the same data.

For sort-merge join:
- Sort Employees by department_id (third element)
- Sort Departments by department_id (first element)
- Merge by comparing sorted lists to find matches
- Store results in sort_merge_result as tuples of employee name and department name

For hash join:
- Create a hash table (dictionary) from Departments keyed by department_id
- Loop through Employees and find matching department name from hash table
- Store results in hash_join_result as tuples of employee name and department name

DBMS Theory

Employees = [(1, 'Alice', 10), (2, 'Bob', 20), (3, 'Charlie', 10)]
Departments = [(10, 'HR'), (20, 'Engineering'), (30, 'Marketing')]
join_key = 'department_id'
nested_loop_result = []
for emp in Employees:
    for dept in Departments:
        if emp[2] == dept[0]:
            nested_loop_result.append((emp[1], dept[1]))
# Add sort-merge join and hash join code below
# Your code here

Need a hint?

Sort both tables by department_id for sort-merge join and use two pointers to merge.
For hash join, build a dictionary from Departments and look up department names for each employee.