Optimizing reformulated RDF queries

Mostrar todas las versiones(2)

El desarrollo de la Web Semántica y la creciente popularidad de su principal formato de datos, RDF, trae aparejada la necesidad de técnicas eficientes y escalables de gestión de datos para responder consultas RDF sobre grandes volúmenes de datos heterogéneos. Una opción popular consiste en la traduc...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Bursztyn, Damián Alexis
Otros Autores:	Ruz, Cecilia Ana
Formato:	Tesis de grado publishedVersion
Lenguaje:	Inglés
Publicado:	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2013
Materias:	PROCESAMIENTO DE CONSULTAS RDF SPARQL REFORMULACION DE CONSULTAS GESTION DE DATOS SEMANTICOS EN LA WEB OPTIMIZACION DE CONSULTAS ALGORITMOS HEURISTICOS RDF QUERY ANSWERING QUERY REFORMULATION SEMANTIC WEB DATA MANAGEMENT QUERY OPTIMIZATION HEURISTIC ALGORITHMS
Acceso en línea:	https://hdl.handle.net/20.500.12110/seminario_nCOM000717_Bursztyn https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesisg&d=seminario_nCOM000717_Bursztyn_oai
Aporte de:	Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires

id	I28-R145-seminario_nCOM000717_Bursztyn_oai
record_format	dspace
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-145
collection	Repositorio Digital de la Universidad de Buenos Aires (UBA)
language	Inglés
orig_language_str_mv	eng
topic	PROCESAMIENTO DE CONSULTAS RDF SPARQL REFORMULACION DE CONSULTAS GESTION DE DATOS SEMANTICOS EN LA WEB OPTIMIZACION DE CONSULTAS ALGORITMOS HEURISTICOS RDF QUERY ANSWERING QUERY REFORMULATION SEMANTIC WEB DATA MANAGEMENT QUERY OPTIMIZATION HEURISTIC ALGORITHMS
spellingShingle	PROCESAMIENTO DE CONSULTAS RDF SPARQL REFORMULACION DE CONSULTAS GESTION DE DATOS SEMANTICOS EN LA WEB OPTIMIZACION DE CONSULTAS ALGORITMOS HEURISTICOS RDF QUERY ANSWERING QUERY REFORMULATION SEMANTIC WEB DATA MANAGEMENT QUERY OPTIMIZATION HEURISTIC ALGORITHMS Bursztyn, Damián Alexis Optimizing reformulated RDF queries
topic_facet	PROCESAMIENTO DE CONSULTAS RDF SPARQL REFORMULACION DE CONSULTAS GESTION DE DATOS SEMANTICOS EN LA WEB OPTIMIZACION DE CONSULTAS ALGORITMOS HEURISTICOS RDF QUERY ANSWERING QUERY REFORMULATION SEMANTIC WEB DATA MANAGEMENT QUERY OPTIMIZATION HEURISTIC ALGORITHMS
description	El desarrollo de la Web Semántica y la creciente popularidad de su principal formato de datos, RDF, trae aparejada la necesidad de técnicas eficientes y escalables de gestión de datos para responder consultas RDF sobre grandes volúmenes de datos heterogéneos. Una opción popular consiste en la traducción de consultas RDF en consultas SQL a ser ejecutadas en los maduros y eficientes sistemas de gestión de bases de datos relacionales tradicionales (RDBMS). Sin embargo, las bases de datos para Web Semántica plantean retos específicos a las tecnologías clásicas de gestión de datos debido a la presencia de datos implícitos, a los cuales los RDBMS no tienen en cuenta durante la evaluación de consultas. Para achicar la brecha entre las bases de datos de Web Semántica que contienen datos impl´ıcitos y la evaluación de consultas proporcionada por los RDBMS actuales, una opción es reformular la consulta entrante para luego traducirla en una consulta SQL que, al ser evaluada por el RDBMS, devuelve las respuestas completas . Si bien este enfoque es conceptualmente suficiente para garantizar el eficaz procesamiento de las consultas de Web Semántica en un RDBMS, en la práctica aparecen problemas significativos de rendimiento debido a la longitud sintáctica de las consultas SQL que resultan de reformulación. Reconocidos y eficientes RDBMSs no son capaces de optimizar eficientemente estas consultas. En algunos casos los RDBMSs simplemente fallan al intentar responder estas consultas, mientras en otros casos se registran tiempos de evaluación muy elevados [1]. En este trabajo, hemos identificado y explotado dos grados de libertad que pueden ser aprovechados para realizar la evaluación de las consultas reformuladas de forma más eficiente. En primer lugar, se enumeran un espectro de consultas alternativas equivalentes, obtenidas mediante el agrupamiento de los átomos de la consulta original y la reformulación de fragmentos (de átomos) de la consulta; las reformulaciones de los fragmentos resultantes son env´ıadas en forma individual al RDBMS para su evaluación, para luego realizar la operación de join entre los resultados intermedios a fines de obtener la respuesta completa a la consulta original. En segundo lugar, SQL proporciona distintas alternativas sintácticas para expresar este tipo de consultas (que consiste en subconsultas cuyos resultados deben ser unidos); detectamos que esta elección sintáctica también permite mejoras en el rendimiento. Diseñamos un modelo de costos que refleja el impacto de las decisiones tomadas dentro de los dos grados de libertad descritos anteriormente. Basado en este modelo de costos, proponemos distintos algoritmos heurísticos que, dada una consulta inicial y las reglas semánticas que aplican en la base de datos (e implican los datos implícitos), realizan las elecciones necesarias en forma automática a fines de producir una consulta SQL cuya evaluación genera la respuesta completa a la consulta de forma eficiente. Por último, presentamos una amplia gama de experimentos basados en un DBMS off-the-shelf, que dan soporte a los beneficios de los algoritmos propuestos.
author2	Ruz, Cecilia Ana
author_facet	Ruz, Cecilia Ana Bursztyn, Damián Alexis
format	Tesis de grado Tesis de grado publishedVersion
author	Bursztyn, Damián Alexis
author_sort	Bursztyn, Damián Alexis
title	Optimizing reformulated RDF queries
title_short	Optimizing reformulated RDF queries
title_full	Optimizing reformulated RDF queries
title_fullStr	Optimizing reformulated RDF queries
title_full_unstemmed	Optimizing reformulated RDF queries
title_sort	optimizing reformulated rdf queries
publisher	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate	2013
url	https://hdl.handle.net/20.500.12110/seminario_nCOM000717_Bursztyn https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesisg&d=seminario_nCOM000717_Bursztyn_oai
work_keys_str_mv	AT bursztyndamianalexis optimizingreformulatedrdfqueries
_version_	1843126989047726080
spelling	I28-R145-seminario_nCOM000717_Bursztyn_oai2025-08-20 Ruz, Cecilia Ana Manolescu, Loana Goasdoué, François Colazzo, Darío Bursztyn, Damián Alexis 2013 El desarrollo de la Web Semántica y la creciente popularidad de su principal formato de datos, RDF, trae aparejada la necesidad de técnicas eficientes y escalables de gestión de datos para responder consultas RDF sobre grandes volúmenes de datos heterogéneos. Una opción popular consiste en la traducción de consultas RDF en consultas SQL a ser ejecutadas en los maduros y eficientes sistemas de gestión de bases de datos relacionales tradicionales (RDBMS). Sin embargo, las bases de datos para Web Semántica plantean retos específicos a las tecnologías clásicas de gestión de datos debido a la presencia de datos implícitos, a los cuales los RDBMS no tienen en cuenta durante la evaluación de consultas. Para achicar la brecha entre las bases de datos de Web Semántica que contienen datos impl´ıcitos y la evaluación de consultas proporcionada por los RDBMS actuales, una opción es reformular la consulta entrante para luego traducirla en una consulta SQL que, al ser evaluada por el RDBMS, devuelve las respuestas completas . Si bien este enfoque es conceptualmente suficiente para garantizar el eficaz procesamiento de las consultas de Web Semántica en un RDBMS, en la práctica aparecen problemas significativos de rendimiento debido a la longitud sintáctica de las consultas SQL que resultan de reformulación. Reconocidos y eficientes RDBMSs no son capaces de optimizar eficientemente estas consultas. En algunos casos los RDBMSs simplemente fallan al intentar responder estas consultas, mientras en otros casos se registran tiempos de evaluación muy elevados [1]. En este trabajo, hemos identificado y explotado dos grados de libertad que pueden ser aprovechados para realizar la evaluación de las consultas reformuladas de forma más eficiente. En primer lugar, se enumeran un espectro de consultas alternativas equivalentes, obtenidas mediante el agrupamiento de los átomos de la consulta original y la reformulación de fragmentos (de átomos) de la consulta; las reformulaciones de los fragmentos resultantes son env´ıadas en forma individual al RDBMS para su evaluación, para luego realizar la operación de join entre los resultados intermedios a fines de obtener la respuesta completa a la consulta original. En segundo lugar, SQL proporciona distintas alternativas sintácticas para expresar este tipo de consultas (que consiste en subconsultas cuyos resultados deben ser unidos); detectamos que esta elección sintáctica también permite mejoras en el rendimiento. Diseñamos un modelo de costos que refleja el impacto de las decisiones tomadas dentro de los dos grados de libertad descritos anteriormente. Basado en este modelo de costos, proponemos distintos algoritmos heurísticos que, dada una consulta inicial y las reglas semánticas que aplican en la base de datos (e implican los datos implícitos), realizan las elecciones necesarias en forma automática a fines de producir una consulta SQL cuya evaluación genera la respuesta completa a la consulta de forma eficiente. Por último, presentamos una amplia gama de experimentos basados en un DBMS off-the-shelf, que dan soporte a los beneficios de los algoritmos propuestos. The development of the Semantic Web and the increasing popularity of its main data format RDF, efficient and scalable data management techniques are needed to handle RDF query answering on large volumes of heterogeneous data. A popular option consists thus of translating RDF queries into SQL queries to be handled by mature and efficient relational database management systems (RDBMSs). However, Semantic Web databases pose specific challenges to classical data management technologies through the presence of implicit data, which RDBMS query evaluation fails to account for. To bridge the gap between the Semantic Web databases containing implicit data and the simple query evaluation provided by RDBMSs, one can reformulate the incoming query into an SQL query which, when evaluated by the RDBMS, returns complete answers. While this approach is conceptually sufficient to ensure efficient processing of Semantic Web queries within RDBMSs, in practice it raises significant performance problems due to the syntactic size of the SQL queries resulting from reformulation. It turns out that many efficient RDBMSs are unable to efficiently optimize such queries. In some cases RDBMS evaluation simply fails, while in other cases very high evaluation times are recorded [1]. In this work, we have identified and exploited two degrees of freedom that could be exploited to make the evaluation of reformulated queries more efficient. First, we enumerate a space of alternative equivalent queries, obtained by grouping atoms from the original query and reformulating query fragments; the resulting reformulated fragments are sent individually for evaluation to the RDBMS before joining their results to obtain the complete query answer. Second, SQL provides alternative syntaxes for expressing such queries (consisting of subqueries whose results must be joined); we found that this syntactic choice leads to performance improvements, too. We have devised a cost model capturing the impact of the choices made within the two freedom degrees described above. Based on this cost model, we propose several heuristic algorithms which, given an initial query and the semantic rules holding on the database (and entailing implicit data), automatically makes the necessary choices in order to produce an SQL query whose evaluation computes the query answers more efficiently. Finally, we present an extensive experimental evaluation based on an off-the-shelf DBMS, which validates the benefits of our proposed algorithms. Fil: Bursztyn, Damián Alexis. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/seminario_nCOM000717_Bursztyn eng Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar PROCESAMIENTO DE CONSULTAS RDF SPARQL REFORMULACION DE CONSULTAS GESTION DE DATOS SEMANTICOS EN LA WEB OPTIMIZACION DE CONSULTAS ALGORITMOS HEURISTICOS RDF QUERY ANSWERING QUERY REFORMULATION SEMANTIC WEB DATA MANAGEMENT QUERY OPTIMIZATION HEURISTIC ALGORITHMS Optimizing reformulated RDF queries Optimizing reformulated rdf queries info:eu-repo/semantics/bachelorThesis info:ar-repo/semantics/tesis de grado info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesisg&d=seminario_nCOM000717_Bursztyn_oai

Optimizing reformulated RDF queries

Ejemplares similares