15SELECT-5

SELECT statement (5)

Outline

Nested queries
Correlated nested queries

A nested query is a query, that has another query embedded in its WHERE or SELECT or FROM clauses.

Implementation of nested queries allows for decomposition of complex queries into a series of simple queries nested one in another. For example, assume, that a selection condition: CONDITION 2 is applied to a relational table: TABLE 2, see a diagram in the present slide. Projection of the results on a column: COLUMN 1, provides the values in a COLUMN 1 of relational table: TABLE 2, that satisfy CONDITION 2. In the next step, a set of values obtained from the first SELECT statement is used in a selection condition applied to a relational table: TABLE 1. Then, there is no need to join the relational tables: TABLE 1 and TABLE 2 to select from: TABLE 1 all rows that belongs to the results selected from a relational table: TABLE 2.

A nested SELECT statement implements a query, that "finds the rows from a relational table: TABLE 1 such that a value in a column: COLUMN 1, is included in the values from COLUMN 1 in a table: TABLE 2, in the rows that satisfy a condition: Condition 2.

A schema explaining how a nested query is constructed is given in the present slide. Implementation of nested queries always starts from the implementation of the innermost SELECT statement. In our case it is a query, that "finds in a relational table: TABLE 2, the rows that satisfy a condition: Condition 2. In the next step, the results are projected on a column: COLUMN 1 and used in the outer SELECT statement. It is possible to consider the innner SELECT statement as a definition of inline view, that is later on used in the outer SELECT statement.

Nested queries

Nested query is a query with another query embedded in WHERE or SELECT or FROM clauses

NESTED

It is possible to nest SELECT statement to any level.

For example, the present slide shows how to create a nested SELECT statement with three levels of nesting. The innermost SELECT statement selects the values from a column: COLUMN 3, from all rows in a relational table: TABLE 3, that satisfy a condition: Condition 3.

Next, the results are used in SELECT statement, that selects the values from a column: COLUMN 4, from all rows in a relational table: TABLE 2, that satisfy a condition: COLUMN 2 IN the results of the previous SELECT statement.

Finally, the results from the second level of nesting are used in SELECT statement, that select the entire rows from a relational table: TABLE 1, that satisfy a condition: COLUMN 1 IN the results of SELECT statement at the second level of nestings.

A schema explaining how a nested query is constructed is given in the present slide.

Nested queries

Nested query is a query with another query embedded in WHERE or SELECT or FROM clauses

NESTED

Nested queries

Sample database

CREATE TABLE DEPARTMENT(
 name               VARCHAR(50)        NOT NULL,
 code               CHAR(5)            NOT NULL,
 total_staff_number DECIMAL(2)         NOT NULL,
 chair              VARCHAR(50)            NULL,
 budget             DECIMAL(9,1)       NOT NULL,
  CONSTRAINT dept_pkey PRIMARY KEY(name),
  CONSTRAINT dept_ckey1 UNIQUE(code),
  CONSTRAINT dept_ckey2 UNIQUE(chair),
  CONSTRAINT dept_check1 CHECK (total_staff_number BETWEEN 1 AND 50) );

CREATE TABLE COURSE(
 cnum               CHAR(7)           NOT NULL,
 title              VARCHAR(200)      NOT NULL,
 credits            DECIMAL(2)        NOT NULL,
 offered_by         VARCHAR(50)           NULL,
  CONSTRAINT course_pkey PRIMARY KEY(cnum),
  CONSTRAINT course_check1 CHECK (credits IN (6, 12)),
  CONSTRAINT course_fkey1 FOREIGN KEY(offered_by)
                        REFERENCES DEPARTMENT(name) ON DELETE CASCADE );

Nested queries

A class of nested queries is based on a concept of inline views
Inline views can be used to reduce the complexity of query implementation
An inner query is created first and its outcomes are used as a relational table (inline view) in an outer query
For example, a query find the titles of courses offered by a department chaired by Peter is decomposed into the following two queries:
- Q1: Find a department chaired by Peter
- Q2: Find the titles of courses offered by a department found in Q1
A query Q1 is implemented first and then it is used in WHERE clause of query Q2

