How to emulate relational algebra division operator in SQL

I found this recently among my files while preparing a lecture on SQL for my Database Systems course. I wrote this on October 2010 and have not checked it since then, but I believe in the correctness of the information.
To my Spanish readers, I ask for your forgiveness, I need to write a few things in english from time to time to avoid getting clogged (Is it “clogged” the right word?).


This document answer a very common question related to the emulation of division operation from relational algebra using SQL. Despite how commonly it’s used, most of the RDBMs don’t support division operation out of the box, so it’s necessary to find a way to emulate it with the help of other supported relational algebra operators. The present document describes a way to do that.

If you want to know what does a relational algebra’s division operator do or want to know how to emulate a division from other relational algebra operators check here.

First, we create the following tables. The meaning of the information contained in the tables is not important, only their structure matters.

CREATE TABLE foo (
  id   INTEGER PRIMARY KEY,
  name VARCHAR(10) 
);

CREATE TABLE faa (
  id   INTEGER PRIMARY KEY,
  name VARCHAR(10) 
);

CREATE TABLE foofaa (
  id_foo INTEGER REFERENCES foo,
  id_faa INTEGER REFERENCES faa
);

This is basically a many to many relation between foo and faa:

+-----+ *    +-----+
| foo |------| faa |
+-----+    * +-----+

or if you like:

+-----+ 1  * +--------+ *  1 +-----+
| foo |------| foofaa |------| faa |
+-----+      +--------+      +-----+

For testing purposes, we’ll fill the tables with some data. This way, the next queries will return the following results:

SELECT * FROM foo;

 id | name 
----+------
  1 | X
  2 | Y
  3 | Z
(3 rows)
SELECT * FROM faa;

 id | name 
----+------
  1 | A
  2 | B
  3 | C
(3 rows)
SELECT * FROM foofaa;

 id_foo | id_faa 
--------+--------
      1 |      1
      1 |      2
      1 |      3
      2 |      1
      2 |      2
      3 |      1
(6 rows)

Then, we want to perform a division between (R):

SELECT foo.id, foo.name, faa.name FROM foo, foofaa, faa
  WHERE foo.id = foofaa.id_foo AND faa.id = foofaa.id_faa;

 id | name | name 
----+------+------
  1 | X    | A
  1 | X    | B
  1 | X    | C
  2 | Y    | A
  2 | Y    | B
  3 | Z    | A
(6 rows)

…and (S):

SELECT name FROM faa;

 name 
------
 A
 B
 C
(3 rows)

So, the operation would be R/S.

The expected result is a relation containing the row (1, X), which is the only one that is related to each and every “name” in (S) (see division).

To emulate this with other relational algebra operators (but in SQL), we have to cross product the attributes in R that are not in S with S. So basically, from the setup we have created we need to cross the content of table faa with the content of S. We’ll name the result of this operation T:

SELECT foo.id, foo.name, faa.name FROM foo, faa;

 id | name | name 
----+------+------
  1 | X    | A
  1 | X    | B
  1 | X    | C
  2 | Y    | A
  2 | Y    | B
  2 | Y    | C
  3 | Z    | A
  3 | Z    | B
  3 | Z    | C
(9 rows)

Then we need to make T-R to have all the elements NOT present in the original R. We’ll call this result U:

(SELECT foo.id, foo.name, faa.name FROM foo, faa)
  EXCEPT
(SELECT foo.id, foo.name, faa.name FROM foo, foofaa, faa
    WHERE foo.id = foofaa.id_foo AND faa.id = foofaa.id_faa);

 id | name | name 
----+------+------
  2 | Y    | C
  3 | Z    | B
  3 | Z    | C
(3 rows)

This looks right, in the sense that the row originally named Y has only related A and B, so in U we have only C, which is not related to Y. Z is related only to A so it’s not related to B and C, and finally, X is related to all entries in faa so it does not appear on the results of U.

Now we project only the attributes from U that belong to R and name the result as V (some aliases tricks where needed to do this):

SELECT x.id, x.foo_name FROM (                                    
  (SELECT foo.id, foo.name AS foo_name, faa.name AS faa_name FROM foo, faa)
    EXCEPT
  (SELECT foo.id, foo.name, faa.name FROM foo, foofaa, faa
      WHERE foo.id = foofaa.id_foo AND faa.id = foofaa.id_faa)) AS x;

 id | foo_name 
----+----------
  2 | Y
  3 | Z
  3 | Z
(3 rows)

And finally we do R-V to get the desired R/S result:

(SELECT * FROM foo)
  EXCEPT
(SELECT x.id, x.foo_name FROM (
  (SELECT foo.id, foo.name AS foo_name, faa.name AS faa_name FROM foo, faa)
    EXCEPT
  (SELECT foo.id, foo.name, faa.name FROM foo, foofaa, faa
      WHERE foo.id = foofaa.id_foo AND faa.id = foofaa.id_faa)) AS x);

 id | name 
----+------
  1 | X
(1 row)

That’s it, the result is R/S!

Sueño de una noche de AVM (parte 2)

En una publicación anterior escribí un poco sobre el AVM y sobre una pesadilla que tuve al respecto.

Si bien en esa publicación describí con cierto detalle el AVM nunca terminé de contar la pesadilla (¿Suspenso? ¿Marketing?).

En fin, mi pesadilla fue la siguiente:


Me encontraba en una sala, en contra de mi voluntad, siendo forzado a trabajar con personas con las que probablemente evitaría trabajar si tuviera la oportunidad. Resulta que yo era algo así como “el líder del proyecto” y “el consultor técnico”. En el fondo había una sensación implícita de que si el proyecto fracasaba todo iba a ser culpa mía. Si el escenario le suena conocido a algún líder de proyecto o consultor puede pasar por mi casa, con gusto nos tomamos unos tragos y luego le presto una soga…

goya_1

Básicamente el proyecto consistía en una aplicación de escritorio basada en Swing, usando los primitivos DAOs que recuerdo (¿pesadillas con la clase MAbstract?) y MS SQL Server de BD. Sin servidor de aplicaciones, sin SOA, sin desacoplar la lógica del negocio del cliente y con unos horribles “updaters” de la BD.

El problema era que en el fondo no lideraba nada ni asesoraba en nada. Es decir, si bien trataba de lograr que todo funcionara y procuraba sugerir diseños que sonaban razonables, en el fondo nadie me hacía caso. La gente venía y me consultaba y luego se iba y hacía lo que quería, que usualmente en el sueño eran cosas locas que atentaban contra el sentido común.

Me explico, como consultor técnico, uno puede enumerarle las opciones técnicas al cliente, explicando de cada una las ventajas, desventajas, riesgos, debilidades, fortalezas, etc. Inclusive, es posible aconsejar para cierto contexto, proyecto o producto sobre la opción más adecuada a utilizar. El problema era, que en la situación en la que me encontraba, no habían opciones… es decir, independientemente del contexto, lo único que podía escoger era… la arquitectura del AVM, que como mencioné en una publicación anterior no era mala, pero con el tiempo se degradó bastante.

Yo sabía que existían alternativas mucho mejores, clamaban en mi interior por salir, no dejaba de pensar en Hibenate, Spring, SOA, EJB, CLEDA, etc…

Pero simplemente no salían. Lo único que podía escoger era el diseño base del AVM.

Debo aclarar que el producto NO era el AVM. Era otro producto, que terminaba pareciéndose al AVM, pero que definitivamente no lo era. Ahora que lo pienso, también parecía haber un problema de requisitos, es decir, si les soy franco no tenía ni la menor idea de que diablos se trataba el producto y eso en particular era muy frustrante.

Como líder de proyecto, mi trabajo era organizar el trabajo, el grupo, planificar, etc. En general, lo que hace un líder de proyecto en el sentido clásico del término. El problema era que el equipo de desarrollo era muy grande, demasiado grande para el producto que se estaba desarrollando. Pienso que habían como 50-60 personas en la sala, cuando yo estaba seguro de que un pequeño grupo de 5 personas sería más que suficiente para el trabajo. ¿Ven el dilema? Otra cosa curiosa es que había comida en toda la sala. El lugar parecía una fiesta, había pizza y refrescos por todos lados y la gente comía de forma muy descuidada. No se porque, pero cada vez que iba a hablar con alguien, esa persona estaba mascando un trozo de bistec o llevándose a la boca un poco de ensalada.

goya_2

Bueno, quizá exageré un poco con la ilustración anterior…

Yo estaba seguro de que lo ideal era usar algún tipo de estrategia ágil, tenía planeado organizar las 50 personas en pequeños grupos de 5-6 personas, usar algo como Scrum y asignar a cada grupo pequeñas tareas. Suena loco y forzado pero sinceramente, creo que fue la mejor idea a la que mi subconsciente pudo llegar para compensar la locura de un proyecto de 5-6 personas desarrollado por 50-60. A decir verdad, dada la locura y lo surrealista de la situación, aún ahora despierto no creo que la estrategia fuese tan mala idea.

Pero aquí viene lo peor…

goya_3

Por más que se suponía que yo era el líder del proyecto, o al menos todos lo suponían, es decir, en lo que a mi respecta yo sólo quería salir corriendo de la sala (desastre) y era evidente que toda la responsabilidad iba a ser mía si algo salía mal, no tenía absolutamente ningún poder de dirección.

Era simplemente imposible organizar tareas, era imposible hablar con nadie del equipo (o del manicomio). Lo peor, era que había una mujer detestable, y esto lo digo sin pretender en lo absoluto ofender al género femenino, que iba como loca de un lado a otro, dando y gritando ordenes, que eran en general disparates, mirándome con cara de cómplice y guiñándome un ojo tanto en tanto… y simplemente no había nada que yo pudiera hacer para detenerla, era una criatura verdaderamente aterradora.

A decir verdad no se en que terminó todo. Si nos guiamos por el sentido común, entonces es evidente que terminó en desastre… pero en el reino del subconsciente uno nunca sabe.

Afortunadamente desperté y resultó ser de esos sueños (pesadillas) impactantes que uno recuerda y escribe. De hecho, releyendo mi texto pienso que la pesadilla fue mucho peor de lo que en verdad he logrado plasmar en estas líneas, mi descripción carece de los colores oscuros, el horror y la frustración necesaria.

Por cierto, si el infierno existe… seguro que esta pesadilla sería un buen tormento XD

goya_4

Todas las ilustraciones de este post son de Francisco Goya

De arriba a abajo, las obras se llaman “El tres de mayo de 1808”, “Saturno devorando a un hijo”, “Esto es peor” y “El sueño de la razón produce monstruos”.


Debo decir que no tengo nada en contra del AVM. Todo lo contrario. En el fondo recuerdo el proyecto con mucho cariño, fue una buena escuela en la que además pude compartir trabajo con buenos colegas. De alguna forma, quizá indirectamente, esta es mi retorcida manera de rendirle un homenaje al AVM.