Extending SPARQL engines with multiway joins

Extending SPARQL engines with multiway joins

Web semantica

RDF

Multiway join

Leapfrog triejoin

Optimalidad asintótica

Apache Jena

620

Ingeniería

Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2019

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.

Rojas Victoriano, Carlos

2022-10-27T21:16:14Z

2022-10-27T21:16:14Z

2019

Riveros Jaeger, Cristian

Pontificia Universidad Católica de Chile. Escuela de Ingeniería

acceso abierto

xi, 58 páginas

application/pdf

en

tesis de maestría

10.7764/tesisUC/ING/65156

https://doi.org/10.7764/tesisUC/ING/65156

https://repositorio.uc.cl/handle/11534/65156