Nested queries

SQL language: basics

Nested queries
➢Introduction
➢The IN operator
➢The NOT IN operator
➢The tuple constructor
➢The EXISTS operator
➢The NOT EXISTS operator
➢Correlation among queries
➢The division operation
Introduction
Nested queries
Introduction
• A nested query is a SELECT statement contained within another query
• query nesting allows decomposing a complex problem into simpler
subproblems
• SELECT statements may be introduced
• within a predicate in the WHERE clause
• within a predicate in the HAVING clause
• in the FROM clause
 Example database: Supply-Product
Foreign Foreign
P PId PName Color Size Store key key

P1 Jumper Red 40 London

SP
P2 Jeans Green 48 Paris SId PId Qty
P3 Blouse Blue 48 Rome S1 P1 300
P4 Blouse Blue 44 London S1 P2 200
P5 Skirt Blue 40 Paris S1 P3 400
S1 P4 200
S1 P5 100
S SId SName #Employees City S2 P1 300
S1 Smith 20 London S2 P2 400
S2 Jones 10 Paris S3 P2 200
S3 Blake 30 Paris S4 P3 200
S4 Clark 20 London S4 P4 300
S5 Adams 30 Athens S4 P5 400
5
Nested queries (no.1)
• Find the codes of the suppliers that are based in the same city as S1

• By using a formulation with nested queries, the problem may be

decomposed into two subproblems
• city of supplier S1
• codes of the suppliers based in the same city
Nested queries (no.1)
• Find the codes of the suppliers that are based in the same city as S1

IDs of the suppliers SELECT SId

based in the same FROM S
city as S1 WHERE City = (SELECT City
City of
FROM S
supplier S1
WHERE SId=‘S1’);

• The ‘=’ operator may be used only if it is known in advance that the
inner SELECT statement always returns a single value
• An equivalent formulation may be defined using a join operation
Equivalent formulation
• The equivalent formulation with join is characterized by
• a FROM clause including all the tables referenced by the FROM clauses of
each SELECT statement
• appropriate join conditions in the WHERE clause
• if needed selection predicates added in the WHERE clause
FROM clause (no.1)
• Find the codes of the suppliers that are based in the same city as S1

SELECT SId
SX
FROM S
WHERE City = (SELECT City SY
FROM S
WHERE SId=‘S1’);
FROM clause (no.1)
• Find the codes of the suppliers that are based in the same city as S1

SELECT ...
FROM S AS SX, S AS SY
...
Join condition (no.1)
• Find the codes of the suppliers that are based in the same city as S1

SELECT SId
FROM S
WHERE City = (SELECT City
FROM S
WHERE SId=‘S1’);
Join condition (no.1)
• Find the codes of the suppliers that are based in the same city as S1

SELECT ...
FROM S AS SX, S AS SY
WHERE [Link]=[Link]
...
Selection predicate (no.1)
• Find the codes of the suppliers that are based in the same city as S1

SELECT SId
FROM S
WHERE City = (SELECT City
FROM S
WHERE SId=‘S1’);
SELECT clause (no.1)
• Find the codes of the suppliers that are based in the same city as S1

SELECT [Link]
FROM S AS SX, S AS SY
WHERE [Link]=[Link] AND
[Link]=‘S1’;
Equivalent formulation (no.2)
• Find the codes of the suppliers whose number of employees is
smaller than the maximum number of employees

SELECT SId
FROM S
WHERE #Employees < (SELECT MAX(#Employees)
FROM S);

• An equivalent formulation with join is not possible

 • It expresses the concept of membership to a set of values

AttributeName IN (NestedQuery)

• It allows to write a query by

• breaking down the problem into subproblems
• following a "bottom-up" process
IN OPERATOR • The nested query can be replaced with a list of values
• The equivalent formulation with the join is characterized by
• FROM clause containing the tables referenced in the FROM of all
SELECTs
• appropriate join conditions in the WHERE clause
• any selection predicates added in the WHERE clause

16
The IN operator (no.1)
• Find the names of the suppliers who supply product P2

