Database Principles and Applications
Lecture 5: Compound Operators & SQL
Dr Shenkai Gu
Copyright © 2024 Dr Shenkai Gu. All rights reserved.
Compound operator: Intersection (⋂)
• In addition to the basic operators, there are several additional
“compound operators”
• These add no computational power to the language, but are useful
shorthands.
• Can be expressed solely with the basic ops.
• Intersection takes two input relations, which must be union-
compatible.
• Q: How to express it using basic operators?
R⋂S = R − R − S
Database Principles and Applications - Lecture 5: SQL – Compound Operators and SQL 2
Compound operator: Join (⋈)
• Joins are compound operators involving cross-product, selection,
and (sometimes) projection.
• Most common type of join is a “natural join” (often just called
“join”).
• R⋈S conceptually is:
• Compute R × S
• Select rows where attributes that appear in both relations have equal
values
• Project all unique attributes and one copy of each of the common ones
• Note: Usually done much more efficiently than this.
Database Principles and Applications - Lecture 5: SQL – Compound Operators and SQL 3
Other types of joins
• Condition Join
• R ⋈c S = 𝜎c R × S
• Result schema: same as that of cross-product
• May have fewer tuples than cross-product and might be able to compute
more efficiently
• a.k.a. “theta-join”
• Equi-Join
• A special case of condition join where the condition c contains only
conjunction of equalities
• Result schema: similar to cross-product, but only one copy of fields for
which equality is specified.
• Natural Join
• Equi-Join on all common fields.
Database Principles and Applications - Lecture 5: SQL – Compound Operators and SQL 4
Condition Join example
sid sname rating age (sid) sname rating age (sid) bid day
22 Alice 7 29 22 Alice 7 29 22 1001 24/07/2017
31 Bob 8 25 22 Alice 7 29 58 1003 11/05/2018 √
58 Charlie 10 31 31 Bob 8 25 22 1001 24/07/2017
TABLE: S1 31 Bob 8 25 58 1003 11/05/2018 √
58 Charlie 10 31 22 1001 24/07/2017
sid bid day 58 Charlie 10 31 58 1003 11/05/2018
22 1001 24/07/2017 𝐒𝟏 × 𝐑𝟏
58 1003 11/05/2018
TABLE: R1
(sid) sname rating age (sid) bid day
√ Compute R×S
22 Alice 7 29 58 1003 11/05/2018
√ Select rows
31 Bob 8 25 58 1003 11/05/2018
√ Remove duplicates
S1 ⋈[Link]<[Link] R1
Database Principles and Applications - Lecture 5: SQL – Compound Operators and SQL 5
Equi-Join example
sid sname rating age (sid) sname rating age (sid) bid day
22 Alice 7 29 22 Alice 7 29 22 1001 24/07/2017 √
31 Bob 8 25 22 Alice 7 29 58 1003 11/05/2018
58 Charlie 10 31 31 Bob 8 25 22 1001 24/07/2017
TABLE: S1 31 Bob 8 25 58 1003 11/05/2018
58 Charlie 10 31 22 1001 24/07/2017
sid bid day 58 Charlie 10 31 58 1003 11/05/2018 √
22 1001 24/07/2017 𝐒𝟏 × 𝐑𝟏
58 1003 11/05/2018
TABLE: R1
sid sname rating age bid day
√ Compute R×S
22 Alice 7 29 1001 24/07/2017
√ Select rows
58 Charlie 10 31 1003 11/05/2018
√ Remove duplicates
√ Retain one field
S1 ⋈sid R1
Database Principles and Applications - Lecture 5: SQL – Compound Operators and SQL 6
Summary
• Relational Algebra
• A small set of operators mapping relations to relations
• You specify the explicit order of operations
• A closed set of operators! Can mix and match.
• Given a query, how to mix and match the relational algebra operators to
answer it
• Basic operations
• 𝜎
• 𝜋
• ×
• −
• ⋃
• Important compound operations
• ⋂/⋈/𝜌
Database Principles and Applications - Lecture 5: SQL – Compound Operators and SQL 7
Homework
• Imaging you have the following tables in a database:
• Boats (bid, bname, color)
• Sailors (sid, sname, rating, age)
• Reserves (sid, bid, day)
• Using relational algebra to complete the following tasks:
• Find names of sailors who reserved boat #1003
• Find names of sailors who reserved a red boat
• Find sailors who reserved a red boat or a green boat
• Note: you can use any combination of the relational algebra
Database Principles and Applications - Lecture 5: SQL – Compound Operators and SQL 8
Query optimization
Relational Algebra
Query 1
Relational Algebra
Query 2
SQL Query
…
Relational Algebra
Query n
DBMS picks
the cheapest one
Database Principles and Applications - Lecture 5: SQL – Compound Operators and SQL 9
Relational query languages
• Two sublanguages:
• DDL – Data Definition Language
• Define and modify schema (at all 3 levels)
• DML – Data Manipulation Language
• Queries can be written intuitively
• DBMS is responsible for efficient evaluation.
• The key: precise semantics for relational queries.
• Optimizer can re-order operations, without affecting query answer.
• Choices driven by cost model:
• How many disk accesses?
• How much CPU?
• The SQL query language
• The most widely used relational query language.
• Standardized (although most systems add their own “special sauce”)
Database Principles and Applications - Lecture 5: SQL – Compound Operators and SQL 10
Review: SQL DDL
CREATE TABLE Boats (bid INTEGER, bid bname color
bname CHAR(20), 1001 Nemo Red
color CHAR(10), 1002 Whale Blue
1003 Shimp Red
PRIMARY KEY bid);
TABLE: Boats
CREATE TABLE Sailors (sid INTEGER,
sname CHAR(20),
sid sname rating age
rating INTEGER, 1 Alice 7 29
age INTEGER, 2 Bob 2 25
PRIMARY KEY sid); 3 Charlie 8 31
CREATE TABLE Reserves (sid INTEGER, TABLE: Sailors
bid INTEGER,
day DATE, sid bid day
1 1001 24/07/2017
PRIMARY KEY (sid, bid),
2 1003 11/05/2018
FOREIGN KEY sid REFERENCES Sailors,
TABLE: Reserves
FOREIGN KEY bid REFERENCES Boats);
Database Principles and Applications - Lecture 5: SQL – Compound Operators and SQL 11
Basic SQL query
DISTINCT: optional keyword indicating
answer should not contain duplicates.
In SQL, default is that duplicates are NOT target-list : A list of attributes
eliminated! (Result is called a “multiset”) of tables in relation-list
SELECT [DISTINCT] target-list
FROM relation-list
[WHERE qualification]
qualification : Comparisons combined relation-list : A list of relation
using AND, OR and NOT. Comparisons are names, possibly with a range-variable
Attr op const or Attr1 op Attr2, where op is after each name.
one of =, <, >, != etc.
Database Principles and Applications - Lecture 5: SQL – Compound Operators and SQL 12
Query semantics
SELECT [DISTINCT] target-list
FROM relation-list
[WHERE qualification]
• FROM: compute cross product of tables.
• WHERE (optional): check conditions, discard tuples that fail.
• SELECT: delete unwanted attributes.
• DISTINCT (optional): eliminate duplicate rows.
• Note: Probably the least efficient way to compute a query!
• Query optimizer will find more efficient ways to get the same answer.
Database Principles and Applications - Lecture 5: SQL – Compound Operators and SQL 13
An example
• Find all 18-year-old sailors: bid bname color
SELECT * SELECT * 1001 Nemo Red
FROM Sailors S FROM Sailor 1002 Whale Blue
WHERE [Link]=18 WHERE age=18 1003 Shimp Red
• To find just names and ratings, replace the TABLE: Boats
first line with:
sid sname rating age
SELECT [Link], [Link]
1 Alice 7 29
• Query multiple relations: 2 Bob 2 25
3 Charlie 8 31
SELECT [Link]
TABLE: Sailors
FROM Sailors S, Reserves R
WHERE [Link]=[Link] AND [Link]=1002 sid bid day
• About range variables 1 1001 24/07/2017
• Needed when ambiguity could arise. e.g., same 2 1003 11/05/2018
table used multiple times in FROM (“self-join”) TABLE: Reserves
Database Principles and Applications - Lecture 5: SQL – Compound Operators and SQL 14
Another example
• Find sailors who have reserved at least one bid bname color
boat 1001 Nemo Red
1002 Whale Blue
SELECT [DISTINCT]
* target-list
1003 Shimp Red
FROM relation-list
Sailors S, Reserves R TABLE: Boats
WHERE qualification
[Link]=[Link]
sid sname rating age
1 Alice 7 29
• Would adding DISTINCT to this query 2 Bob 2 25
makes a difference? 3 Charlie 8 31
TABLE: Sailors
• What would happen if we replace * with sid bid day
[Link] in the SELECT clause? 1 1001 24/07/2017
• Would adding DISTINCT to this variant of the 2 1003 11/05/2018
query makes a difference? TABLE: Reserves
Database Principles and Applications - Lecture 5: SQL – Compound Operators and SQL 15
Dr Shenkai Gu | [Link]@[Link]
Contents of these slides are solely for the purpose of
study and research by the course audiences.
No part of the slides, including the slide template, may
be reproduced or used in any manner whatsoever without
the express written permission of the author.
Thank you!
Copyright © 2024 Dr Shenkai Gu. All rights reserved.