It is possible to nest SELECT statements to theoretically unlimited level in WHERE clause.

A sample nested query in the middle of the present slide implements a query "find the titles of courses offered by a department chaired by Peter".

Interpretation of the nested query given in the present slide is the following. First, the inner query retrieves from a relational table: DEPARTMENT, the names of departments chaired by Peter. Note, that there may be at most one department chaired by Peter because a column: name, is a candidate key in a relational table: DEPARTMENT. Next, the result from processing of inner query is used in a condition: "offered by equals to a name of department found by an inner query", to select the rows for a relational table: COURSE. Finally, the titles of courses offered by a department chaired by Peter are returned, as the final results of the query processing.

It is important to remember, that if an inner query returns more than one row, then we must use set membership symbol: IN, instead of: equals sign. If an inner query returns at most one row we still must use equals sign. Using equals sign allows for more efficient implementation of a nested query, in a situation where an inner query always returns at most one row.

Nested queries

In nested queries SELECT statements are nested to theoretically unlimited level in WHERE clause


SELECT title
FROM COURSE
WHERE offered_by IN ( SELECT name
                      FROM DEPARTMENT
                      WHERE chair = 'Peter' );

If an inner query returns more than one row then we must use IN istead of =
However, it does not mean that we can always use IN instead of =
If an inner query returns zero or at most one row then using = instead of IN allows a query processor to find more efficient query processing plan

A query: "find the titles of courses offered by a department chaired by Peter" is implemented in the following way.

We start from the implementation of an inner query that finds: a name of department chaired by Peter, as an inline view Q. Implementation of an inline view Q is given at the top of the present slide. Next, we implement an outer query, that finds the titles of courses offered by a department, whose name has been retrieved by an inner query implemented as an inline view Q.

Implementation of the second step, is given in the middle of the present slide. Of course, a notation: "offered by equals Q dot name" is used only to denote a fact, that in the next step a definition of inline view: Q, must be copied into an outer query.

The final implementation of the nested query, that "find the titles of courses offered by a department chaired by Peter", is given at the bottom of the present slide.

Nested queries

Implementation of a query find the titles of courses offered by a department chaired by Peter consists of the following steps

Create a inner query as inline view Q

( SELECT name
FROM DEPARTMENT
WHERE chair = 'Peter' ) Q

Create a temporary outer query, that references an inline view Q created earlier

Replace a reference Q to an inline view with the inline view itself

SELECT title
FROM COURSE
WHERE offered_by IN ( SELECT name
                      FROM DEPARTMENT
                      WHERE chair = 'Peter' );

In another example, we implement a nested query, that finds the chair people of all departments that offer 12 credit point courses".

We start from a subquery, that "finds the names of departments that offer at least one 12 credit point course". SELECT statement, that implements the first subquery is given at the top of the present slide.

In the next step we create an outer subquery, that "finds the chair people of departments found in the inner subquery". A preliminary implementation of an outer subquery is given in the middle of the present slide.

Of course, a notation: "name in Q.offered by", does not compile well and we have to replace a name of inline view: Q, with a definition of inline view created in the first step.

The final implementation of a nested query, that finds finds the chair peoples of all departments that offer 12 credit point courses ?, is given at the bottom of the present slide.

Nested queries

Another example, find the chairs of all departments, that offer 12 credit point courses

Create an inner query as inline view Q

( SELECT offered_by
FROM COURSE
WHERE credits = 12) Q;

Next, create an intermediate from of outer query, that references an inline view Q created earlier

Replace a reference to an inline view Q with the inline view itself

SELECT chair
FROM DEPARTMENT
WHERE name IN ( SELECT offered_by
                FROM COURSE
                WHERE credits = 12 );

A query: find the chairs of all departments that offer no courses", requires implementation of the ANTIJOIN operation. The ANTIJOIN operation returns all rows from the first argument of the operation, that cannot be joined with any row from the second argument of the operation.