• Decomposition of the problem into two subproblems

• codes of the suppliers of product P2
• names of the suppliers with such codes
The IN operator (no.1)
• Find the names of the suppliers who supply product P2

SP
SId PId Qty
S1 P1 300
(SELECT SId Codes
S1 P2 200
of the
S1 P3 400 SId FROM SP
S1 P4 200 S1 suppliers
WHERE PId=‘P2’)
S1 P5 100 S2 of P2
S1 P6 100 S3
S2 P1 300
S2 P2 400
S3 P2 200
S4 P3 200
S4 P4 300
S4 P5 400
 The IN operator (no.1)
• Find the names of the suppliers who supply product P2
S
SId SName #Employees City
S1 Smith 20 London Set membership
SELECT SName
S2 Jones 10 Paris FROM S
S3 Blake 30 Paris Codes
WHERE SId IN (SELECT SId
S4 Clark 20 London of the
FROM SP
S5 Adams 30 Athens suppliers
WHERE PId=‘P2’); of P2 SId
S1
S2
S3

19
Example 1: Equivalent Formulation with Join
• Find the names of the suppliers who supply product P2

IN JOIN
SELECT SName SELECT SName
FROM S FROM S, SP
WHERE SId IN (SELECT SId WHERE [Link]=[Link]
FROM SP
AND PId=‘P2’;
WHERE PId=‘P2’);

20
Example 2: IN Operator
• Find the name of suppliers who provide at least one red product

SELECT SName
FROM S
WHERE SId IN (SELECT SId
FROM SP Red Supplier
WHERE PId IN (SELECT PId Product names
Supplier with
FROM P Red Product those
Codes
WHERE Color=‘Red’)); Codes codes

21
 Example 2: Equivalent formulation
• Find the name of suppliers who provide at least one red product

IN JOIN
SELECT SName
SELECT SName FROM S,SP 1
1
FROM S WHERE [Link]=[Link]
WHERE SId IN
(SELECT SId
FROM SP
WHERE PId
IN (SELECT PId
FROM P
WHERE Color=‘Red’)); 22
 Example 2: Equivalent formulation
• Find the name of suppliers who provide at least one red product

IN JOIN
SELECT SName
SELECT SName FROM S, SP, P 2

FROM S WHERE [Link]=[Link] AND

WHERE SId IN [Link]= [Link]
(SELECT SId
FROM SP 2

WHERE PId
IN (SELECT PId
FROM P
WHERE Color=‘Red’)); 23
 Example 2: Equivalent formulation
• Find the name of suppliers who provide at least one red product

IN JOIN
SELECT SName
SELECT SName FROM S, SP, P
FROM S WHERE [Link]=[Link] AND
WHERE SId IN [Link]= [Link] AND 3

(SELECT SId Color = ‘Red’

FROM SP
WHERE PId
IN (SELECT PId
3
FROM P
WHERE Color=‘Red’)); 24
 • It expresses the concept of exclusion from a set of values

AttributeName NOT IN (NestedQuery)

NOT IN
OPERATOR • It requires the identification of an appropriate set to be
excluded defined by
• a nested query
• a list of values
• There is no equivalent formulation with join

48
Example 1: Concept of exclusion
• Find the names of the suppliers who do not supply product P2
• it is not possible to express the query with a join operation

SELECT SName
FROM S, SP
WHERE [Link] = [Link]
AND PId <>'P2';
Wrong solution
• The query matches the request:
• Find the name of suppliers who provide at least one product other than P2

49
Wrong solution (no.1)
• Find the names of the suppliers who do not supply product P2
SP
S SId PId Qty
SId SName #Employees City
S1 P1 300
S1 Smith 20 London
S1 P2 200
S2 Jones 10 Paris
S1 P3 400
S3 Blake 30 Paris
S1 P4 200
S4 Clark 20 London
S1 P5 100
S5 Adams 30 Athens
S2 P1 300
S2 P2 400
R
S3 P2 200
SName S4 P3 200
Smith S4 P4 300
Jones S4 P5 400
Clark
The NOT IN operator (no.1)
• Find the names of the suppliers who do not supply product P2
• Set to be excluded
• suppliers of product P2

