Bases de Datos en Grafos: cuando las apariencias no engañan

La forma en que las aplicaciones modernas estructuran sus datos está rompiendo con lo que se conocía como “bases de datos relacionales” para modelarse estructuralmente a través de grafos. Sin embargo, hasta el momento los estudios de bases de datos de grafos se han centrado en la topología del grafo subyacente y han prestado poca atención a aquellas consultas que representan cabalmente la manera en que los datos se relacionan con esta misma topología.

Hoy en día los grafos están presentes en todos lados, desde las redes sociales hasta las citas bibliográficas y las bases de datos biológicas, entre muchos otros fenómenos naturales y humanos. Pero, ¿qué se entiende como “grafo”? Un grafo es una estructura compuesta de puntos que se conocen como nodos o vértices, los cuales están unidos a través de flechas que reciben el nombre de aristas. Como estructuras matemáticas de objetos relacionados en forma binaria, los grafos encuentran interés no sólo desde la matemática –en tanto estructura algebraica– sino también desde la lógica: se trata de modelos que permiten expresar propiedades fundamentales de la matemática y que, por este motivo, tienen un impacto significativo en el conocimiento de los lenguajes formales.

El ICC cuenta con un grupo de Lógica y Computabilidad, que se ocupa de abordar áreas fundamentales de la disciplina computacional -teoría de base de datos, teoría de la computabilidad e información cuántica y también cuestiones de cognición- con aplicaciones muy concretas, en este caso hacia los lenguajes de consulta de bases de datos estructuradas en grafos. Estas bases se representan como grafos (dirigidos) cuyas aristas contienen etiquetas (atributos) provenientes de un alfabeto finito y sus nodos contienen valores de datos provenientes de un dominio infinito.

“En nuestro grupo de investigación estudiamos, entre muchas otras cosas, lenguajes de consulta que sean lo más ricos posibles para expresar propiedades sobre grafos al tiempo que mantienen buenas propiedades computacionales. Un ejemplo son las propiedades de caminos, porque al responder a cierto patrón lógico, por ejemplo, si existe un camino con tales o cuales propiedades desde un cierto nodo ‘a’ hasta un nodo ‘b’, nos brindan información fundamental”, puntualiza Santiago Figueira, investigador del ICC y director del grupo de Lógica y Computabilidad.

“En este contexto, un camino de un grafo no es necesariamente algo lineal sino la descripción de una forma de conectar dos nodos. Una de las ventajas características de las bases de datos estructuradas en grafos es que a través del lenguaje –entendido como un mecanismo sintáctico formal– se puede exhibir directamente la topología de los datos, conocer similitudes entre la topología de diferentes grafos entre sí y facilitar su manipulación algorítmica para luego ser implementados. Existen grafos que tienen millones de datos y no pueden ser representados fácilmente. El desafío aquí es diseñar lenguajes expresivos que a la vez soporten ser ejecutados en estructuras tan grandes.

Con el crecimiento de grandes volúmenes de información (como parte del fenómeno de Big Data) ya sea en las redes sociales, las redes de citas bibliográficas, la web semántica o las bases de datos biológicas, el fenómeno de la consulta (querying) se ha convertido en un tema altamente desafiante entre los investigadores en computación. “No obstante, la mayoría de los proyectos científicos en este tema se han centrado en la exploración de la topología del grafo subyacente y no tanto en las consultas que controlan de qué manera los datos contenidos en el grafo (así sean amigos en una red social, autores de libros, palabras, referencias textuales o datos genéticos, etc.) se relacionan con la topología”, comenta Figueira, quien es doctor en Ciencias de la Computación.

A través de lenguajes de consulta que permiten comparar los valores de los datos, el proyecto académico liderado por Figueira “Lenguajes data-aware sobre bases de datos estructuras en grafos” pretende diseñar y estudiar nuevos lenguajes formales de especificaciones que aporten más información sobre cómo los datos cambian a lo largo de los patrones topológicos que los rodean. Para ello están utilizando XPath, un lenguaje originalmente pensado para razonar sobre “árboles”, que permite construir expresiones que recorren y procesan un documento XML. El enfoque es lógico y quizá el antecedente más claro sea el de las Lógicas Modales: lenguajes que también permiten razonar sobre grafos etiquetados pero de una forma mucho más restrictiva que XPath.

