{"id":35751,"date":"2026-04-29T11:53:36","date_gmt":"2026-04-29T09:53:36","guid":{"rendered":"https:\/\/inlab.fib.upc.edu\/?p=35751"},"modified":"2026-04-29T11:53:43","modified_gmt":"2026-04-29T09:53:43","slug":"foster-wallace-y-el-contenimiento-de-consultas","status":"publish","type":"post","link":"https:\/\/inlab.fib.upc.edu\/es\/articles\/foster-wallace-y-el-contenimiento-de-consultas","title":{"rendered":"Foster Wallace y el contenimiento de consultas"},"content":{"rendered":"\n

La semana del 24 de Marzo, en Tampere (Finlandia), se celebr\u00f3 el congreso internacional conjunto de bases de datos EDBT\/ICDT, siendo el EDBT la comunidad que estudia nuevas tecnolog\u00edas en la pr\u00e1ctica, y el ICDT la comunidad que estudia el fundamento te\u00f3rico. El caso es que, este a\u00f1o, el inLab FIB ha tenido presencia en el ICDT con un full paper<\/a> de la mano del autor de este mismo art\u00edculo. A partir de aqu\u00ed, la pregunta inevitable es… \u00bfqu\u00e9 hace un investigador en ingenier\u00eda del software en un congreso de teor\u00eda pura de bases de datos? \u00bfPueden los investigadores m\u00e1s bien pr\u00e1cticos aportar en un contexto absolutamente te\u00f3rico? \u00bfTiene sentido intentarlo en un contexto donde la IA se lo est\u00e1 comiendo todo? <\/p>\n\n

La clave de todo ello se esconde en una pregunta a\u00fan m\u00e1s bestia: \u00bfpor qu\u00e9 quieres investigar? En efecto, si tu objetivo es hacerte un nombre en la investigaci\u00f3n, con un poco de suerte te tumbar\u00e1n cada art\u00edculo enviado con suficiente contundencia como para desistir antes de acabar en terapia (si no t\u00fa, los tuyos). Y s\u00ed, se suele tener mucha, y mucha suerte en la investigaci\u00f3n. <\/p>\n\n

Suposem per\u00f2 que t\u2019interessa un problema genu\u00efnament. Per exemple, el problema tractat en l\u2019article anterior \u00e9s el conteniment de consultes d\u2019una base de dades (BD). En una BD diem que una consulta q1 est\u00e0 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\u00e9s consultes booleanes. En aquest cas, diem que q1 est\u00e0 contingut en q2 si i nom\u00e9s s\u00ed quan q1 \u00e9s cert, tamb\u00e9 ho \u00e9s q2. <\/p>\n\n

Un requisito habitual de los art\u00edculos acad\u00e9micos es la utilizaci\u00f3n de peque\u00f1os ejemplos did\u00e1cticos 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\u00edamos m\u00e1s o menos as\u00ed: <\/p>\n\n

q1() :- Animal(x), ViveEn(x,Agua)<\/p>\n\n

El caso es que tambi\u00e9n podr\u00edamos estar interesados en otra consulta similar, por ejemplo, una consulta preguntando si tenemos animales acu\u00e1ticos que son mam\u00edferos: <\/p>\n\n

q2() :- Animal(y), ViveEn(y,Agua), EsMamifero(y)<\/p>\n\n

Claramente, la consulta q2 est\u00e1 contenida en q1, ya que, en resumen, q2 est\u00e1 pidiendo lo mismo que q1, pero aplicando un filtro adicional (que ser\u00eda la comprobaci\u00f3n de EsMam\u00edfero). 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\u00e9 proveedores de datos ofrecen datos que pueden interesar a un cliente<\/a>. <\/p>\n\n

Todo esto est\u00e1 muy bien, pero \u00bfc\u00f3mo demonios podemos resolver este problema? Pues aqu\u00ed tenemos una muy buena noticia: desde hace m\u00e1s de 40 a\u00f1os sabemos que, si las consultas tienen una forma concreta (\u00a1y muy frecuente!), una consulta q est\u00e1 contenida en otra consulta q\u2019 si, y solo si, podemos reescribir q\u2019 en t\u00e9rminos de q. En nuestro ejemplo, q2 es literalmente la misma consulta que q1 pero cambiando la variable y por x y a\u00f1adiendo una comprobaci\u00f3n adicional EsMam\u00edfero. Lo mejor de todo esto es que esta comprobaci\u00f3n 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\u00e1 de encontrar que q2 es como q1 pero cambiando la variable x por y. <\/p>\n\n

\u00bfY cu\u00e1l 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\u00e1ticas (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\u00e1 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\u00e1s detalles en el propio art\u00edculo, pero no se preocupen, ninguno de estos formalismos acaba siendo excesivamente complicado ni se aleja demasiado de las intuiciones aqu\u00ed descritas. El art\u00edculo pretende ser entendible, hasta el punto de perder las dos grandes ventajas de los textos ininteligibles que dec\u00eda Foster Wallace: 1) cuanto menos personas entienden el art\u00edculo, m\u00e1s eruditos se sienten algunos autores (llegando a la m\u00e1xima de Wilde de que ni el propio autor entiende lo que dice), y 2) cuanto menos personas entienden el art\u00edculo, menos personas pueden criticarlo (llegando a la m\u00e1xima de ver art\u00edculos aceptados en congresos porque nadie los ha entendido). <\/p>\n\n

Pero no nos pongamos tan negativos, y hablemos de qu\u00e9 pasa cuando a\u00f1adimos negaci\u00f3n 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: <\/p>\n\n

q3() :- Animal(y), ViveEn(y,Agua), not ViveEn(y,Tierra).<\/p>\n\n

En resumen, cuando las consultas tienen negaci\u00f3n, el Teorema del Homomorfismo falla. Es decir, hay consultas contenidas en otras, a pesar de no poder reescribirse una en t\u00e9rminos de la otra. La ruptura del Teorema del Homomorfismo es bastante problem\u00e1tica, 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\u00f3n son, en general, dif\u00edciles y computacionalmente complejos. Como ingeniero del software, me gustan las ideas de implementaci\u00f3n sencillas, por lo que confieso que aqu\u00ed me qued\u00e9 bastante atascado intentando encontrar una caracterizaci\u00f3n que diga cu\u00e1ndo una consulta, incluso con negaci\u00f3n, satisface el Teorema del Homomorfismo, para as\u00ed poder hacer uso de este test. No quer\u00e1is saber el l\u00edo en el que me estaba metiendo yo mismo construyendo, de forma incremental, una caracterizaci\u00f3n sumamente inteligente en t\u00e9rminos de Wilde para resolver un problema cada vez m\u00e1s frustrante y cada vez m\u00e1s desmotivador. <\/p>\n\n

En Esto es agua<\/a>, Foster Wallace dec\u00eda que la principal habilidad que se adquiere en la universidad no es la de pensar, sino la de decidir qu\u00e9 pensar. Ante las adversidades, antes de seguir maldici\u00e9ndonos los huesos, Foster Wallace nos invita a salir de nuestro mon\u00f3logo interno y prestar una atenci\u00f3n consciente a lo que est\u00e1 ocurriendo a nuestro alrededor. <\/p>\n\n

Olvid\u00e9monos por un momento del problema que tenemos con la negaci\u00f3n, y fij\u00e9monos 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\u00e9 que x es un Ni\u00f1o, puedo generar un nuevo dato diciendo que x es tambi\u00e9n Persona: <\/p>\n\n

Ni\u00f1o(x) -> Persona(x)<\/p>\n\n

El problema principal de las TGDs es que pueden generar una cantidad infinita de datos, ya que la generaci\u00f3n de un nuevo dato puede provocar la ejecuci\u00f3n de la misma TGD, y as\u00ed indefinidamente. Por ejemplo, supongamos una TGD que dice que todo padre ha tenido otro padre: <\/p>\n\n

PadreDe(x, y) -> PadreDe(y, z) <\/p>\n\n

Claramente, cuando creamos una tupla PareDe, necesitamos crear otra tupla PareDe, y as\u00ed hasta el infinito.<\/p>\n\n

Para resolver este problema, la comunidad te\u00f3rica de BD ha estudiado condiciones que garantizan que una TGD no genera datos indefinidamente. Si una TGD solo puede ejecutarse, recursivamente, un m\u00e1ximo 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\u00e9n debe vivir en la tierra: <\/p>\n\n

Animal(x), ViveEn(x,Agua) -> ViveEn(x,Tierra).<\/p>\n\n

Esta TGD es one-bounded ya que, al crear nuevas tuplas de ViveEn, estas no pueden ejecutar de nuevo la misma regla.<\/p>\n\n

Volviendo a las consultas, existe una cierta relaci\u00f3n 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 \u201cTortuga\u201d 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\u00f3n, es bastante sencillo construir su correspondiente TGD que genera datos para falsarla. De hecho, basta con tomar la condici\u00f3n negada y a\u00f1adirla a la parte derecha de la TGD. <\/p>\n\n

El caso es que, en el art\u00edculo, demostramos que una query satisface el Teorema del Homomorfismo si y solo si su correspondiente TGD es one-bounded. La intuici\u00f3n principal es que, para probar que una consulta q1 est\u00e1 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\u00e9s de ejecutar la TGD una vez, pero falla para validar si q1 es cierta si se ejecuta la TGD varias veces recursivamente. <\/p>\n\n

No deja de ser po\u00e9tico ver que, en el mundo de las consultas de bases de datos, igual que en la investigaci\u00f3n, o como dir\u00eda 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\u00e1 la investigaci\u00f3n trata de buscar puentes entre distintos \u00e1mbitos. Quiz\u00e1 trata de comunicarlos de una manera llana para facilitar esa conexi\u00f3n a otra persona. Quiz\u00e1 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\u00f3n, te deseo mucho m\u00e1s que suerte. <\/p>\n\n

<\/p>\n","protected":false},"excerpt":{"rendered":"

La semana del 24 de Marzo, en Tampere (Finlandia), se celebr\u00f3 el congreso internacional conjunto de bases de datos EDBT\/ICDT, siendo el EDBT la comunidad que estudia nuevas tecnolog\u00edas en la pr\u00e1ctica, y el ICDT la comunidad que estudia el fundamento te\u00f3rico. El caso es que, este a\u00f1o, el inLab FIB ha tenido presencia en […]<\/p>\n","protected":false},"author":1302,"featured_media":35750,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[457],"tags":[],"experteses":[],"class_list":["post-35751","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-articles"],"acf":[],"_links":{"self":[{"href":"https:\/\/inlab.fib.upc.edu\/es\/wp-json\/wp\/v2\/posts\/35751","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/inlab.fib.upc.edu\/es\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/inlab.fib.upc.edu\/es\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/inlab.fib.upc.edu\/es\/wp-json\/wp\/v2\/users\/1302"}],"replies":[{"embeddable":true,"href":"https:\/\/inlab.fib.upc.edu\/es\/wp-json\/wp\/v2\/comments?post=35751"}],"version-history":[{"count":4,"href":"https:\/\/inlab.fib.upc.edu\/es\/wp-json\/wp\/v2\/posts\/35751\/revisions"}],"predecessor-version":[{"id":35762,"href":"https:\/\/inlab.fib.upc.edu\/es\/wp-json\/wp\/v2\/posts\/35751\/revisions\/35762"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/inlab.fib.upc.edu\/es\/wp-json\/wp\/v2\/media\/35750"}],"wp:attachment":[{"href":"https:\/\/inlab.fib.upc.edu\/es\/wp-json\/wp\/v2\/media?parent=35751"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/inlab.fib.upc.edu\/es\/wp-json\/wp\/v2\/categories?post=35751"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/inlab.fib.upc.edu\/es\/wp-json\/wp\/v2\/tags?post=35751"},{"taxonomy":"experteses","embeddable":true,"href":"https:\/\/inlab.fib.upc.edu\/es\/wp-json\/wp\/v2\/experteses?post=35751"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}