In contrast, the JOIN operation returns all rows joined from the first and the second argument of the operation. In the other words, all rows from the first and the second argument that can be joined.

The SEMIJOIN operation is the opposite to the ANTIJOIN operation and it returnes all rows from the first argument of the operation, that can be joined with at least one row from the second argument of the operation.

Both ANTIJOIN and SEMIJOIN operations are not directly implemented in SQL.

The SEMIJOIN operation can be expressed in two different ways. The first one, is a simple JOIN operation and later on projection on the attributes of the first argumentof JOIN operation. The second method uses a nested query with: IN condition, in WHERE clause of an outer SELECT statement.

The ANTIJOIN operation can be expressed through: LEFT or RIGHT OUTER JOIN operation, and: IS NULL condition, over the columns from either right or left argument of the operation. The ANTIJOIN operation can also be implemented as a nested query with: NOT IN condition, in outer SELECT statement.

A query: "find the chairs of all departments that offer no courses" is equivalent to a query, that finds all rows in a relational table: DEPARTMENT, that cannot be joined with any row in a relational table: COURSE. It is why we have to implement it, as the ANTIJOIN operation. An inner query implemented as an inline view: Q, finds all departments, that offer at least one course. Implementation of an inline view: Q, is given in the middle of the present slide. An outer query, finds all chairs of departments, that are NOT included in the results of an inner query. A temporary implementation of an outer query is given at the bottom of the present slide. Note, that a reference to an inline view: "name not in Q dot offered by", is not syntactically correct and it is included only to show a location where an an inline view: Q, must be embedded into the final implementation.

Nested queries

A query find the chairs of all departments that offer no courses is an example of ANTIJOIN operation
It is equivalent to a query find all rows in a relational table DEPARTMENT that cannot be joined with any row in a relational table COURSE
An inner query is implemented as an inline view finds all departments, that offer at least one course
An outer query finds all chairs of departments that are NOT included in the results of an inner query

Nested queries

Finally, we replace a reference to an inline view Q with the inline view itself


SELECT chair
FROM DEPARTMENT
WHERE name NOT IN ( SELECT offered_by
                    FROM COURSE );

SELECT statement (5)

A difference between a nested query and a correlated nested query is such, that in a correlated nested query an inline view implementing an inner query, references the names of relational tables used in an outer query.

An interpretation of a correlated nested query is the following. The rows from a relational table accessed by an outer query are read one by one. When a row is picked from the table then, all references located in an inner query, to the columns of the relational table used in outer query are replaced with the values of the picked row. Next, an inner query is processed and the results are verified against either empty or not empty condition included in WHERE clause. If a condition in WHERE clause evaluates to true, then the row from a relational table used in the outer query is saved in the results. Otherwise the row is ignored. The same cycle is repeated for the next row picked from a relational table used in an outer query.

A schema of interpretation of correlated nested query is presented in the current slide. The rows from a relational table: TABLE 1, alias T 1, are read one by one and an inner query is processed for each row read. All references in an inner query to the columns of a relational table: T 1 dot COLUMN N are replaced with the values taken from the current row. Next, an inner query is processed and its results are tested against: EXISTS condition. This is because: EXISTS keyword, is used in WHERE condition of an outer SELECT statement. If the results from the processing of an inner SELECT statement are not empty, then EXISTS condition evaluates to true and a row from a relational table: T 1 is appended to the final results. Then, the next row is picked from a relational table: T 1, the references located in an inner SELECT statement to the columns of a relational table T 1 are replaced with the values taken from the current row and an inner SELECT statement is processed again. If the results are not empty, then the current row from a relational table: T 1, is appended to the final results.

Please note, that it really does not matter what values are retrieved by an inner query.

It is important whether the results of inner query are not empty, if EXIST is used in WHERE clause or empty, if NOT EXISTS is used in WHERE clause. This is why, it is possible to SELECT whatever, for example a constant: x, in an inner SELECT statement of a correlated nested query.

Correlated nested queries

In a correlated nested query an inline view may reference the names of relational tables used in SELECT statements outer to the inline view

NESTED

