{"id":1221,"date":"2018-02-20T12:22:29","date_gmt":"2018-02-20T15:22:29","guid":{"rendered":"https:\/\/icc.fcen.uba.ar\/?p=1221"},"modified":"2022-03-29T10:40:58","modified_gmt":"2022-03-29T13:40:58","slug":"bases-de-datos-en-grafos-cuando-las-apariencias-no-enganan","status":"publish","type":"post","link":"https:\/\/icc.fcen.uba.ar\/en\/bases-de-datos-en-grafos-cuando-las-apariencias-no-enganan\/","title":{"rendered":"Bases de Datos en Grafos: cuando las apariencias no enga\u00f1an"},"content":{"rendered":"

La forma en que las aplicaciones modernas estructuran sus datos est\u00e1 rompiendo con lo que se conoc\u00eda como \u201cbases de datos relacionales\u201d para modelarse estructuralmente a trav\u00e9s de grafos. Sin embargo, hasta el momento los estudios de bases de datos de grafos se han centrado en la topolog\u00eda del grafo subyacente y han prestado poca atenci\u00f3n a aquellas consultas que representan cabalmente la manera en que los datos se relacionan con esta misma topolog\u00eda.<\/strong><\/em><\/p>\n

Hoy en d\u00eda los grafos est\u00e1n presentes en todos lados, desde las redes sociales hasta las citas bibliogr\u00e1ficas y las bases de datos biol\u00f3gicas, entre muchos otros fen\u00f3menos naturales y humanos. Pero, \u00bfqu\u00e9 se entiende como \u201cgrafo\u201d? Un grafo es una estructura compuesta de puntos que se conocen como nodos o v\u00e9rtices, los cuales est\u00e1n unidos a trav\u00e9s de flechas que reciben el nombre de aristas. Como estructuras matem\u00e1ticas de objetos relacionados en forma binaria, los grafos encuentran inter\u00e9s no s\u00f3lo desde la matem\u00e1tica \u2013en tanto estructura algebraica\u2013 sino tambi\u00e9n desde la l\u00f3gica: se trata de modelos que permiten expresar propiedades fundamentales de la matem\u00e1tica y que, por este motivo, tienen un impacto significativo en el conocimiento de los lenguajes formales.
\n<\/span><\/p>\n

El ICC cuenta con un grupo de L\u00f3gica y Computabilidad<\/strong>, que se ocupa de abordar \u00e1reas fundamentales de la disciplina computacional -teor\u00eda de base de datos, teor\u00eda de la computabilidad e informaci\u00f3n cu\u00e1ntica y tambi\u00e9n cuestiones de cognici\u00f3n- 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.
\n<\/span>
\n\u201c<\/span>En nuestro grupo de investigaci\u00f3n estudiamos, entre muchas otras cosas, lenguajes de consulta que sean lo m\u00e1s 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\u00f3n l\u00f3gico, por ejemplo, si existe un camino con tales o cuales propiedades desde un cierto nodo \u2018a\u2019 hasta un nodo \u2018b\u2019, nos brindan informaci\u00f3n fundamental\u201d<\/span><\/i>, puntualiza Santiago Figueira<\/strong>, investigador del ICC y director del grupo de L\u00f3gica y Computabilidad.<\/p>\n

\u201c<\/span>En este contexto, un camino de un grafo no es necesariamente algo lineal sino la descripci\u00f3n de una forma de conectar dos nodos. Una de las ventajas caracter\u00edsticas de las bases de datos estructuradas en grafos es que a trav\u00e9s del lenguaje \u2013entendido como un mecanismo sint\u00e1ctico formal\u2013 se puede exhibir directamente la topolog\u00eda de los datos, conocer similitudes entre la topolog\u00eda de diferentes grafos entre s\u00ed y facilitar su manipulaci\u00f3n algor\u00edtmica para luego ser implementados. Existen grafos que tienen millones de datos y no pueden ser representados f\u00e1cilmente. El desaf\u00edo aqu\u00ed es dise\u00f1ar lenguajes expresivos que a la vez soporten ser ejecutados en estructuras tan grandes.
\n<\/span><\/p>\n

Con el crecimiento de grandes vol\u00famenes de informaci\u00f3n (como parte del fen\u00f3meno de Big Data) ya sea en las redes sociales, las redes de citas bibliogr\u00e1ficas, la web sem\u00e1ntica o las bases de datos biol\u00f3gicas, el fen\u00f3meno de la consulta (querying) se ha convertido en un tema altamente desafiante entre los investigadores en computaci\u00f3n. \u201cNo obstante, la mayor\u00eda de los proyectos cient\u00edficos en este tema se han centrado en la exploraci\u00f3n de la topolog\u00eda del grafo subyacente y no tanto en las consultas que controlan de qu\u00e9 manera los datos contenidos en el grafo (as\u00ed sean amigos en una red social, autores de libros, palabras, referencias textuales o datos gen\u00e9ticos, etc.) se relacionan con la topolog\u00eda\u201d<\/i>, comenta Figueira, quien es doctor en Ciencias de la Computaci\u00f3n.
\n<\/span><\/p>\n

\"\"A trav\u00e9s de lenguajes de consulta que permiten comparar los valores de los datos, el proyecto acad\u00e9mico liderado por Figueira \u201cLenguajes data-aware sobre bases de datos estructuras en grafos\u201d pretende dise\u00f1ar y estudiar nuevos lenguajes formales de especificaciones que aporten m\u00e1s informaci\u00f3n sobre c\u00f3mo los datos cambian a lo largo de los patrones topol\u00f3gicos que los rodean. Para ello est\u00e1n utilizando XPath, un lenguaje originalmente pensado para razonar sobre \u201c\u00e1rboles\u201d, que permite construir expresiones que recorren y procesan un documento XML. El enfoque es l\u00f3gico y quiz\u00e1 el antecedente m\u00e1s claro sea el de las L\u00f3gicas Modales: lenguajes que tambi\u00e9n permiten razonar sobre grafos etiquetados pero de una forma mucho m\u00e1s restrictiva que XPath.
\n<\/span><\/p>\n

En este proyecto tambi\u00e9n participa Sergio Abriola (investigador en formaci\u00f3n del ICC), Mar\u00eda Vanina Mart\u00ednez (investigadora formada del ICC) e investigadores franceses asociados en cooperaci\u00f3n.
\n<\/span><\/p>\n

Uno de los problemas centrales, de complejidad computacional, que aborda el proyecto es el de la satisfacibilidad (SAT), que podr\u00eda resumirse como: dada una consulta, \u00bfexiste una base de datos que la hace verdadera? Se plantea hasta d\u00f3nde los lenguajes formales permiten expresar propiedades de modo tal que la pregunta antes mencionada sea computable, es decir, que una computadora pueda autom\u00e1ticamente decidir si la respuesta a la pregunta es por \u201cs\u00ed\u201d o por \u201cno\u201d. En otras palabas se estudia cu\u00e1l es el l\u00edmite de expresividad de estos lenguajes.
\n<\/span><\/p>\n

\u201c<\/span>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\u201d<\/span><\/i>, argumenta Figueira. En este aspecto, el investigador aclara que la clase de complejidad P (tiempo polinomial) no es el \u00fanico con \u201cbuen\u201d comportamiento computacional, ya que \u201cen l\u00f3gica y teor\u00eda de aut\u00f3matas existen problemas decidibles con complejidad mucho m\u00e1s alta que P y a\u00fan as\u00ed son considerados \u2018medianamente tratables<\/em>\u201d, concluye.<\/p>\n

\n

\"\"\u00bfPor qu\u00e9 P Vs. NP sigue siendo un problema tan vigente para la Computaci\u00f3n y fuertemente relacionado con el problema de SAT?<\/b>
\n\u201c<\/span>Es una cuesti\u00f3n que atraviesa much\u00edsimas \u00e1reas de la Computaci\u00f3n. Un problema est\u00e1 en P si puede ser resuelto con una computadora en tiempo polinomial con respecto al tama\u00f1o de la entrada, en este caso, un grafo que representa la base de datos. El problema NP por excelencia busca decidir si una f\u00f3rmula de la L\u00f3gica Proposicional es o no satisfacible. Se llama \u2018Problema SAT para L\u00f3gica Proposicional\u2019 y, como todo problema en NP, sabemos resolverlo en tiempo polinomial con una computadora en cierta forma \u2018tramposa\u2019, no determin\u00edstica, 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\u00e1quina determin\u00edstica cl\u00e1sica. Sabemos que P est\u00e1 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\u00f3 a mediados de la d\u00e9cada del \u201930 que la L\u00f3gica de Primer Orden era indecidible, es decir, que ning\u00fan m\u00e9todo efectivo (o, al menos, lo que \u00e9l mismo se preocup\u00f3 de definir formalmente como \u201cm\u00e9todo efectivo\u201d, las m\u00e1quinas de Turing) pod\u00eda resolver el problema de SAT para la L\u00f3gica de Primer Orden. Esto mismo tambi\u00e9n lo demostr\u00f3 Church independientemente y usando otro formalismo para \u201clo efectivo\u201d. El resultado de Turing se basa en el famoso \u2018Problema de la Parada\u2019 (Halting Problem): \u00bfexiste 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\u00f3 que no, que ese \u201cdecididor\u201d universal no existe. A\u00fan as\u00ed los l\u00f3gicos 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\u00f3n que pueden ser resueltos por una computadora cl\u00e1sica usando una cantidad de memoria polinomial con respecto al tama\u00f1o de la entrada. Es decir, usamos una m\u00e1quina de Turing determin\u00edstica con espacio polinomial y tiempo ilimitado (aunque siempre finito). M\u00e1s all\u00e1 de esta ventaja, esta clase, en general, no resulta familiar para quienes desarrollan algoritmos para grafos porque no hay muchos problemas en teor\u00eda de grafos que se resuelvan con algoritmos en esta clase. Todav\u00eda existen diversos problemas l\u00f3gicos para los cuales no se conoce la complejidad precisa o incluso si son o no computables. En cierto modo, esto sigue motivando nuestras investigaciones\u201d, <\/span><\/i>reflexiona Figueira.<\/span>
\n<\/span><\/i><\/p>\n<\/blockquote>\n<\/div>

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

La forma en que las aplicaciones modernas estructuran sus datos est\u00e1 rompiendo con lo que se conoc\u00eda como \u201cbases de datos relacionales\u201d para modelarse estructuralmente a trav\u00e9s de grafos. Sin embargo, hasta el momento los estudios de bases de datos de grafos se han centrado en […]<\/p>\n","protected":false},"author":3,"featured_media":1265,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[71,12],"tags":[25,48,24,42],"class_list":["post-1221","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-actualidad","category-noticias","tag-computo","tag-grafos","tag-teoria","tag-turing"],"_links":{"self":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/1221","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/comments?post=1221"}],"version-history":[{"count":7,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/1221\/revisions"}],"predecessor-version":[{"id":2176,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/1221\/revisions\/2176"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media\/1265"}],"wp:attachment":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media?parent=1221"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/categories?post=1221"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/tags?post=1221"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}