Relational Division

Sometimes you come across a problem in SQL that is far more complex than you first imagine. One classic of these is 'Relational Division' - a poorly understood aspect of SQL that can help answer what must be a common question:

Return the things that have all of the items in a given list

Example questions:

• If I have a list of people with related skills, how can I return those with all of the skills in a list.
• Get a list of products that have a given set of features, recipes with the following ingredients, etc

Most might answer that you use an IN LIST - but that is an OR list not an AND list.

So not:

• Return those with any of the given values e.g. where related values in (1,2,3) but
• Return those with all of the given values i.e. where related values = 1 and 2 and 3

In Joe Celko's SQL for Smarties he has a list of pilots who can fly types of planes and a hanger with some planes in it. Which pilots can fly all of the planes in the hanger. This is called - Relational Division.

This is unbelievable that it is so hard to answer this question.

So to an example to show how it works:

Let's assume we have a set of people that possess one or more skills. The answer we want is show me the people who have all of the skills in a list.

e.g. get those with LAMP skills - Drupal, PHP and MySQL

Given a table schema like

/* Tables and data for Relational Division Example */
CREATE TABLE `skill` (
  `idSkill` int(11) NOT NULL AUTO_INCREMENT,
  `Skill` varchar(45) DEFAULT NULL,
  PRIMARY KEY (`idSkill`)
) ENGINE=InnoDB AUTO_INCREMENT=5 DEFAULT CHARSET=latin1


CREATE TABLE `person` (
  `idPerson` int(11) NOT NULL AUTO_INCREMENT,
  `person_name` varchar(45) DEFAULT NULL,
  PRIMARY KEY (`idPerson`)
) ENGINE=InnoDB AUTO_INCREMENT=5 DEFAULT CHARSET=latin1

CREATE TABLE `person_skill` (
  `idPerson` int(11) NOT NULL,
  `idSkill` int(11) NOT NULL,
  PRIMARY KEY (`idPerson`,`idSkill`),
  KEY `fk_person_skill_Skill1` (`idSkill`),
  CONSTRAINT `fk_person_skill_person` FOREIGN KEY (`idPerson`) REFERENCES `person` (`idPerson`) ON DELETE NO ACTION ON UPDATE NO ACTION,
  CONSTRAINT `fk_person_skill_Skill1` FOREIGN KEY (`idSkill`) REFERENCES `Skill` (`idSkill`) ON DELETE NO ACTION ON UPDATE NO ACTION
) ENGINE=InnoDB DEFAULT CHARSET=latin1


INSERT INTO `person` (`idPerson`, `person_name`) VALUES
(1, 'Tom'),
(2, 'Dick'),
(3, 'Harriet'),
(4, 'Alice');

INSERT INTO `skill` (`idSkill`, `Skill`) VALUES
(1, 'Linux'),
(2, 'PHP'),
(3, 'MySQL'),
(4, 'Drupal');

INSERT INTO `person_skill` (`idPerson`, `idSkill`) VALUES
(1, 1),
(4, 1),
(1, 2),
(2, 2),
(4, 2),
(1, 3),
(2, 3),
(3, 3),
(4, 3),
(1, 4),
(3, 4),
(4, 4);

Tom, Dick and Harriet are people
Linux, Drupal, MySQL, PHP are skills

Tom is skilled in all four skills (Linux, Drupal, PHP and MySQL) as is Alice; Dick and Harriet only have two skills.

People have 1 or more skills - but we want to find all those with Drupal and PHP and MYSQL skills

Put another way say we normally use an in list like:

/**
 * An in list performs an OR not an AND
 */
SELECT p.person_name, s.skill FROM `test`.`person` p
  inner join person_skill ps on ps.idPerson = p.idPerson
  inner join skill s on s.idskill = ps.idskill
where skill in ('Drupal', 'PHP' , 'MySQL')
order by p.idperson

but that is an or list

e.g. it says return all people who have Drupal, PHP or MySQL and you'll get back all four people.

What we want is to select People that have all of the skills provided, like an in list but an AND not OR

This turns out to be exceptionally hard and not easy to resolve - it is called Relational Division.

You will find loads about it but very few good answers (Joe Celko always has good solutions clearly - https://www.simple-talk.com/sql/t-sql-programming/divided-we-stand-the-s... - His book 'SQL for Smarties' is a must read for DBAs))

Here is a quick solution:

/* List people with all four skills */
SELECT  s.person_name
FROM    Person s INNER JOIN
                 (SELECT     ps.idPerson
                  FROM          person_skill ps
                  WHERE      ps.idskill IN (1,2,3,4)
                  GROUP BY ps.idperson
                  HAVING      COUNT(*) =
                       (SELECT     COUNT(*)
                        FROM          skill
                        WHERE      (idskill IN (1,2,3,4)))
                  ) filter ON s.idPerson = filter.idPerson
ORDER BY s.person_name

Basically it says 'get all the people with any of the skills but where the number of skills they have is equal to the number of skills matched by the list'.

Count the number of skills from the skill table.

Do a group by of the people and their skill count and only return those with the same number of skills as asked for. You'd think it would be simpler than that wouldn't you...

This method enables you to pass in one in list and use it twice.

To adapt the method provided by Joe Celko where his example uses a table of planes in a hanger - (our example uses a provided in list)'

/** Example adapted from Joe Celko's explanation of relational division:
 *  https://www.simple-talk.com/sql/t-sql-programming/divided-we-stand-the-sql-of-relational-division/
 */
SELECT DISTINCT person_name
  FROM person_Skill AS PS1 inner join person p on p.idperson = ps1.idperson
  WHERE NOT EXISTS
       (SELECT *
          FROM skill
         WHERE idskill in (2,3,4) and NOT EXISTS
               (SELECT *
                  FROM person_Skill AS PS2
                 WHERE (PS1.idperson = PS2.idperson)
                   AND (PS2.idskill = skill.idskill)));

This will give us the people with MySQL and Drupal skills (e.g. Tom, Harriet & Alice). This must be the best answer - if not the easiest to understand. Joe Celko uses an nice double negative to explain the logic here (using his Pilot's and Hanger of planes example)'

The quickest way to explain what is happening in this query is to imagine a World War II movie where a cocky pilot has just walked into the hangar, looked over the fleet, and announced, "There ain't no planes in this hangar that I can't fly!" We want to find pilots for whom no plane exists in the hangar for which they have no skills. You might want to read that double negative again – it is ugly English, but good logic. https://www.simple-talk.com/sql/t-sql-programming/divided-we-stand-the-s...

I have also seen other examples that test the list for the number of items (I prefer the previous example as it also tests for the skills' existence):

/* Another example using interrogation of in list not sub query */
SELECT     s.person_name
FROM         Person s INNER JOIN
                      (SELECT     ps.idPerson
                        FROM          person_skill ps
                        WHERE      ps.idskill IN (1, 2, 3)
                        GROUP BY ps.idperson
                        HAVING      COUNT(*) = (Length('1, 2, 3') - Length(REPLACE('1, 2, 3', ',', '')) + 1)
                        ) filter ON s.idPerson = filter.idPerson
ORDER BY s.person_name

That uses one 'in list' and simply counts the number of items passed in(by looking for commas).

Me on Google+

Refs

• https://www.simple-talk.com/sql/t-sql-programming/divided-we-stand-the-sql-of-relational-division/
• http://en.wikipedia.org/wiki/Relational_algebra#Division_.28.C3.B7.29