In an interpretation visualised in the present slide, the second row from a relational table: T 1, is used to replace the references to the columns in a relational table T 1 in an inner SELECT statement, with values taken from the row. Then, an inner SELECT statement is processed and because the results of its processing are empty, the second row from a relational table: T 1, is not include into the final results.

Note, that if an inner SELECT statement does not have any references to a relational table used in an outer SELECT statement, then either nothing or all rows from a relational table used in an outer query, are included into the final result. It is so because, evaluation: of EXISTS or NOT EXISTS condition, does not depend on the rows picked from a relational table used in an outer SELECT statement.

A correlated nested query must have in an inner query the references to the values selected in an outer query.

Correlated nested queries

In a correlated nested query an inline view may reference the names of relational tables used in SELECT statemens outer to the inline view

NESTED

Correlated nested queries

In a correlated nested query an inline view may reference the names of relational tables used in SELECT statements outer to the inline view

NESTED

Implementation of a correlated nested query, usually needs a transformation of a natural language specification of a query, into a form that uses "exists" or "not exists" quantifiers.

For example, a query like: "find the chairs of departments, that offer 12 credit point courses", should be re-phrased into a query: "find the chairs of departments, such that there exists at least one course worth 12 credits and it is offered by a department we are looking for". Such specification of a query sounds a bit awkward, but a phrase: "there exists at least one ..." makes the specification almost the same as SELECT statement. Then, an inner query " ... course worth 12 credit points offered by a department we are looking for" is implemented as an inline view: Q, given in the middle of the present slide.

An inline view: Q, contains a reference to a department name: DEPARTMENT dot name, that implements a reference "... offered by a department we are looking for".

Next, we implement an outer query, that "finds the chairs of departments that there exists at least one course in a view: Q." SELECT statement, that implements such query is given at the bottom of the present slide. SELECT statement has EXISTS quantifier, in WHERE clause and at the moment uses a name of an inline view: Q,

Of course, to make the query syntactically correct, we have to replace a name of an inline view: Q, with a definition of the view.

Correlated nested queries

For example, consider a query, that finds the chairs of departments, that offer 12 credit point courses
Such query can be expressed as an equivalent query, that finds the chairs of departments, such that there exists at least one course worth 12 credit points offered by a department we are looking for
An inner query ... course worth 12 credit points offered by a department we are looking for is implemented as the following inline view Q
A temporary outer query, that finds the chairs of departments such that there exists at least one course found in the inner quer is implemented in the folowing way

A complete implementation of the query is given in the present slide.

Interpretation of such query is performed in the following way. The first row is picked from a relational table: DEPARTMENT. A value of an attribute: name, taken from the row replaces a reference:"DEPARTMENT dot name", in WHERE condition of an inner SELECT statement. An inner SELECT statement is processed and the result of processing is either empty or not empty. If the result of processing is not empty, then it means, that there exists a course worth 12 credits an offered by a department with a name included in the first row in a relational table: DEPARTMENT. It means, that the first row satisfies a search condition and a value of an attribute: chair, in the row can be inserted into the final results of query processing.

Next, the second row is picked from a relational table: DEPARTMENT. Again, a value of attribute: name, taken from the row replaces a reference: "DEPARTMENT dot name", in WHERE condition of an inner SELECT statement and an inner SELECT statement is processed. If the results of processing are empty, then a value of an attribute: chair, in the second row is not included into the final results of the query. If the results of processing of an inner query are not empty then a value of an attribute: chair, is inserted into the final results of query processing.

Next, the third row is taken from a relational table: DEPARTMENT and a value of attribute: name, in the row, replaces a reference: "DEPARTMENT dot name", in WHERE condition of an inner SELECT statement and an inner SELECT statement is processed. If the results of processing are not empty, then a value of an attribute chair in the third row is included into the final results of the query, otherwise the third row is skipped.

And the same procedure is repeated for all remaining rows in a relational table: DEPARTMENT.

Correlated nested queries

Finally, we replace a reference to an inline view Q with the inline view itself


