"Canonicalisation of SPARQL 1.1 Queries" se titula el trabajo de tesis con el que el investigador Jaime Salas obtuvo recientemente el grado de Doctor en Computación de la Universidad de Chile, el cual fue guiado por el académico del DCC, Aidan Hogan.

El investigador explica que en este trabajo diseña una forma canónica para consultas de SPARQL, “tal que cualquier consulta que devuelva las mismas respuestas va a tener la misma forma canónica. Es como la idea que +2, 2.000, y -(-2) pueden tener la forma canónica 2. Nótese que esta forma canónica tiene sus limitaciones para consultas más complejas (que tienen filtros, negación, por ejemplo), porque se pueden diseñar consultas que son iguales pero van a tener distintas formas canónicas. Sin embargo, la gracia de lo que se hizo fue que para consultas que sólo tienen joins, uniones y proyecciones, no existe ese problema. Además de diseñar la forma canónica, diseñé un algoritmo que dado una consulta, devuelve la forma canónica de esa consulta. Esto era también para demostrar que, a pesar de ser un problema teóricamente difícil, el proceso podía ser eficiente (hacerse en poco tiempo) para la mayoría de las consultas que uno ve en el día a día. Se hicieron experimentos sobre un gran número de consultas extraídas de sistemas reales, y se vio que la gran mayoría se procesaba en menos de 100ms. Finalmente, discutimos que el trabajo tiene aplicaciones prácticas, sin embargo aquí es donde hay más trabajo para el futuro”.

Agrega que uno de los principales desafíos que abordó durante el desarrollo de este trabajo, fue “ahondar en la teoría detrás del álgebra relacional, reaprender muchos temas de la teoría de la computación que no comprendí del todo durante mi pregrado y perseverar por tantos años para terminar el doctorado”.

Jaime Salas, es Magíster en Ciencias mención Computación e Ingeniero Civil en Computación de la Universidad de Chile. En 2018, junto al profesor Aidan Hogan, obtuvieron el premio el Best Student Paper Award en la International Semantic Web Conference (ISWC), la más importante en el área de web semántica, con el trabajo  "Canonicalisation of Monotone SPARQL Queries". Actualmente, se encuentra realizando un postdoctorado de tres años en la Universidad de Southampton en el Reino Unido. 

¡Felicitaciones!

Resumen "Canonicalisation of SPARQL 1.1 Queries" 

SPARQL es el lenguaje de consulta estándar para RDF de acuerdo al World Wide Web Consortium (W3C). Es un lenguaje de consulta altamente expresivo que contiene las operaciones estándares del álgebra relacional tales como los joins, la unión, los outer joins, etc. además de operaciones propias de los lenguajes de consulta para grafos. Debido a esto, existen varias maneras de representar la misma consulta que no son triviales de determinar, lo cual puede causar ineficiencias en aplicaciones de la Web Semántica. Por ejemplo, un sistema de caché podría funcionar más eficientemente si fuese capaz de detectar estas consultas equivalentes. 

Se propone una técnica de canonicalización como una solución a este problema, de manera que se computa una forma canónica para las consultas SPARQL donde todas las consultas son equivalentes módulo nombres de variables (o congruentes) a su forma canónica, y para un subconjunto del lenguaje, todas las consultas congruentes tienen la misma forma canónica.

Se describen en detalle los pasos que componen este método de canonicalización: la normalización algebraica, la representación de la consulta como un grafo RDF, la minimización de las componentes monótonas de la consulta, y la rotulación canónica de las variables. A pesar de la alta complejidad teórica del problema, los experimentos demuestran el buen comportamiento del método en consultas enviadas por usuarios reales.

Finalmente, se discuten posibles casos de uso en sistemas de caché, análisis de consultas, query benchmarking, etc.

--
Comunicaciones DCC