SELECT SName
FROM S
WHERE SId NOT IN (SELECT SId
FROM SP Codes of the suppliers
who supply P2
WHERE PId=‘P2’);
does not belong to
NOT IN and relational algebra (no.1)
• Find the names of the suppliers who do not supply product P2

pSName
pSName

- S p

pSId pSId
S sPId=‘P2’
sPId=‘P2’
S
SP
SP p: [Link]=[Link]
The NOT IN operator (no.2)
• Find the names of the suppliers who only supply product P2

Find the names of the suppliers of P2 who

have never supplied products other than P2

• Set to be excluded
• suppliers of products other than P2
The NOT IN operator (no.2)
• Find the names of the suppliers who only supply product P2

SELECT SName
FROM S, SP
WHERE [Link] NOT IN (SELECT SId Codes of the suppliers
FROM SP who supply
at least one product
WHERE PId<>‘P2’) other than P2
AND [Link]=[Link];
Alternative solution (no.2)
• Find the names of the suppliers who only supply product P2

SELECT SName
FROM S
WHERE [Link] NOT IN (SELECT SId Codes of the suppliers
FROM SP who supply
at least one product
WHERE PId<>‘P2’) other than P2
AND [Link] IN (SELECT SId
FROM SP);
The NOT IN operator (no.3)
• Find the names of the suppliers who do not supply any red products
• Set to be excluded:
• suppliers of red products, identified by their codes

SELECT SName
FROM S
WHERE SId NOT IN
(SELECT SId
FROM SP
Codes of the
suppliers of at least one
WHERE PId IN (SELECT PId
red product FROM P
WHERE Color=‘Red’));
Wrong alternative (no.3)
• Find the names of the suppliers who do not supply any red products
SELECT SName
FROM S
WHERE SId IN
(SELECT SId
Codes of the
FROM SP
suppliers of WHERE PId NOT IN (SELECT PId
non-red FROM P
products
WHERE Color=‘Red’));

• The set of elements to be excluded is incorrect

Wrong alternative (no.3)
• Find the names of the suppliers who do not supply any red products
SELECT SName
FROM S
WHERE SId IN
(SELECT SId
Codes of the
FROM SP
suppliers of WHERE PId NOT IN (SELECT PId
non-red FROM P
products
WHERE Color=‘Red’));

• The set of elements to be excluded is incorrect

Wrong alternative (no.3)
• Find the names of the suppliers who do not supply any red products
P SP
PId PName Color Size Store
P1 Jumper Red 40 London SId PId Qty
P2 Jeans Green 48 Paris S1 P1 300
P3 Blouse Blue 48 Rome S1 P2 200
P4 Blouse Blue 44 London S1 P3 400
P5 Skirt Blue 40 Paris S1 P4 200
S1 P5 100
S2 P1 300
S SId SName #Employees City S2 P2 400
S1 Smith 20 London S3 P2 200
S2 Jones 10 Paris S4 P3 200
S3 Blake 30 Paris S4 P4 300
S4 Clark 20 London S4 P5 400
S5 Adams 30 Athens
59
 • It allows defining a temporary structure for a tuple
• the attributes belonging to it must be listed within ()

TUPLE (AttributeName1, AttributeName2, ...)

CONSTRUCTOR
• It enhances the expressive power of the IN and NOT
IN operators

60
Example (no.1)

TRIP (TId, StartingPlace, Destination,

DepartureTime, ArrivalTime)

• Find the pairs of starting places and destinations for which none of
the trips lasts more than 2 hours
Example (no.1)

TRIP (TId, StartingPlace, Destination,

DepartureTime, ArrivalTime)

