La setmana del 24 de Març, a Tampere (Finlàndia), es va cel·lebrar el congrés internacional conjunt de bases de dades EDBT/ICDT, essent l’EDBT la comunitat que n’estudia noves tecnologies a la pràctica, i l’ICDT la comunitat que n’estudia el fonament teòric. El cas és que, aquest any, l’inLab FIB ha tingut presència a l’ICDT amb un full paper de la mà de l’autor d’aquest mateix article. A partir d’aquí, la pregunta inevitable és… què fa un investigador en enginyeria del software en un congrés de teoria pura de bases de dades? Poden els investigadors més aviat pràctics aportar en un context absolutament teòric? Té sentit intentar-ho en un context on la IA s’ho està menjant tot?
La clau de tot plegat s’amaga en una pregunta encara més bèstia: per què vols investigar? En efecte, si el teu objectiu és fer-te un nom en la investigació, amb una mica de sort te tombaran cada article enviat amb suficient contundència com per desistir abans no acabis a teràpia (si no tu, els teus). I sí, s’acostuma a tenir molta, i molta sort en la investigació.
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 requisit habitual dels articles acadèmics és la utilització de petits exemples didàctics amb aire motivacional. Per continuar parafrasejant Foster Wallace, suposem que volem fer una consulta sobre una BD d’animals preguntant si hi ha registrats animals que viuen a l’aigua. En llenguatge Datalog, l’escriuríem més o menys així:
q1() :- Animal(x), ViuA(x,Aigua)
El cas és que també podríem estar interessats en una altra consulta semblant, per exemple, una consulta preguntant si tenim animals aquàtics que són mamífers:
q2() :- Animal(y), ViuA(y,Aigua), EsMamifer(y)
Clarament, la consulta q2 està continguda en q1, ja que, en resum, q2 està demanant el mateix que q1, però aplicant un filtre addicional (que seria la comprovació de EsMamífer). Adonar-nos del conteniment de consultes ens pot ajudar en diversos problemes, com el d’optimitzar el rendiment d’una base de dades, o fins i tot, trobar quins proveidors de dades ofereixen dades que poden interessar a un client.
Tot això està molt bé, però com diantre podem resoldre aquest problema? Doncs aquí tenim una molt bona notícia: desde fa més de 40 anys sabem que, si les consultes tenen una forma concreta (i molt freqüent!), una consulta q està continguda en una altra consulta q’ si, i només si, podem reescriure q’ en termes de q. En el nostre exemple, q2 és literalment la mateixa consulta que q1 però canviant la variable y per x i afegint una comprovació addicional EsMamifer. El millor de tot plegat és que aquesta comprovació es pot fer amb un test ben senzill: només hem de crear una BD que contingui tots els elements de la query q2 (substituint cada variable per una constant, per exemple, substituint la variable y per una constant #y), i si llancem la consulta q1 contra aquesta BD, la BD ja s’encarregarà de trobar que q2 és com q1 però canviant la variable x per y.
I quina és aquesta forma concreta que han de satisfer les consultes perquè tot això funcioni? En essència, la consulta ha de ser positiva, que vol dir que no pot tenir operacions matemàtiques (sumes, restes, o comparacions de més gran o més petit), ni tampoc condicions negades. És a dir, estem parlant de consultes SQL que només fan servir EQUI-JOINS. Essent formals, diem que una conjunctive query està continguda en una altra conjuntive query, en set-semantics, si existeix un homomorfisme des de la segona consulta a la primera (Teorema del Homomorfisme). El lector interessat pot trobar més detalls en el propi article, però no patiu, cap d’aquests formalismes no acaba sent excessivament complicat, ni s’allunya gaire de les intuicions aquí descrites. L’article pretén ser entenedor, fins al punt de perdre els dos grans avantatges dels textos inintel·ligibles que deia Foster Wallace: 1) com menys persones entenen l’article, més erudit se senten alguns autors (arribant a la màxima de Wilde on ni l’autor mateix entén el que diu), i 2) com menys persones entenen l’article, menys persones poden criticar-lo (arribant a la màxima de veure articles acceptats en congressos perquè ningú no els ha entès).
Però no ens posem tant negatius, i parlem de què passa quan afegim negació a les consultes. Per exemple, posem per cas que ara demanem si existeixen animals que viuen a l’aigua però que no viuen a terra:
q3() :- Animal(y), ViuA(y,Aigua), not ViuA(y, Terra).
En resum, quan les consultes tenen negació, el Teorema del Homomorfisme falla. És a dir, hi ha consultes contingudes en d’altres, tot i no poder reescriure una en termes de l’altra. El trencament del Teorema del Homomorfisme és bastant fomut, ja que mentre implementar un test d’homorfisme és bastant senzill, els tests que s’han ideat per comprovar el conteniment de dos consultes amb negació són, en general, difícils i computacionalment complexos. Com a enginyer del software, m’agraden les idees d’implementació senzilles, pel que confesso que aquí em vaig encallar bastant mirant de trobar una caracterització que digui quan una consulta, fins i tot amb negació, satisfà el Teorema de l’Homomorfisme, per així fer ús d’aquest test. No vulgueu saber l’embolic en què m’estava ficant jo mateix construint, incrementalment, una caracterització sumament intel·ligent en termes de Wilde per resoldre un problema cada cop més frustrant i cada cop més desmotivador.
A l’Aigua és Això, Foster Wallace deia que la principal habilitat que s’adquireix a la universitat no és la de pensar, sinó decidir què pensar. Davant de les adversitats, abans de continuar maleint-nos els ossos, Foster Wallace ens convida a sortir del nostre monòleg intern i prendre una atenció, conscient, del que està passant al nostre voltant.
Oblidem-nos per un moment del problema que tenim amb la negació, i fixem-nos en un altre formalisme anomenat tuple-generating dependencies (TGD). Una TGD és una regla que, a partir d’unes dades de la BD, en genera unes altres. Per exemple, podem tenir una TGD que diu que si sé que x és un Nen, puc generar una nova dada dient que x és també Persona:
Nen(x) -> Persona(x)
El problema principal de les TGDs és que poden generar una quantitat infinita de dades, ja que la generació d’una nova dada pot provocar l’execució de la mateixa TGD, i així indefinidament. Per exemple, suposem una TGD que diu que tot pare ha tingut un altre pare:
PareDe(x, y) -> PareDe(y, z)
Clarament, quan creem una tupla PareDe, necessitem crear una altra tupla PareDe, i així fins a l’infinit.
Per resoldre aquest problema, la comunitat teòrica de BD ha estudiat condicions que garanteixen que una TGD no genera dades indefinidament. Si una TGD només pot executar-se, recursivament, un màxim de 5 vegades, diem que la TGD és 5-bounded. Similarment, si quan executem una TGD, no la podem reexecutar recursiva un altre cop, diem que la TGD és one-bounded. Per exemple, imaginem una TGD que, en resum, diu que si un animal viu a l’aigua, també ha de viure a terra:
Animal(x), ViuA(x, Aigua) -> ViuA(x, Terra).
Aquesta TGD és one-bounded ja que, al crear noves tuples de ViuA, aquestes no poden executar de nou la mateixa regla.
Tornant a les consultes, hi ha una certa relació entre aquestes i les TGDs. En particular, l’anterior TGD representa les dades que s’han de crear per insatisfer la query q3. En efecte, cada instància de dades que pot satisfer q3 (per exemple, si trobem un animal “Tortuga” que viu a l’Aigua però no a Terra), es pot usar en la TGD per crear una nova dada (ViuA(Tortuga, Terra)) que invalida q3. Donada una consulta amb negació, és bastant senzill construir la seva corresponent TGD que genera dades per falsar-la. De fet, n’hi ha prou amb prendre la condició negada, i afegir-la a la part dreta de la TGD.
El cas és que, a l’article, demostrem que una query satisfà el Teorema de l’Homomorfisme si i només si la seva corresponent TGD és one-bounded. La intuició principal és que, per provar que una consulta q1 està continguda en una altra q2, n’hi ha prou en analitzar si, sobre una BD on q1 és cert, es pot executar la TGD de q2, de manera que insatisfem q2, però seguim satisfent q1. El cas és que el test d’homomorfisme s’encarrega de validar que q1 segueix sent cert després d’executar la TGD un cop, però falla per validar si q1 és cert si s’executa la TGD diverses vegades recursivament.
No deixa de ser poètic veure que, en el món de les consultes de bases de dades, igual que en la investigació, o com diria Foster Wallace, en les trinxeres de la vida adulta quotidiana, la incapacitat de deixar de buclar en un mateix ens impedeix trobar una resposta senzilla i sincera en el nostre entorn. Potser la investigació tracta de buscar ponts entre diferents àmbits. Potser tracta de comunicar-los d’una manera planera per facilitar aquesta connexió a algú altra. Potser tracta d’un exercici conscient de construir, entre tots, quelcom positiu per capgirar tanta negativitat. Vingui’s d’on vingui’s, si et vols dedicar a la investigació, et desitjo molt més que sort.