Noticias
Mayo, 2021.- El artículo “When is Approximate Counting for Conjunctive Queries Tractable?”, de Marcelo Arenas, académico U. Católica y director IMFD; Luis Alberto Croquevielle, alumno graduado de magíster U. Católica e IMFD; Rajesh Jayaram, alumno de doctorado Carnegie Mellon University, y Cristian Riveros, académico U. Católica e investigador IMFD fue aceptado en el 53rd ACM Symposium on Theory of Computing de 2021, que se realizará de forma virtual en junio de este año. En este trabajo de investigación, se proponen soluciones para ciertos tipos de consulta en sistemas de bases de datos, las consultas conjuntivas o “conjunctive queries”, que forman la clase de consultas más utilizadas y estudiadas en este tipo de sistemas.
El ACM Symposium on Theory of Computing (STOC) es la conferencia más importante a nivel internacional en el área de teoría de la computación.
Sobre la investigación, Marcelo Arenas explica: “El desarrollo de bases de datos usualmente implica tratar de conseguir respuestas completas y precisas a las consultas. Si uno quisiera, por ejemplo, que una base de datos nos entregue la lista de alumnos de un curso, necesitamos que la entregue completa, no con el 90% de la información”. Pero, cuando hay volúmenes grandes de información, empieza a perder sentido la idea de calcular respuestas completas.
“Por ejemplo, si busco la lista de personas en Wikipedia, me da muchos resultados, por lo que puede ser una mejor alternativa ver las primeras 10 personas, las siguientes 10, y así sucesivamente. Luego, puedo necesitar saber cuales nacieron en una cierta región geográfica, lo que es una consulta más compleja pues requiere hacer un cruce de datos”, explica. Y para tener una idea general, que nos permita conocer mejor al grupo que queremos estudiar, es relevante saber la cantidad total de resultados, y poder visualizar algunos de los casos.
En este contexto, para lograr respuestas significativas desde grandes cantidades de información, se establece una estrategia que contempla la integración de tres alternativas que se complementan: poder enumerar los resultados según algún criterio (tener los primeros 10, los siguientes 10, y así sucesivamente); conseguir respuestas variadas en sus características de búsqueda con cierto nivel de azar; y poder conocer el total de los resultados.
Esto, porque normalmente los algoritmos que calculan respuestas a consultas muy rápido tienden a ser sesgados, lo que hacen es pre-calcular algo: “Esto quiere decir que cuando pedimos una respuesta, el algoritmo ya tiene algo precalculado, y cuando pedimos la siguiente, lo que hace es moverse dentro de esa misma estructura, entregando respuestas muy parecidas”.
Por ende, para conseguir una visión que podríamos calificar como real, es necesario contar con variedad, lo que es posible conseguir haciendo una selección de respuestas al azar, considerando una distribución uniforme dentro del universo conocido. Y, para conocer el tamaño del universo, necesitamos saber el total de los resultados.
Este tipo de problemas son técnicos cuando se plantean a nivel de bases de datos, pero pueden tener aplicaciones y usos muy relevantes para la sociedad, por ejemplo, al momento de definir necesidades para crear políticas públicas. “Pensar que vamos a analizar todas las bases de datos disponibles en diferentes plataformas para definir quienes serán beneficiados por una política pública, es irracional. Pero sí podemos, primero, saber el total de personas; luego hacer consultas que nos permitan cruzar datos de diferentes fuentes y características -como puede ser el nivel educacional y la ubicación geográfica, provenientes incluso de bases de datos distintas- y también visualizar casos específicos (siempre considerando que todos estos datos deben ser anonimizados), por ejemplo, sacar cierta cantidad de casos por región, o comuna, que nos permitan ver diferencias geográficas; podemos entonces tener una idea bastante completa y basada en información real, en la cual basar las decisiones.
En este trabajo, los investigadores se enfocaron en estos tres problemas: enumeración, generación uniforme y conteo. “Los tomamos como tres problemas que tienen que ser estudiados juntos. En general, estos son problemas difíciles desde el punto de vista computacional, por lo que hicimos fue proponer una solución para cierto tipo de consultas”, por eso se enfocaron en un fragmento que permite abarcar los tres problemas en conjunto: la clase de consultas conjuntiva, que son las más comunes en base de datos y que permiten cruzar datos para entenderlos. “La idea de cruzar información -join- es una operación básica e importante. En este artículo demostramos que es posible solucionar de manera eficiente los problemas de enumeración, generación uniforme y conteo aproximado para una clase de consultas que está muy bien definida, y que es muy utilizada”, explica Marcelo Arenas.
STOC cubre todas las áreas de investigación relacionadas con teorías de la computación y algoritmos. Las investigaciones destacadas por este grupo son aquellas que amplían el alcance de la teoría de la computación, o que plantean problemas importantes que pueden beneficiarse de la investigación y el análisis teórico.
Los temas de interés incluyen, entre otros: algoritmos y estructuras de datos, complejidad computacional, aleatoriedad en computación, teoría de grafos algorítmicos y combinatoria, algoritmos de aproximación, criptografía, teoría del aprendizaje computacional, economía y computación, algoritmos paralelos y distribuidos, computación cuántica, teoría de codificación algorítmica, geometría computacional, aplicaciones computacionales de lógica, optimización, algoritmos algebraicos y aspectos teóricos de áreas como redes, privacidad, biología computacional y bases de datos.
