Extending SPARQL engines with multiway joins
| dc.contributor.advisor | Riveros Jaeger, Cristian | |
| dc.contributor.author | Rojas Victoriano, Carlos | |
| dc.contributor.other | Pontificia Universidad Católica de Chile. Escuela de Ingeniería | |
| dc.date.accessioned | 2022-10-27T21:16:14Z | |
| dc.date.available | 2022-10-27T21:16:14Z | |
| dc.date.issued | 2019 | |
| dc.description | Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2019 | |
| dc.description.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. | |
| dc.format.extent | xi, 58 páginas | |
| dc.fuente.origen | SRIA | |
| dc.identifier.doi | 10.7764/tesisUC/ING/65156 | |
| dc.identifier.uri | https://doi.org/10.7764/tesisUC/ING/65156 | |
| dc.identifier.uri | https://repositorio.uc.cl/handle/11534/65156 | |
| dc.information.autoruc | Escuela de ingeniería ; Riveros Jaeger, Cristian ; S/I ; 131276 | |
| dc.information.autoruc | Escuela de ingeniería ; Rojas Victoriano, Carlos ; S/I ; 213706 | |
| dc.language.iso | en | |
| dc.nota.acceso | Contenido completo | |
| dc.rights | acceso abierto | |
| dc.subject | Web semantica | es_ES |
| dc.subject | RDF | es_ES |
| dc.subject | Multiway join | es_ES |
| dc.subject | Leapfrog triejoin | es_ES |
| dc.subject | Optimalidad asintótica | es_ES |
| dc.subject | Apache Jena | es_ES |
| dc.subject.ddc | 620 | |
| dc.subject.dewey | Ingeniería | es_ES |
| dc.title | Extending SPARQL engines with multiway joins | es_ES |
| dc.type | tesis de maestría | |
| sipa.codpersvinculados | 131276 | |
| sipa.codpersvinculados | 213706 |