En este proyecto también participa Sergio Abriola (investigador en formación del ICC), María Vanina Martínez (investigadora formada del ICC) e investigadores franceses asociados en cooperación.

Uno de los problemas centrales, de complejidad computacional, que aborda el proyecto es el de la satisfacibilidad (SAT), que podría resumirse como: dada una consulta, ¿existe una base de datos que la hace verdadera? Se plantea hasta dónde los lenguajes formales permiten expresar propiedades de modo tal que la pregunta antes mencionada sea computable, es decir, que una computadora pueda automáticamente decidir si la respuesta a la pregunta es por “sí” o por “no”. En otras palabas se estudia cuál es el límite de expresividad de estos lenguajes.

“En general los lenguajes de consulta que permiten razonar sobre los datos son indecidibles, o sea, la pregunta de satisfacibilidad no es computable. Al agregar poder expresivo a los lenguajes, uno corre el riesgo de caer en lo indecidible: le pedimos tanto al lenguaje que se vuelve no computable. Entonces uno busca un balance, entre ser expresivo pero a la vez tener buen comportamiento computacional, uno busca un lenguaje que sirva para modelar nuevos problemas”, argumenta Figueira. En este aspecto, el investigador aclara que la clase de complejidad P (tiempo polinomial) no es el único con “buen” comportamiento computacional, ya que “en lógica y teoría de autómatas existen problemas decidibles con complejidad mucho más alta que P y aún así son considerados ‘medianamente tratables”, concluye.

¿Por qué P Vs. NP sigue siendo un problema tan vigente para la Computación y fuertemente relacionado con el problema de SAT?
“Es una cuestión que atraviesa muchísimas áreas de la Computación. Un problema está en P si puede ser resuelto con una computadora en tiempo polinomial con respecto al tamaño de la entrada, en este caso, un grafo que representa la base de datos. El problema NP por excelencia busca decidir si una fórmula de la Lógica Proposicional es o no satisfacible. Se llama ‘Problema SAT para Lógica Proposicional’ y, como todo problema en NP, sabemos resolverlo en tiempo polinomial con una computadora en cierta forma ‘tramposa’, no determinística, que lanza tantos procesos en paralelo como hagan faltan; sin embargo no sabemos si se puede resolver en tiempo polinomial con una computadora, no tramposa, digamos, una máquina determinística clásica. Sabemos que P está incluido en NP (porque una computadora no tramposa puede ser programada para no hacer trampa) pero no sabemos si son iguales o no. Alan Turing demostró a mediados de la década del ’30 que la Lógica de Primer Orden era indecidible, es decir, que ningún método efectivo (o, al menos, lo que él mismo se preocupó de definir formalmente como “método efectivo”, las máquinas de Turing) podía resolver el problema de SAT para la Lógica de Primer Orden. Esto mismo también lo demostró Church independientemente y usando otro formalismo para “lo efectivo”. El resultado de Turing se basa en el famoso ‘Problema de la Parada’ (Halting Problem): ¿existe un programa que tome como entrada un programa p y una entrada x y nos diga si el programa p con entrada x termina o se cuelga? Turing demostró que no, que ese “decididor” universal no existe. Aún así los lógicos tenemos otras clases de complejidad interesantes, como PSPACE, que incluye NP (que a su vez incluye a P). Esta es la clase de problemas de decisión que pueden ser resueltos por una computadora clásica usando una cantidad de memoria polinomial con respecto al tamaño de la entrada. Es decir, usamos una máquina de Turing determinística con espacio polinomial y tiempo ilimitado (aunque siempre finito). Más allá de esta ventaja, esta clase, en general, no resulta familiar para quienes desarrollan algoritmos para grafos porque no hay muchos problemas en teoría de grafos que se resuelvan con algoritmos en esta clase. Todavía existen diversos problemas lógicos para los cuales no se conoce la complejidad precisa o incluso si son o no computables. En cierto modo, esto sigue motivando nuestras investigaciones”, reflexiona Figueira.