Efficient processing of recursive and federated queries in SPARQL
Loading...
Date
2021
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Han pasado décadas desde los primeros pasos de la Web Semántica, y si bien, los avances han sido considerables, aún hay espacio para mejorar. En esta tesis discutimos una forma de extender SPARQL con funcionalidades recursivas, con el fin de extender el poder expresivo del lenguaje, pero también abarcar casos de uso que aún no están cubiertos. Además proponemos nuevos algoritmos que nos permiten evaluar las
funcionalidades recursivas y las consultas generales de SPARQL de forma más eficiente, tanto en entornos locales como distribuidos en la web.
Este trabajo se abre con la presentación de SPARQL Recursivo, una extensión al lenguaje basado en uno perador de punto fijo. Luego definimos un fragmento de este lenguaje, que es menos expresivo pero puede ser evaluado de forma más eficiente. Después mostramos cómo la idea de lenguajes recursivos puede ser utilizada para computar procedimientos de analítica de grafos con SPARQL, estudiando qué otros operadores necesita el lenguaje para llevar acabo esta tarea. Así, proponemos el lenguaje
SPARQAL, para hacer analítica de grafos dentro de bases de datos RDF.
Sin embargo, el desarrollo de estas extensiones produce una sobrecarga del motor
de consultas, por la cantidad de Basic Graph Patterns que hay que resolver. Por esta
razón es que buscamos técnicas para proponer nuevos algoritmos de evaluación para
este fragmento de SPARQL. Nuestras técnicas están basadas en los algoritmos de join
Worst-case optimal, una nueva familia de algoritmos con buenas propiedades teóricas.
De esta forma diseñamos e implementamos un algoritmo basado en el LeapfrogTriejoin que, según lo que muestran nuestros experimentos, resuelve los patrones de grafos de
forma mucho más eficiente. Luego de esto, buscamos entender cómo estas técnicas de
join pueden ser extendidas para entornos Web distribuidos y cómo nos pueden ayudar
a integrar datos que actualmente no son accesibles para la Web Semántica.
Description
Tesis (Doctor in Engineering Sciences)--Pontificia Universidad Católica de Chile, 2021