SELECT chair
FROM DEPARTMENT
WHERE EXISTS ( SELECT *
               FROM COURSE
               WHERE credits = 12 AND offered_by = DEPARTMENT.name );

Correlated nested queries

In a correlated nested query an inline view may reference the names of relational tables used in SELECT statement outer to the inline view

NESTED

In the next example, we use a technique of correlated nested queries to implement a query: "find the chairs of all departments that offer no courses ?

The query can be rewritten into a format with: "not exists" phrase, in the following way. "Find the chairs of departments, such that does not exist a course offered by a department we are looking for." We start from implementation of an inline view: Q, that includes a query: "finds all courses offered by a department we are looking for". Implementation of an inline view is given in the middle of the present slide.

In the next step, we implement a query, that "finds all chairs of departments such that does not exist a course included in the inline view". Implementation of a query with a reference to inline view: Q, is given at the bottom of the present slide.

Finally, to get a syntactically correct statement, we replace a name of inline view: Q, with a definition of the view, see the next slide.

Correlated nested queries

Another example where inline view references a name of relational table used in SELECT statement outer to the inline view is the following
Find the chairs of all departments, that offer no courses
It is equivalent to a query find the chairs of departments, such that does not exist a course offered by a department we are looking for
An inner query finds ... a course offered by a department we are looking for and it is implemented as an inline view Q
A temporary outer query finds all chairs of deparments such that does not exist a course found by an inner query

A complete implementation of the query is given in the present slide.

Interpretation of such query is performed in the following way. The first row is taken from a relational table: DEPARTMENT. A value of an attribute: name, in the row replaces a reference: "DEPARTMENT dot name", in WHERE condition of an inner SELECT statement. An inner SELECT statement is processed and the result of processing is either empty or not empty. If the result of processing is empty, then it means that does not exist a course offered by a department with a name included in the first row in a relational table: DEPARTMENT. It means, that the first row satisfies a search condition and a value of an attribute: chair, can be inserted into the final results of query processing.

Next, the second row is taken from a relational table: DEPARTMENT. Again, a value of attribute: name, in the row, replaces a reference: DEPARTMENT dot name, in WHERE condition of an inner SELECT statement and an inner SELECT statement is processed. If the results of processing are not empty, then a value of an attribute: chair, in the second row is not included into the final results of the query. If the results of processing of an inner query are empty, then then a value of an attribute: chair, is inserted into the final results of query processing.

Next the third row is taken from a relational table: DEPARTMENT, and a value of attribute: name, in the row replaces a refrence: DEPARTMENT dot name, in WHERE condition of an inner SELECT statement and an inner SELECT statement is processed. If the results of processing are empty, then a value of an attribute: chair, in the third row is included into the final results of the query, otherwise the third row is skipped. And the same procedure is repeated for all remaining rows in a relational table: DEPARTMENT

Correlated nested queries

Finally, we replace a reference to an inline view Q with the inline view itself


SELECT chair
FROM DEPARTMENT
WHERE NOT EXISTS( SELECT *
                  FROM COURSE
                  WHERE offered_by = DEPARTMENT.name );

References

C. Coronel, S. Morris, A. Basta, M. Zgola, Data Management and Security, Chapters 5, 7, Cengage Compose eBook, 2018, eBook: Data Management and Security, 1st Edition
T. Connoly, C. Begg, Database Systems, A Practical Approach to Design, Implementation, and Management, Chapter 6.3.5 Subqueries, Chapter 6.3.8 EXISTS and NOT EXISTS, Chapter 7.4.1 Creating a View Pearson Education Ltd, 2015
D. Darmawikarta, SQL for MySQL A Beginner's Tutorial, Chapter 7 Subqueries, Chapter 9 Views, Brainy Software Inc. First Edition: June 2014
How to ... ? Cookbook, How to implement queries in SQL ? (Part 2) Recipe 6.3 How to implement nested queries ?
How to ... ? Cookbook, How to implement queries in SQL ? (Part 2) Recipe 6.4 Recipe 6.4 How to implement correlated nested queries ?