Canonicalisation of Sparql 1.1 queries

Abstract

SPARQL es el lenguaje de consulta est´andar para RDF de acuerdo al World Wide Web Consortium (W3C). Es un lenguaje de consulta altamente expresivo que contiene las operaciones est´andares del ´algebra relacional tales como los joins, la uni´on, los outer joins, etc. adem´as 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´antica. Por ejemplo, un sistema de cach´e podr´ıa funcionar m´as eficientemente si fuese capaz de detectar estas consultas equivalentes. Se propone una t´ecnica de canonicalizaci´on como una soluci´on a este problema, de manera que se computa una forma can´onica para las consultas SPARQL donde todas las consultas son equivalentes m´odulo nombres de variables (o congruentes) a su forma can´onica, y para un subconjunto del lenguaje, todas las consultas congruentes tienen la misma forma can´onica. Se describen en detalle los pasos que componen este m´etodo de canonicalizaci´on: la normalizaci´on algebraica, la representaci´on de la consulta como un grafo RDF, la minimizaci´on de las componentes mon´otonas de la consulta, y la rotulaci´on can´onica de las variables. A pesar de la alta complejidad te´orica del problema, los experimentos demuestran el buen comportamiento del m´etodo en consultas enviadas por usuarios reales. Finalmente, se discuten posibles casos de uso en sistemas de cach´e, an´alisis de consultas, query benchmarking, etc.

SPARQL is the standard query language for RDF as recommended by the World Wide Web Consortium (W3C). It is a highly expressive query language that contains the standard operations based on set algebra such as joins, unions, outer joins, etc. as well as navigational operations found in graph querying languages. Because of this, there are various ways to represent the same query, which may lead to redundancies in applications of the Semantic Web such as caching systems, where cached results could be returned if the systems were capable of detecting these duplicates. We propose a canonicalisation technique as a solution, where we compute a canonical form for SPARQL queries such that all queries are equivalent modulo variable names (congruent) to their canonical form, and where for a subset of the language, all congruent queries will have the same canonical form. We describe in full detail the steps that comprise our canonicalisation method: the algebraic rewriting, the representation of the query as an RDF graph, the minimisation of monotone sub-queries, and the canonical labelling. Despite the theoretical complexity of this problem, our experiments show good performance over real-world queries. Finally, we anticipate applications in caching, log analysis, query benchmarking, etc.