La semana del 24 de Marzo, en Tampere (Finlandia), se celebró el congreso internacional conjunto de bases de datos EDBT/ICDT, siendo el EDBT la comunidad que estudia nuevas tecnologías en la práctica, y el ICDT la comunidad que estudia el fundamento teórico. El caso es que, este año, el inLab FIB ha tenido presencia en el ICDT con un full paper de la mano del autor de este mismo artículo. A partir de aquí, la pregunta inevitable es… ¿qué hace un investigador en ingeniería del software en un congreso de teoría pura de bases de datos? ¿Pueden los investigadores más bien prácticos aportar en un contexto absolutamente teórico? ¿Tiene sentido intentarlo en un contexto donde la IA se lo está comiendo todo?
La clave de todo ello se esconde en una pregunta aún más bestia: ¿por qué quieres investigar? En efecto, si tu objetivo es hacerte un nombre en la investigación, con un poco de suerte te tumbarán cada artículo enviado con suficiente contundencia como para desistir antes de acabar en terapia (si no tú, los tuyos). Y sí, se suele tener mucha, y mucha suerte en la investigación.
Suposem però que t’interessa un problema genuïnament. Per exemple, el problema tractat en l’article anterior és el conteniment de consultes d’una base de dades (BD). En una BD diem que una consulta q1 està continguda en una consulta q2 si els resultats de q1 sempre estan continguts en q2, independentment de la BD. Per simplificar, suposem que tenim només consultes booleanes. En aquest cas, diem que q1 està contingut en q2 si i només sí quan q1 és cert, també ho és q2.
Un requisito habitual de los artículos académicos es la utilización de pequeños ejemplos didácticos con aire motivacional. Para continuar parafraseando a Foster Wallace, supongamos que queremos hacer una consulta sobre una BD de animales preguntando si hay registrados animales que viven en el agua. En lenguaje Datalog, lo escribiríamos más o menos así:
q1() :- Animal(x), ViveEn(x,Agua)
El caso es que también podríamos estar interesados en otra consulta similar, por ejemplo, una consulta preguntando si tenemos animales acuáticos que son mamíferos:
q2() :- Animal(y), ViveEn(y,Agua), EsMamifero(y)
Claramente, la consulta q2 está contenida en q1, ya que, en resumen, q2 está pidiendo lo mismo que q1, pero aplicando un filtro adicional (que sería la comprobación de EsMamífero). Darnos cuenta del contenimiento de consultas nos puede ayudar en diversos problemas, como el de optimizar el rendimiento de una base de datos, o incluso, encontrar qué proveedores de datos ofrecen datos que pueden interesar a un cliente.
Todo esto está muy bien, pero ¿cómo demonios podemos resolver este problema? Pues aquí tenemos una muy buena noticia: desde hace más de 40 años sabemos que, si las consultas tienen una forma concreta (¡y muy frecuente!), una consulta q está contenida en otra consulta q’ si, y solo si, podemos reescribir q’ en términos de q. En nuestro ejemplo, q2 es literalmente la misma consulta que q1 pero cambiando la variable y por x y añadiendo una comprobación adicional EsMamífero. Lo mejor de todo esto es que esta comprobación se puede hacer con un test muy sencillo: solo tenemos que crear una BD que contenga todos los elementos de la query q2 (sustituyendo cada variable por una constante, por ejemplo, sustituyendo la variable y por una constante #y), y si lanzamos la consulta q1 contra esta BD, la BD ya se encargará de encontrar que q2 es como q1 pero cambiando la variable x por y.
¿Y cuál es esa forma concreta que deben cumplir las consultas para que todo esto funcione? En esencia, la consulta debe ser positiva, lo que quiere decir que no puede tener operaciones matemáticas (sumas, restas o comparaciones de mayor o menor), ni tampoco condiciones negadas. Es decir, estamos hablando de consultas SQL que solo usan EQUI-JOINS. Siendo formales, decimos que una conjunctive query está contenida en otra conjunctive query, en set-semantics, si existe un homomorfismo desde la segunda consulta a la primera (Teorema del Homomorfismo). El lector interesado puede encontrar más detalles en el propio artículo, pero no se preocupen, ninguno de estos formalismos acaba siendo excesivamente complicado ni se aleja demasiado de las intuiciones aquí descritas. El artículo pretende ser entendible, hasta el punto de perder las dos grandes ventajas de los textos ininteligibles que decía Foster Wallace: 1) cuanto menos personas entienden el artículo, más eruditos se sienten algunos autores (llegando a la máxima de Wilde de que ni el propio autor entiende lo que dice), y 2) cuanto menos personas entienden el artículo, menos personas pueden criticarlo (llegando a la máxima de ver artículos aceptados en congresos porque nadie los ha entendido).
Pero no nos pongamos tan negativos, y hablemos de qué pasa cuando añadimos negación a las consultas. Por ejemplo, pongamos por caso que ahora preguntamos si existen animales que viven en el agua pero que no viven en tierra:
q3() :- Animal(y), ViveEn(y,Agua), not ViveEn(y,Tierra).
En resumen, cuando las consultas tienen negación, el Teorema del Homomorfismo falla. Es decir, hay consultas contenidas en otras, a pesar de no poder reescribirse una en términos de la otra. La ruptura del Teorema del Homomorfismo es bastante problemática, ya que mientras implementar un test de homomorfismo es bastante sencillo, los tests que se han ideado para comprobar el contenimiento de dos consultas con negación son, en general, difíciles y computacionalmente complejos. Como ingeniero del software, me gustan las ideas de implementación sencillas, por lo que confieso que aquí me quedé bastante atascado intentando encontrar una caracterización que diga cuándo una consulta, incluso con negación, satisface el Teorema del Homomorfismo, para así poder hacer uso de este test. No queráis saber el lío en el que me estaba metiendo yo mismo construyendo, de forma incremental, una caracterización sumamente inteligente en términos de Wilde para resolver un problema cada vez más frustrante y cada vez más desmotivador.
En Esto es agua, Foster Wallace decía que la principal habilidad que se adquiere en la universidad no es la de pensar, sino la de decidir qué pensar. Ante las adversidades, antes de seguir maldiciéndonos los huesos, Foster Wallace nos invita a salir de nuestro monólogo interno y prestar una atención consciente a lo que está ocurriendo a nuestro alrededor.
Olvidémonos por un momento del problema que tenemos con la negación, y fijémonos en otro formalismo llamado tuple-generating dependencies (TGD). Una TGD es una regla que, a partir de unos datos de la BD, genera otros nuevos. Por ejemplo, podemos tener una TGD que dice que si sé que x es un Niño, puedo generar un nuevo dato diciendo que x es también Persona:
Niño(x) -> Persona(x)
El problema principal de las TGDs es que pueden generar una cantidad infinita de datos, ya que la generación de un nuevo dato puede provocar la ejecución de la misma TGD, y así indefinidamente. Por ejemplo, supongamos una TGD que dice que todo padre ha tenido otro padre:
PadreDe(x, y) -> PadreDe(y, z)
Claramente, cuando creamos una tupla PareDe, necesitamos crear otra tupla PareDe, y así hasta el infinito.
Para resolver este problema, la comunidad teórica de BD ha estudiado condiciones que garantizan que una TGD no genera datos indefinidamente. Si una TGD solo puede ejecutarse, recursivamente, un máximo de 5 veces, decimos que la TGD es 5-bounded. Similarmente, si cuando ejecutamos una TGD no podemos reejecutarla recursivamente otra vez, decimos que la TGD es one-bounded. Por ejemplo, imaginemos una TGD que, en resumen, dice que si un animal vive en el agua, también debe vivir en la tierra:
Animal(x), ViveEn(x,Agua) -> ViveEn(x,Tierra).
Esta TGD es one-bounded ya que, al crear nuevas tuplas de ViveEn, estas no pueden ejecutar de nuevo la misma regla.
Volviendo a las consultas, existe una cierta relación entre estas y las TGDs. En particular, la TGD anterior representa los datos que deben crearse para insatisfacer la query q3. En efecto, cada instancia de datos que puede satisfacer q3 (por ejemplo, si encontramos un animal “Tortuga” que vive en el Agua pero no en la Tierra), puede usarse en la TGD para crear un nuevo dato (ViveEn(Tortuga, Tierra)) que invalida q3. Dada una consulta con negación, es bastante sencillo construir su correspondiente TGD que genera datos para falsarla. De hecho, basta con tomar la condición negada y añadirla a la parte derecha de la TGD.
El caso es que, en el artículo, demostramos que una query satisface el Teorema del Homomorfismo si y solo si su correspondiente TGD es one-bounded. La intuición principal es que, para probar que una consulta q1 está contenida en otra q2, basta con analizar si, sobre una BD donde q1 es cierta, se puede ejecutar la TGD de q2, de manera que insatisfacemos q2 pero seguimos satisfaciendo q1. El caso es que el test de homomorfismo se encarga de validar que q1 sigue siendo cierta después de ejecutar la TGD una vez, pero falla para validar si q1 es cierta si se ejecuta la TGD varias veces recursivamente.
No deja de ser poético ver que, en el mundo de las consultas de bases de datos, igual que en la investigación, o como diría Foster Wallace, en las trincheras de la vida adulta cotidiana, la incapacidad de dejar de buclear en uno mismo nos impide encontrar una respuesta sencilla y sincera en nuestro entorno. Quizá la investigación trata de buscar puentes entre distintos ámbitos. Quizá trata de comunicarlos de una manera llana para facilitar esa conexión a otra persona. Quizá trata de un ejercicio consciente de construir, entre todos, algo positivo para dar la vuelta a tanta negatividad. Venga de donde venga, si te quieres dedicar a la investigación, te deseo mucho más que suerte.