• Find the pairs of starting places and destinations for which none of
the trips lasts more than 2 hours
SELECT StartingPlace, Destination
FROM TRIP
WHERE (StartingPlace, Destination) NOT IN
(SELECT StartingPlace, Destination
Tuple FROM TRIP
constructor WHERE ArrivalTime-DepartureTime>2);
 • The EXISTS operator admits a nested query as a
parameter and returns
• true if the nested query returns a non-empty set (that is, it
returns at least one tuple)
• false if the internal query returns the empty set (i.e., no
EXISTS tuple)

OPERATOR • In the internal query of EXISTS, the SELECT clause is

mandatory, but irrelevant, because the attributes are
not displayed
• The correlation condition ties the execution of the
internal query to the values of the attributes of the
current tuple in the external query

63
The EXISTS operator (no.1)
• Find the names of the suppliers of product P2

Find the names of the suppliers for which there

exists a product supply for P2
Correlation condition (no.1)
• Find the names of the suppliers of product P2

SELECT SName
FROM S
WHERE EXISTS (SELECT *
FROM SP
WHERE PId=‘P2’
AND [Link]=[Link] );

Correlation condition

• The correlation condition ties the execution of the internal query to

the values of the attributes of the current tuple in the external query
How EXISTS works (no.1)
• Find the names of the suppliers of product P2
SP
S SId SName #Employees City
S1 Smith 20 London SId PId Qty
S2 Jones 10 Paris S1 P1 300
S3 Blake 30 Paris S1 P2 200
S4 Clark 20 London S1 P3 400
S5 Adams 30 Athens S1 P4 200
S1 P5 100
SELECT * S2 P1 300
FROM SP S2 P2 400
WHERE PId=‘P2’ S3 P2 200
S4 P3 200
AND [Link]=‘S1’
S4 P4 300
Value of SId in the S4 P5 400
current line of table S
How EXISTS works (no.1)
• Find the names of the suppliers of product P2
SP
S SId SName #Employees City
S1 Smith 20 London SId PId Qty
S2 Jones 10 Paris S1 P1 300
S3 Blake 30 Paris S1 P2 200
S4 Clark 20 London S1 P3 400
S5 Adams 30 Athens S1 P4 200
S1 P5 100
S2 P1 300
• The predicate including EXISTS is true S2 P2 400
for S1 since there exists a supply for S3 P2 200
P2 by S1 S4 P3 200
• S1 belongs to the result of the query S4 P4 300
S4 P5 400
How EXISTS works (no.1)
• Find the names of the suppliers of product P2
SP
S SId SName #Employees City
S1 Smith 20 London SId PId Qty
S2 Jones 10 Paris S1 P1 300
S3 Blake 30 Paris S1 P2 200
S4 Clark 20 London S1 P3 400
S5 Adams 30 Athens S1 P4 200
S1 P5 100
S2 P1 300
• The predicate including EXISTS is S2 P2 400
false for S4 since there does not exist S3 P2 200
a supply for P2 by S4 S4 P3 200
• S4 does not belong to the result of S4 P4 300
the query S4 P5 400
Result of the query (no.1)
• Find the names of the suppliers of product P2

R
SName
Smith
Jones
Blake
Scope of attributes
• A nested query may reference attributes defined within outer queries
• A query may not reference attributes defined
• within a nested query at an inner level
• within a different query at the same level
 • The EXISTS operator admits a nested query as a
parameter and returns
• true if the nested query returns an empty set (i.e., no
tuple)
• false if the nested query returns a non-empty set (that is,
NOT EXISTS it returns at least one tuple)

OPERATOR • In the internal query of EXISTS, the SELECT clause is

mandatory, but irrelevant, because the attributes are
not displayed
• The correlation condition ties the execution of the
internal query to the values of the attributes of the
current tuple in the external query

71
The NOT EXISTS operator (no.1)
• Find the names of the suppliers that do not supply product P2

Find the names of the suppliers for which

there does not exist a product supply for P2
The NOT EXISTS operator (no.1)
• Find the names of the suppliers who do not supply product P2
SELECT SName
FROM S
WHERE NOT EXISTS (SELECT *
FROM SP
WHERE PId=‘P2’
AND [Link]=[Link] );
Correlation condition

