-- In the lecture notes we defined relational division for relations -- R(X, Y) and S(Y) as -- -- R / S == pi_X(R) - pi_X( (pi_X (R) x S) - R) -- -- Mistral Contrastin directly translates this into SQL -- using the "not in" construct (twice). -- Here is a tiny example using Mistral's query idea. create table R ( x1 int, x2 int ) ; create table S ( x2 int ) ; insert into R values (1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 2); insert into S values (1), (2), (3); -- This query will return "2" -- all x1 values in R that are associated with all x2 values in S. -- select distinct x1 from R where x1 not in (select x1 from (select x1, S.x2 from R, S where (x1, S.x2) not in (select * from R))) ; --- Now let us turn to an amusing example --- provided by Constantin Manea. --- --- We have three relations: --- --- products(barcode, name) --- purchases(id, date_created) --- customer_log(transaction_id, product_id) --- --- Let's populate that tables with a bit of data. --- CREATE TABLE products ( barcode bigint NOT NULL, name varchar(100) NOT NULL, PRIMARY KEY (barcode) ); INSERT INTO products (barcode, name) VALUES (107595782255, 'Milk'), (274411900030, 'Coat Hanger Set'), (293111016617, 'Rubber Tubing'), (314171852081, 'Bear Trap'), (325018705296, 'Ski Mask'), (461240515054, 'Saw'), (540748139122, 'Candy'), (620050429565, 'Honey'), (640135143681, 'Tourist Map of Pentagon'), (707846003157, 'Hatchet'), (792490360432, 'Spool of Razor Wire'), (926249864208, 'Bread'), (934379996978, 'Gasoline Can'); CREATE TABLE purchases ( id bigint NOT NULL, date_created timestamp NOT NULL, PRIMARY KEY (id) ); INSERT INTO purchases (id, date_created) VALUES (267774161140, '2014-01-29 23:41:55'), (450353462267, '2014-01-29 23:44:20'), (529774644351, '2014-01-29 23:39:03'), (868060326785, '2014-01-29 23:42:22'), (977312414521, '2014-01-29 23:38:30'); CREATE TABLE customer_log ( transaction_id bigint DEFAULT NULL, product_id bigint DEFAULT NULL, primary key (transaction_id, product_id), CONSTRAINT FK_customer_log_products FOREIGN KEY (product_id) REFERENCES products (barcode), CONSTRAINT FK_customer_log_purchases FOREIGN KEY (transaction_id) REFERENCES purchases (id) ); INSERT INTO customer_log (transaction_id, product_id) VALUES (529774644351, 314171852081), (529774644351, 934379996978), (529774644351, 707846003157), (529774644351, 293111016617), (529774644351, 461240515054), (529774644351, 325018705296), (529774644351, 792490360432), (529774644351, 640135143681), (450353462267, 926249864208), (450353462267, 540748139122), (267774161140, 274411900030), (267774161140, 107595782255), (977312414521, 620050429565), (977312414521, 707846003157), (868060326785, 792490360432); ---- Now the NSA has identified some subsets of these ---- purchases to be suspect, In particular these SELECT barcode FROM products WHERE name IN ('Rubber Tubing', 'Bear Trap', 'Ski Mask', 'Saw', 'Hatchet', 'Spool of Razor Wire', 'Gasoline Can', 'Tourist Map of Pentagon'); --- So we are interested in --- R(X, Y) = customer_log(transaction_id, product_id) --- S(Y) = SUSPECT(barcode) (barcode == product_id) --- --- We can use division to find the suspect transactions. select distinct transaction_id from customer_log where transaction_id not in (select transaction_id from (select transaction_id, barcode from customer_log, (SELECT barcode FROM products WHERE name IN ('Rubber Tubing', 'Bear Trap', 'Ski Mask', 'Saw', 'Hatchet', 'Spool of Razor Wire', 'Gasoline Can', 'Tourist Map of Pentagon')) where (transaction_id, barcode) not in (select * from customer_log))) ; ---- query result : ---- 529774644351 ----