Relational division

Let`s consider task:

Determine makers which produce models of all types (in Computer firm schema).

The keyword here is “all” which means that maker in Product table must have models of every type: PC, Laptop, and Printer.

There is special operation for solving this type of tasks in the relational algebra. This operation is relational division (DIVIDE BY).

This operation makes solution of considering task very simple [1]:

Product[maker, type] DIVIDE BY Product[type]

The hooks determine projection operation to the corresponding attributes.

The relational division operation is superfluous. It can be expressed by the other operations of the relational algebra. Perhaps, that`s the reason why it absents in the SQL.

Let`s introduce some methods of implementation of relational division in SQL on considering example.

Grouping

If we use fact that there is only three types of product corresponding to description of the knowledge domain, we may group data by maker and count quantity of unique types. Then we select only makers with quantity equal three.

Итак,

SELECT maker
FROM Product
GROUP BY maker
HAVING COUNT(distinct type) = 3;
mssql
🚫
[[ error ]]
[[ column ]]
[[ value ]]

But if the type`s count is arbitrary this solution will be right only in current state of database, not in every possible. So we need to replace hard number by “variable”, i.e. to use subquery:

SELECT maker  
FROM Product  
GROUP BY maker  
HAVING COUNT(DISTINCT type) = (SELECT COUNT(DISTINCT type) FROM Product);
mssql
🚫
[[ error ]]
[[ column ]]
[[ value ]]

Subtraction

If we subtract model types of every maker from all types then the resultant set must have no rows for maker with all types of product.

SELECT DISTINCT maker
FROM Product Pr1
WHERE 0 = (SELECT COUNT(*) FROM
(SELECT type FROM Product
 EXCEPT
 SELECT type FROM Product Pr2 WHERE Pr2.maker = Pr1.maker
) X );
mssql
🚫
[[ error ]]
[[ column ]]
[[ value ]]

This query may be rewritten in shorter form if we take into account fact that the ALL predicate returns TRUE if the subquery have no rows:

SELECT DISTINCT maker
FROM Product Pr1
WHERE type = ALL
(SELECT type FROM Product
 EXCEPT
 SELECT type FROM Product Pr2 WHERE Pr2.maker = Pr1.maker
);
mssql
🚫
[[ error ]]
[[ column ]]
[[ value ]]

The ALL predicate`s list will be empty for target makers, and in all other cases it would contain types which are absent in the maker product list and the operation “=” for all models returns FALSE.

Existence

There is no such type of product which is absent in the maker`s product list.

SELECT DISTINCT maker
FROM Product Pr1
WHERE NOT EXISTS (SELECT type
                  FROM Product
                  WHERE type NOT IN (SELECT type
                                     FROM Product Pr2
                                     WHERE Pr1.maker = Pr2.maker));
mssql
🚫
[[ error ]]
[[ column ]]
[[ value ]]

All solutions, except first one, are using correlation subquery for determining the maker`s product types set.

We should also note that the solution with grouping is not applicable for cases in which we need to divide by not full set of types, but its subset. For instance, if we need to find all makers with product`s set include (or equal to) set of types determined by some criteria. Other methods may be adapted for solving such tasks.

Suggested exercises: 71