Canonicalisation of SPARQL Queries

Abstract

SPARQL es el lenguaje de consulta estándar para RDF, definido por el World Wide Web Consortium. Presentemente, hay una gran cantidad de servicios de consulta de SPARQL en la Web. También hay una gran demanda por estos servicios diariamente. Debido a la gran cantidad de consultas que deben procesar estos servicios, los procesadores sufren una sobrecarga que podría ser reducida si fuésemos capaces de detectar consultas equivalentes. Nuestra propuesta consiste en el diseño y la implementación de un algoritmo de canonicalización eficiente, el cual nos permitirá computar una forma canónica para las consultas. Las consultas que sean equivalentes deben tener la misma forma canónica, lo cual haría posible detectar un mayor número de consultas duplicadas. Hemos cubierto una parte significante de SPARQL 1.0 con nuestro trabajo; principalmente consultas que tengan la forma de uniones de consultas conjuntivas. El algoritmo que hemos desarrollado realiza una canonicalización completa de las consultas que contienen estas operaciones. Para las otras operaciones, realizamos una canonicalización parcial, pues estas otras operaciones son usadas popularmente en consultas reales. Hemos diseñado experimentos para probar la correctitud y el desempeño de nuestro algoritmo en comparación contra otros métodos sintácticos. Realizamos nuestros experimentos sobre consultas reales extraídas de bitácoras de bases de datos de RDF, y también sobre consultas sintéticas que diseñamos para forzar un mal comportamiento del algoritmo. Los resultados de nuestros experimentos son excitosos, pues la mayoría de las consultas reales son procesables en un tiempo corto, menor a un segundo. El número de consultas duplicadas encontradas es considerablemente superior que las encontradas por el algoritmo base definido. Finalmente, el algoritmo deja de funcionar únicamente para las consultas sintéticas diseñadas por nosotros, y de una gran complejidad, las cuales no ocurren en la práctica. El siguiente documento presenta el trabajo hecho.