• The correlation condition ties the execution of the internal query to

the values of the attributes of the current tuple in the external query
How NOT EXISTS works (no.1)
• Find the names of the suppliers who do not supply product P2
SP
S SId SName #Employees City
S1 Smith 20 London SId PId Qty
S2 Jones 10 Paris S1 P1 300
S3 Blake 30 Paris S1 P2 200
S4 Clark 20 London S1 P3 400
S5 Adams 30 Athens S1 P4 200
S1 P5 100
SELECT * S2 P1 300
FROM SP S2 P2 400
WHERE PId=‘P2’ S3 P2 200
S4 P3 200
AND [Link]=‘S1’
S4 P4 300
Value of SId in the S4 P5 400
current line of table S
How NOT EXISTS works (no.1)
• Find the names of the suppliers who do not supply product P2
SP
S SId SName #Employees City
S1 Smith 20 London SId PId Qty
S2 Jones 10 Paris S1 P1 300
S3 Blake 30 Paris S1 P2 200
S4 Clark 20 London S1 P3 400
S5 Adams 30 Athens S1 P4 200
S1 P5 100
S2 P1 300
• The predicate including NOT EXISTS S2 P2 400
is false for S1 since there exists a S3 P2 200
supply for P2 by S1 S4 P3 200
• S1 does not belong to the result of S4 P4 300
the query S4 P5 400
How NOT EXISTS works (no.1)
• Find the names of the suppliers who do not supply product P2
SP
S SId SName #Employees City
S1 Smith 20 London SId PId Qty
S2 Jones 10 Paris S1 P1 300
S3 Blake 30 Paris S1 P2 200
S4 Clark 20 London S1 P3 400
S5 Adams 30 Athens S1 P4 200
S1 P5 100
S2 P1 300
• The predicate including NOT EXISTS S2 P2 400
is true for S4 since there does not S3 P2 200
exist a supply for P2 by S4 S4 P3 200
• S4 does belong to the result of the S4 P4 300
query S4 P5 400
How NOT EXISTS works (no.1)
• Find the names of the suppliers who do not supply product P2
SP
S SId SName #Employees City
S1 Smith 20 London SId PId Qty
S2 Jones 10 Paris S1 P1 300
S3 Blake 30 Paris S1 P2 200
S4 Clark 20 London S1 P3 400
S5 Adams 30 Athens S1 P4 200
S1 P5 100
S2 P1 300
• The predicate including NOT EXISTS S2 P2 400
is true for S5 since there exists a S3 P2 200
supply for P2 by S5 S4 P3 200
• S5 does belong to the result of the S4 P4 300
query S4 P5 400
Result of the query (no.1)
• Find the names of the suppliers who do not supply product P2

R
SName
Clark
Adams
 • It may be required to bind the computation of a
nested query to the value(s) of one or more
attributes in an outer query
• the binding is expressed by one or more correlation
conditions
CORRELATION • A correlation condition
• must be specified in the WHERE clause of the nested
BETWEEN query that requires it
QUERIES • is a predicate that binds some attributes of tables
appearing in the nested query’s FROM clause to attributes
of tables appearing in the FROM clause of outer queries
• Correlation conditions may not be expressed
• within queries at the same nesting level
• with references to attributes of a table appearing in the
FROM clause of a nested query

79
Correlation among queries (no.1)
• For each product, find the code of the supplier who supplies the
highest quantity

SELECT PId, SId

FROM SP AS SPX
WHERE Qty = (... Maximum
quantity
for the current
) product
Correlation among queries (no.1)
• For each product, find the code of the supplier who supplies the
highest quantity

SELECT PId, SId

FROM SP AS SPX
WHERE Qty = (SELECT MAX(Qty)
Maximum
FROM SP AS SPY quantity
... )
Correlation among queries (no.1)
• For each product, find the code of the supplier who supplies the
highest quantity

SELECT PId, SId

