Relational Query Languages
Open in the Padhaiko app3.1 Relational algebra
Relational algebra is a procedural query language consisting of a set of operations that take one or two relations as input and produce a new relation as output. Because the output is always a relation, operations can be arbitrarily composed into relational algebra expressions (closed under the relational model).
Fundamental and Derived Relational Algebra Operations
The six basic (fundamental) operations of relational algebra are:
- Select (): Unary operation that selects tuples (rows) from relation satisfying selection predicate :
- Project (): Unary operation that extracts specified attributes (columns) and automatically eliminates duplicate rows (since relations are sets).
- Union (): Binary operation returning tuples in , in , or in both. Requires union-compatibility ( and must have the same arity and compatible attribute domains).
- Set Difference (): Binary operation returning tuples in that are not in (requires union-compatibility).
- Cartesian Product (): Binary operation pairing every tuple of with every tuple of . If has tuples and attributes and has tuples and attributes, has tuples and attributes.
- Rename ( or ): Unary operation assigning a new name (and optionally new attribute names) to the result of expression —essential for self-joins.
Additional (derived) operations expressed using the six primitives:
- Set Intersection (): Tuples present in both union-compatible relations.
- Theta-Join () and Natural Join (): Combines tuples from and matching on common attributes (natural join keeps one copy of common attributes).
- Division (): Finds tuples in associated with every tuple in (used for "for all" queries, e.g., students enrolled in all core courses):
3.2 Concept of DDL, DML and DCL
SQL (Structured Query Language) statements are categorized by their functional role in defining, manipulating, and controlling database access:
| Sub-Language | Full Name | Purpose | Common Commands |
|---|---|---|---|
| DDL | Data Definition Language | Defines, alters, and drops database schemas, tables, constraints, views, and indexes (updates the data dictionary). | CREATE, ALTER, DROP, TRUNCATE, RENAME |
| DML | Data Manipulation Language | Queries and modifies the actual data tuples inside tables. | SELECT, INSERT, UPDATE, DELETE |
| DCL | Data Control Language | Controls user access permissions, privileges, and roles. | GRANT, REVOKE |
| TCL (related) | Transaction Control Language | Manages transaction boundaries and durability. | COMMIT, ROLLBACK, SAVEPOINT |
3.3 Overview of the SQL query language-DDL and DML queries
DDL Commands (CREATE, ALTER, DROP, TRUNCATE)
SQL DDL defines relation schemas along with column data types (INT, NUMERIC(p,s), VARCHAR(n), CHAR(n), DATE) and integrity constraints (PRIMARY KEY, FOREIGN KEY, NOT NULL, UNIQUE, CHECK, DEFAULT).
CREATE TABLE Department (
DeptID INT PRIMARY KEY,
DeptName VARCHAR(50) NOT NULL UNIQUE
);
CREATE TABLE Student (
RollNo INT PRIMARY KEY,
Name VARCHAR(60) NOT NULL,
Semester INT CHECK (Semester BETWEEN 1 AND 8),
GPA NUMERIC(3, 2) DEFAULT 0.00,
DeptID INT,
FOREIGN KEY (DeptID) REFERENCES Department(DeptID)
ON DELETE SET NULL
ON UPDATE CASCADE
);
-- Alter schema: add a column or constraint
ALTER TABLE Student ADD Email VARCHAR(80) UNIQUE;
-- Remove all rows quickly (keeps table structure)
TRUNCATE TABLE Student;
-- Permanently remove table definition and data
DROP TABLE Student;Basic DML SELECT Query Structure
A basic SQL query follows the SFW (Select–From–Where) structure:
- Execution Order (Conceptual):
FROM(Cartesian product/joins)WHERE(row filtering)GROUP BYHAVINGSELECT(projection/expressions)DISTINCTORDER BY. - SQL vs. Relational Algebra Duplicate Handling: Relational algebra eliminates duplicate rows automatically; SQL uses multiset (bag) semantics by default and requires
SELECT DISTINCTto remove duplicates. - Pattern Matching & Sorting:
LIKEsupports%(zero or more characters) and_(exactly one character);ORDER BY col ASC|DESCsorts output;IS NULL/IS NOT NULLtest for missing values (never= NULL).
SELECT DISTINCT Name, GPA
FROM Student
WHERE DeptID = 10 AND Name LIKE 'A%'
ORDER BY GPA DESC;3.4 Set operations
SQL implements the three classical mathematical set operations on query results—UNION, INTERSECT, and EXCEPT (called MINUS in Oracle). Both SELECT queries must be union-compatible (same number of columns in the same order with compatible data types).
| Aspect | Set-Eliminating (Default) | Multiset / Duplicate-Preserving (ALL) |
|---|---|---|
UNION / INTERSECT / EXCEPT | Automatically eliminates duplicate rows in the result. | , , |
UNION ALL / INTERSECT ALL / EXCEPT ALL | Retains duplicates according to bag multiplicity (, , ). | Multiset bag operators |
-- Students enrolled in Course 301 OR Course 302 (no duplicates)
SELECT RollNo FROM Enrolls WHERE CourseID = 301
UNION
SELECT RollNo FROM Enrolls WHERE CourseID = 302;
-- Students enrolled in BOTH Course 301 AND Course 302
SELECT RollNo FROM Enrolls WHERE CourseID = 301
INTERSECT
SELECT RollNo FROM Enrolls WHERE CourseID = 302;
-- Students enrolled in Course 301 but NOT Course 302
SELECT RollNo FROM Enrolls WHERE CourseID = 301
EXCEPT
SELECT RollNo FROM Enrolls WHERE CourseID = 302;3.5 Aggregate functions – GROUP BY – HAVING
Aggregate functions take a collection (multiset) of values from a column and compute a single summary value:
COUNT(*)/COUNT(col):COUNT(*)counts all rows (includingNULLs);COUNT(col)ignoresNULLs;COUNT(DISTINCT col)counts unique non-null values.SUM(col)/AVG(col): Sum and arithmetic mean of non-null numeric values.MIN(col)/MAX(col): Minimum and maximum non-null values.
GROUP BY and HAVING
GROUP BYpartitions rows that share identical values on grouping columns into groups so aggregate functions produce one summary row per group.WHEREvs.HAVING:WHEREfilters individual rows before grouping (cannot contain aggregate functions);HAVINGfilters entire groups afterGROUP BYand aggregation.- Rule: Any non-aggregated attribute appearing in the
SELECTlist must appear in theGROUP BYclause.
-- Find departments with more than 20 students and average GPA >= 3.20
SELECT DeptID, COUNT(*) AS TotalStudents, AVG(GPA) AS AvgGPA
FROM Student
WHERE Semester >= 3
GROUP BY DeptID
HAVING COUNT(*) > 20 AND AVG(GPA) >= 3.20
ORDER BY AvgGPA DESC;3.6 Joins and types of joins
A JOIN combines tuples from two or more relations based on a related column or join condition.
| Join Type | Behavior on Matching vs. Non-Matching Rows | Relational Algebra |
|---|---|---|
CROSS JOIN | Pairs every row of with every row of ( rows). | |
INNER JOIN | Returns only pairs of rows satisfying the ON condition (or USING). Unmatched rows are dropped. | |
NATURAL JOIN | Joins implicitly on all columns with identical names and types, keeping one copy of each common column. | |
LEFT OUTER JOIN | Returns all matching rows plus unmatched rows from the left table padded with NULLs on the right. | () |
RIGHT OUTER JOIN | Returns all matching rows plus unmatched rows from the right table padded with NULLs on the left. | |
FULL OUTER JOIN | Returns all matching rows plus unmatched rows from both left and right tables padded with NULLs. | |
| Self-Join | Joins a table with itself using table aliases (e.g., Employee E JOIN Employee M ON E.MgrID = M.EmpID). |
-- 1. Inner Join: Students with their department names
SELECT S.RollNo, S.Name, D.DeptName
FROM Student S
INNER JOIN Department D ON S.DeptID = D.DeptID;
-- 2. Left Outer Join: Include students even if DeptID is NULL
SELECT S.RollNo, S.Name, D.DeptName
FROM Student S
LEFT OUTER JOIN Department D ON S.DeptID = D.DeptID;3.7 Nested sub queries
A nested subquery is a SELECT–FROM–WHERE query embedded inside another SQL query (WHERE, FROM, or SELECT clause).
Independent vs. Correlated Subqueries and Set Predicates
- Non-Correlated (Independent) Subquery: The inner query runs once independently of the outer query, producing a scalar value or set of values used by the outer query.
- Correlated Subquery: The inner query references an attribute from the outer query's table alias and therefore must be re-evaluated once for each candidate row of the outer query.
- Subquery Operators:
IN/NOT IN: Tests set membership (caution:x NOT IN (subquery)evaluates toUNKNOWNif the subquery returns even oneNULL!).ANY(SOME) /ALL: Compares a scalar against a set using>,<,=,>=,<=(e.g.,Salary > ALL (...)means greater than the maximum).EXISTS/NOT EXISTS: Evaluates toTRUEif the subquery returns at least one row (or zero rows forNOT EXISTS). Ideal for correlated subqueries and division queries ("for all").
-- Non-correlated: Students whose GPA exceeds the university average
SELECT RollNo, Name, GPA
FROM Student
WHERE GPA > (SELECT AVG(GPA) FROM Student);
-- Correlated with EXISTS: Departments that currently have at least one student
SELECT D.DeptName
FROM Department D
WHERE EXISTS (
SELECT 1 FROM Student S WHERE S.DeptID = D.DeptID
);3.8 Database modification (Insert, update, delete)
DML modification statements change the stored database instance while respecting all primary key, foreign key, CHECK, and NOT NULL constraints:
-- 1. INSERT: explicit tuple or query-driven bulk insert
INSERT INTO Department (DeptID, DeptName) VALUES (10, 'Computer Engineering');
INSERT INTO HonorsList (RollNo, Name)
SELECT RollNo, Name FROM Student WHERE GPA >= 3.80;
-- 2. UPDATE: modify existing rows matching WHERE (omit WHERE updates ALL rows!)
UPDATE Student
SET GPA = GPA + 0.05
WHERE DeptID = 10 AND GPA <= 3.95;
-- 3. DELETE: remove matching rows (TRUNCATE removes all rows without row logging)
DELETE FROM Student
WHERE Semester > 8;3.9 Views
A view is a virtual relation whose contents are defined dynamically by a stored SELECT query rather than stored physically on disk (unlike a materialized view).
- Purposes: (1) Security—hide sensitive columns like
SalaryorPhone; (2) Simplicity—encapsulate complex multi-table joins; (3) Logical Data Independence—preserve legacy interfaces when base tables are normalized or split. - Updatable Views: A view is generally updatable (
INSERT/UPDATE/DELETEpasses through to the base table) only if it is defined on a single base table with noDISTINCT,GROUP BY,HAVING, aggregate functions, or set operations. Views withWITH CHECK OPTIONreject updates that would cause modified rows to disappear from the view.
CREATE VIEW CSE_Honor_Students AS
SELECT RollNo, Name, GPA
FROM Student
WHERE DeptID = 10 AND GPA >= 3.50
WITH CHECK OPTION;
SELECT * FROM CSE_Honor_Students ORDER BY GPA DESC;
DROP VIEW CSE_Honor_Students;3.10 Triggers and stored procedures
| Aspect | Stored Procedure | Trigger |
|---|---|---|
| Definition | A named, precompiled block of SQL + procedural control statements stored inside the DBMS catalog. | A special stored block automatically fired by the DBMS in response to a specific data modification event. |
| Invocation | Explicitly invoked by an application or user via CALL proc_name(args). | Implicitly invoked on INSERT, UPDATE, or DELETE (BEFORE or AFTER, FOR EACH ROW or FOR EACH STATEMENT). |
| Parameters | Accepts IN, OUT, and INOUT parameters. | Takes no explicit arguments; accesses row changes via OLD and NEW transition variables. |
| Primary Use | Reusable business logic, batch updates, reduced network round-trips. | Auditing changes, enforcing complex cross-table integrity rules, maintaining derived summary values. |
-- Stored Procedure: promote a student's semester
CREATE PROCEDURE PromoteStudent(IN p_roll INT)
BEGIN
UPDATE Student
SET Semester = Semester + 1
WHERE RollNo = p_roll AND Semester < 8;
END;
-- Trigger: log salary changes into an audit table
CREATE TRIGGER AuditSalaryUpdate
AFTER UPDATE OF Salary ON Instructor
FOR EACH ROW
WHEN (NEW.Salary <> OLD.Salary)
BEGIN
INSERT INTO SalaryLog(InstID, OldSal, NewSal, ChangedAt)
VALUES (NEW.InstID, OLD.Salary, NEW.Salary, CURRENT_TIMESTAMP);
END;3.11 Privilege and roles management – GRANT and REVOKE statements
To protect data from unauthorized access, SQL Data Control Language (DCL) manages privileges (SELECT, INSERT, UPDATE, DELETE, REFERENCES, ALL PRIVILEGES) and roles (named collections of privileges assigned to groups of users).
GRANT: Gives specific privileges on a database object (table or view) to a user or role. AddingWITH GRANT OPTIONallows the recipient to pass that privilege onward to others.REVOKE: Withdraws previously granted privileges. UsingCASCADEalso revokes dependent privileges passed on viaWITH GRANT OPTION, whereasRESTRICTfails if dependent grants exist.
-- Create a role and assign privileges to it
CREATE ROLE ExamStaff;
GRANT SELECT, UPDATE (GPA) ON Student TO ExamStaff;
-- Assign the role to a user
GRANT ExamStaff TO user_kiran;
-- Grant direct privilege with delegation authority
GRANT SELECT ON Department TO user_maya WITH GRANT OPTION;
-- Revoke privilege (cascading any downstream grants)
REVOKE SELECT ON Department FROM user_maya CASCADE;
REVOKE ExamStaff FROM user_kiran;Worked Out Examples
3.1
Given the relational schema:
Book(BookID, Title, Author, Price)Member(MemID, Name, City)Borrow(MemID, BookID, IssueDate)
Write both Relational Algebra expressions and SQL queries for:
- Find the
TitleandAuthorof all books costing more than . - Find the
Nameof members living in'Kathmandu'who have borrowed at least one book by'Silberschatz'. - Find the
MemIDof members who have borrowed no books at all.
Query 1 (Selection and Projection):
- Relational Algebra:
- SQL:
SELECT Title, Author
FROM Book
WHERE Price > 500;Query 2 (Multi-table Join with Filtering):
- Relational Algebra:
- SQL:
SELECT DISTINCT M.Name
FROM Member M
JOIN Borrow BR ON M.MemID = BR.MemID
JOIN Book B ON BR.BookID = B.BookID
WHERE M.City = 'Kathmandu' AND B.Author = 'Silberschatz';Query 3 (Set Difference / NOT IN / EXCEPT):
- Relational Algebra:
- SQL:
SELECT MemID FROM Member
EXCEPT
SELECT MemID FROM Borrow;- /
SELECT Title, Author FROM Book WHERE Price > 500; - /
SELECT DISTINCT M.Name FROM Member M JOIN Borrow BR ... JOIN Book B ... - /
SELECT MemID FROM Member EXCEPT SELECT MemID FROM Borrow;
3.2
Consider the relation Sales(SaleID, Dept, Amount) with tuples: {(1, 'CS', 500), (2, 'CS', 700), (3, 'ECE', 450), (4, 'CS', 600), (5, 'ECE', 550), (6, 'CE', 300)}. Trace the exact output of the following SQL query:
SELECT Dept, COUNT(*) AS NumSales, SUM(Amount) AS TotalAmt, AVG(Amount) AS AvgAmt
FROM Sales
WHERE Amount >= 400
GROUP BY Dept
HAVING COUNT(*) >= 2
ORDER BY TotalAmt DESC;Applying FROM and WHERE Amount >= 400: Tuple (6, 'CE', 300) fails Amount >= 400 and is discarded immediately before grouping. The surviving rows are:
(1, 'CS', 500),(2, 'CS', 700),(4, 'CS', 600)(3, 'ECE', 450),(5, 'ECE', 550)
Grouping (GROUP BY Dept) and Computing Aggregates:
- Group
'CS'( rows):NumSales,TotalAmt,AvgAmt. - Group
'ECE'( rows):NumSales,TotalAmt,AvgAmt.
Applying HAVING COUNT(*) >= 2 and ORDER BY TotalAmt DESC: Both 'CS' () and 'ECE' () pass the HAVING filter. Sorting descending by TotalAmt places 'CS' () before 'ECE' ().
| Dept | NumSales | TotalAmt | AvgAmt |
|---|---|---|---|
| CS | 3 | 1800 | 600 |
| ECE | 2 | 1000 | 500 |
3.3
Given two relations and , compute the resulting tuples and row counts of:
- (Natural Join)
- on
- (Cartesian Product, row count only)
Computing the Natural Join (): The common attribute is . Match tuples where :
- Tuple matches both and in
(1, x, 10)and(1, x, 20). - Tuples and have no match for in ; has no match in .
Thus has tuples: {(1, x, 10), (1, x, 20)}.
Computing the Left Outer Join (): Retains all matching tuples from , plus the unmatched left tuples (2, y) and (3, z) padded with NULL for and :
(1, x, x, 10),(1, x, x, 20),(2, y, NULL, NULL),(3, z, NULL, NULL)tuples.
Computing the Cartesian Product Size (): Since and , tuples (each with attributes).
- ( tuples).
- ( tuples).
- tuples.
Exercises
Practice Exercises — Relational Query Languages
Differentiate between DDL, DML, and DCL in SQL with at least two example commands for each. Why is relational algebra called a procedural language while SQL is declarative?
DDL, DML, and DCL Definitions:
- DDL (Data Definition Language): Defines and modifies database structure/schemas (e.g.,
CREATE TABLE,ALTER TABLE,DROP TABLE,TRUNCATE). - DML (Data Manipulation Language): Retrieves and modifies data stored inside tables (e.g.,
SELECT,INSERT,UPDATE,DELETE). - DCL (Data Control Language): Controls user permissions and security access (e.g.,
GRANT,REVOKE).
Procedural vs. Declarative Query Languages:
- Relational Algebra (Procedural): The user explicitly specifies how to compute the answer by writing a sequence of step-by-step operations (, etc.) in a chosen order.
- SQL (Declarative / Non-Procedural): The user specifies what data is desired (
SELECT ... FROM ... WHERE ...), leaving the DBMS query optimizer free to choose the fastest physical execution plan.
DDL defines schema (CREATE, ALTER, DROP), DML manipulates data (SELECT, INSERT, UPDATE, DELETE), and DCL manages permissions (GRANT, REVOKE). Relational algebra is procedural (specifies operations and order), whereas SQL is declarative (specifies the desired result while the optimizer picks the execution strategy).
Given the schema Employee(EmpID, Name, Dept, Salary) and Project(ProjID, ProjName, Dept):
- Write a relational algebra expression to find the
Nameof employees in'IT'earning more than . - Write an SQL query using a nested correlated subquery (or
EXISTS) to find departments that currently have no assigned projects.
Relational Algebra Expression: Apply selection for both conditions, followed by projection onto Name:
SQL Query Using NOT EXISTS: Find distinct departments in Employee for which no matching Dept exists in Project:
SELECT DISTINCT E.Dept
FROM Employee E
WHERE NOT EXISTS (
SELECT 1 FROM Project P WHERE P.Dept = E.Dept
);SELECT DISTINCT E.Dept FROM Employee E WHERE NOT EXISTS (SELECT 1 FROM Project P WHERE P.Dept = E.Dept);
Compare Inner Join, Left Outer Join, Right Outer Join, and Full Outer Join with a concrete two-table example, and explain the difference between WHERE and HAVING clauses in SQL.
Join Types Comparison: Suppose Dept(DNo, DName) has {(1, 'CS'), (2, 'Civil')} and Emp(EID, DNo) has {(10, 1), (11, NULL)}:
- Inner Join: Returns only matching pairs:
{(10, 1, 'CS')}( row). - Left Outer Join (
Emp LEFT JOIN Dept): Keeps unmatched left rows ((11, NULL, NULL)), returning rows. - Right Outer Join (
Emp RIGHT JOIN Dept): Keeps unmatched right rows ((NULL, 2, 'Civil')), returning rows. - Full Outer Join (
Emp FULL OUTER JOIN Dept): Keeps unmatched rows from both sides, returning rows.
WHERE vs. HAVING:
WHEREfilters individual tuples beforeGROUP BYgrouping occurs and cannot use aggregate functions (COUNT,SUM,AVG).HAVINGfilters entire groups afterGROUP BYand aggregate calculations have been performed, and typically contains aggregate conditions (e.g.,HAVING AVG(Salary) > 60000).
Inner Join keeps only matched rows; Left/Right/Full Outer Joins preserve unmatched rows from the left, right, or both tables padded with NULLs. WHERE filters individual rows before grouping, whereas HAVING filters grouped aggregates after GROUP BY.
What is a view in SQL, and what conditions must hold for a view to be updatable? Contrast a trigger with a stored procedure and show how GRANT and REVOKE manage user privileges.
Views and Updatability:
- A view is a virtual table computed dynamically from a stored
SELECTquery (CREATE VIEW name AS SELECT ...). It improves security (column/row hiding) and logical data independence. - A view is generally updatable only when it draws from a single base relation without
DISTINCT,GROUP BY,HAVING, aggregate functions, set operations (UNION), or computed expressions on the updated column.
Triggers vs. Stored Procedures and DCL:
- A stored procedure is executed explicitly (
CALL proc(...)) and acceptsIN/OUTparameters, whereas a trigger fires automatically onINSERT,UPDATE, orDELETEevents usingOLD/NEWrow values. GRANT SELECT, INSERT ON Student TO role_ta;assigns permissions (optionallyWITH GRANT OPTION), andREVOKE INSERT ON Student FROM role_ta CASCADE;removes them along with dependent delegated grants.
A view is a virtual query-defined table (updatable when derived from a single base table without aggregates/grouping/set-ops). A stored procedure is called explicitly while a trigger fires automatically on DML events; GRANT assigns privileges/roles and REVOKE withdraws them.
Let relation have tuples and relation have tuples. Suppose and are union-compatible and share exactly tuple in common (). Compute:
- The exact number of tuples in (Cartesian product).
- The exact number of tuples in (SQL
UNION, duplicate-eliminating) vs.UNION ALL. - The exact number of tuples in (SQL
EXCEPT).
Cartesian Product (): Every tuple in is paired with every tuple in :
Union ( vs. UNION ALL) and Set Difference ():
- SQL
UNION(set union): Eliminates the shared duplicate tuple:
- SQL
UNION ALL(bag union): Retains all tuples from both inputs:
- SQL
EXCEPT(): Removes the shared tuple from :
- tuples.
- (
UNION) tuples;UNION ALLtuples. - (
EXCEPT) tuples.