Extending SPARQL engines with multiway joins
Loading...
Date
2019
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
En los últimos años han surgido nuevos algoritmos de join, los cuales no evalúan la operación como un operador binario como ha sido usual, sino que como un gran operador de join que reúne una cantidad arbitraria de relaciones a la vez. Estos algoritmos ofrecen garantías teóricas de eficiencia y se ha demostrado que para el peor caso, su complejidad asintótica es óptima. Más aún, se ha mostrado empíricamente que mejoran significativamente los tiempos de ejecución de consultas para bases de datos relacionales y de grafos. A pesar de estos prometedores resultados teóricos y prácticos, la comunidad de la Web Semántica aún no ha adoptado tales técnicas. De hecho, ninguna base de datos RDF nativa soporta actualmente tales algoritmos de join. El objetivo de este trabajo es mostrar cómo modificar un motor RDF existente para incorporar uno de estos algoritmos y estudiar su rendimiento en consultas intensivas en joins. Específicamente, en este trabajo se propone un nuevo procedimiento para evaluar consultas SPARQL basadas en un algoritmo de multiway join óptimo para el peor caso llamado Leapfrog Triejoin. Para esto modificamos el motor RDF Apache Jena para que resuelva las consultas usando este nuevo método. Luego presentamos resultados de dos benchmarks SPARQL conocidos: Berlín y WatDiv. Además proponemos un nuevo benchmark basado en Wikidata que busca proporcionar información sobre el rendimiento del join sobre un conjunto de patrones de consulta intensivo en joins y diverso. Nuestros resultados muestran que Apache Jena con este nuevo algoritmo ejecuta consultas intensivas en join más rápido que la versión base y otros dos motores SPARQL (Virtuoso y Blazegraph), llegando en algunos casos a ser órdenes de magnitud más rápido.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2019
Keywords
Web semantica, RDF, Multiway join, Leapfrog triejoin, Optimalidad asintótica, Apache Jena