Semantics and complexity of SPARQL 1.1 property paths
Loading...
Date
2012
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
SPARQL - el lenguaje de consultas standar para bases de datos RDF - proporciona sólo funcionalidades limitadas de navegación, sin embargo, estas características son de fundamental importancia en los modelos de datos basadas en grafos, como es el caso de RDF. Esto ha llevado a la W3C ha incluir funcionalidades como property path en la próxima versión del standar, SPARQL 1.1. Se han puesto a prueba distintas implementaciones de SPARQL 1.1 que manejan consultas con property paths, observando un bajo rendimiento en sus métodos de evaluación para este tipo de consultas, incluso, para escenarios simples.
En búsqueda de una explicación formal a este comportamiento, se ha realizado un estudio de la complejidad computacional de la evaluación de consultas con property paths. Los resultados muestran que el bajo rendimiento de las implementaciones probadas, no corresponde a un problema de estos sistemas en particular, si no más bien, tiene que ver con la especificación. De hecho, se muestra que cualquier implementación que siga la especificación de SPARQL 1.1 (a Noviembre del 2011), está destinada a mantener el mismo comportamiento, siendo el mayor problema, la necesidad de contar soluciones impuesta en la propuesta actual.
En esta tesis se incluyen diversos resultados teóricos que demuestran la imposibilidad de computar consultas de property paths en tiempos razonables, que junto a los resultados empíricos, entregan una evidencia contundente en contra de la actual propuesta de semántica para property paths en SPARQL 1.1. Finalmente, se porpone una sem´antica natural alternativa que resuelve los problemas de desempe\02DCno, permitiendo así la adopción del standar por parte de usuarios, desarrolladores y teóricos.
En búsqueda de una explicación formal a este comportamiento, se ha realizado un estudio de la complejidad computacional de la evaluación de consultas con property paths. Los resultados muestran que el bajo rendimiento de las implementaciones probadas, no corresponde a un problema de estos sistemas en particular, si no más bien, tiene que ver con la especificación. De hecho, se muestra que cualquier implementación que siga la especificación de SPARQL 1.1 (a Noviembre del 2011), está destinada a mantener el mismo comportamiento, siendo el mayor problema, la necesidad de contar soluciones impuesta en la propuesta actual.
En esta tesis se incluyen diversos resultados teóricos que demuestran la imposibilidad de computar consultas de property paths en tiempos razonables, que junto a los resultados empíricos, entregan una evidencia contundente en contra de la actual propuesta de semántica para property paths en SPARQL 1.1. Finalmente, se porpone una sem´antica natural alternativa que resuelve los problemas de desempe\02DCno, permitiendo así la adopción del standar por parte de usuarios, desarrolladores y teóricos.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2012