FROM SP AS SPX
Maximum
WHERE Qty = (SELECT MAX(Qty)
quantity
FROM SP AS SPY for the current
WHERE [Link]=[Link]); product
Correlation condition
Correlation among queries (no.2)
TRIP (TId, StartingPlace, Destination,
DepartureTime, ArrivalTime)

• Find the codes of the trips whose duration is lower than the average
duration of the trips on the same route (i.e., same starting place and
destination)

SELECT TId
FROM TRIP AS TA
WHERE ArrivalTime-DepartureTime < (... Average
duration
of trips
on the current
) route
Correlation among queries (no.2)
TRIP (TId, StartingPlace, Destination,
DepartureTime, ArrivalTime)
• Find the codes of the trips whose duration is lower than the average
duration of the trips on the same route (i.e., same starting place and
destination)

SELECT TId
FROM TRIP AS TA
WHERE ArrivalTime-DepartureTime <
(SELECT AVG(ArrivalTime-DepartureTime) Average
FROM TRIP AS TB duration
... ) of trips
Correlation among queries (no.2)
TRIP (TId, StartingPlace, Destination,
DepartureTime, ArrivalTime)

• Find the codes of the trips whose duration is lower than the average
duration of the trips on the same route (i.e., same starting place and
destination)

SELECT TId
FROM TRIP AS TA
WHERE ArrivalTime-DepartureTime <
(SELECT AVG(ArrivalTime-DepartureTime)
FROM TRIP AS TB Correlation conditions
WHERE [Link]=[Link]
AND [Link]=[Link]);
 DIVISION • In SQL, the division operation can be performed
using the COUNT operator, to verify that all the
OPERATOR elements of interest belong to the reference set

88
The division operation (no.1)
• Find the codes of the suppliers who supply all products
• In relational algebra we must use the division operator

pSId,PId pPId

SP P
Division in SQL (no.1)
• Find the codes of the suppliers who supply all products

• Remark
• all products that may be supplied are listed in table P

• a supplier is supplying all products if he or she is supplying a number of

distinct products equal to the cardinality of P
Division in SQL (no.1)
• Find the codes of the suppliers who supply all products

SELECT COUNT(*) Total

number
FROM P
of products
 Division in SQL (no.1)
• Find the codes of the suppliers who supply all products

SELECT SId
For each supplier, FROM SP
total number of GROUP BY SId
products supplied Total
HAVING COUNT(*) = (SELECT COUNT(*)
number
FROM P) of products
 Division in SQL (no.1)
• Find the codes of the suppliers who supply all products

SP(SID, PID, Qty)

SELECT SId
For each supplier, FROM SP
total number of GROUP BY SId
products supplied Total
HAVING COUNT(*) = (SELECT COUNT(*) number
FROM P) of products
 Division in SQL (no.1) – Different SP TABLE
• Find the codes of the suppliers who supply all products

SP(SID, PID, Date, Qty)

SELECT SId
For each supplier, FROM SP
total number of GROUP BY SId
products supplied Total
HAVING COUNT(DISTINCT PID)= (SELECT COUNT(*) number
FROM P); of products
Division in SQL: procedure (no.2)
• Find the codes of the suppliers who supply at least all of the products
supplied by supplier S2
• We must count
• the number of products supplied by S2
• the number of products supplied both by an arbitrary supplier and by S2
• The two counts must be equal
Division in SQL (no.2)
• Find the codes of the suppliers who supply at least all of the products
supplied by supplier S2

SELECT COUNT(*) Number of

FROM SP products
WHERE SId=‘S2’ supplied by S2
 Division in SQL (no.2)
• Find the codes of the suppliers who supply at least all of the products
supplied by supplier S2

SELECT SId
FROM SP
For each supplier, WHERE PId IN (SELECT PId
the total number of Products
products supplied, FROM SP supplied by S2
including only the WHERE SId=‘S2’)
products supplied by GROUP BY SId
S2
HAVING COUNT(*)=(SELECT COUNT(*)
Number
FROM SP of products
WHERE SId=‘S2’); supplied by S2