Heterogeneous data is typically integrated into a knowledge graph using declarative mappings. There are two ways of constructing the graph with the mappings: materialization and virtualization. Historically, virtualization has focused on relational databases due to their predominance and because of the possibility of pushing down costly computations in SQL. However, the current prevalence of diverse data has rendered existing virtualization techniques insufficient. This diversity is not a problem in materialization, but it must be optimized to create large graph dumps.
The first research problem addressed in this thesis is the optimization of materialization. We propose mapping partitioning, which divides rules into groups with non-overlapping outputs. Two strategies are introduced to optimize materialization: parallel processing of the mapping groups reduces execution times, and sequential processing reduces the consumption of memory. We devise algorithms for partitioning a mapping and validate their effectiveness on several benchmarks and use cases. We empirically compare materialization with mapping partitioning against a baseline without partitioning and state-of-the-art systems. The results demonstrate the positive impact of partitioning on materialization with a large reduction in execution times and memory usage.
Building on optimized materialization, we address our second research problem: generic virtualization over multiple and diverse sources. We propose shifting from the established query translation approach to a data translation approach. The idea is to converge on the fly the relevant subset of data for a SPARQL query into an intermediate representation. Coalescing heterogeneous data into this representation is easier than translating queries into the potentially diverse query languages of the local sources. We present the ITT architecture, based on star-shaped mapping candidate selection to find the relevant set of rules, rapid materialization of intermediate results into a triple table, and unfolding SPARQL queries to SQL over the triple table. Experiments with mixed data sources demonstrate the generic nature of ITT. Compared to query translation with Ontop, the experimental results showed that ITT outperformed query translation in many cases. While ITT exhibited a more intensive use of memory, it did not experience timeouts, unlike Ontop.
The thesis also addresses other challenges in KG construction arising from the emergence of the RDF-star graph model and the need for flexible data transformations. For RDF-star, we devise the RML-star mapping language, a baseline materialization algorithm, and a method for the automatic extraction of RML-star from property graphs to mitigate labor-intensive mapping development. Regarding flexible data transformations, we extend RML views to tabular files to leverage SQL, overcoming RML’s limitations with complex joins and composite data values. We also propose unfolding data transformations defined in RML-FNML to RML views, enabling query translation-based virtualization systems to process RML-FNML with prior unfolding of the mappings. Finally, we implemented Python user-defined functions in RML to allow more flexible data transformations using a high-level programming language; their positive impact on knowledge graph construction has been demonstrated at an industry scale in the chemical sector.
RESUMEN
La integración de datos heterogéneos en un grafo de conocimiento se realiza comúnmente mediante reglas de mapeo declarativas. Existen dos formas de construir el grafo con estas reglas: materialización y virtualización. Históricamente, la virtualización se ha centrado en las bases de datos relacionales debido a su predominancia y a la posibilidad de delegar tareas computacionalmente intensivas mediante SQL. No obstante, las técnicas de virtualización existentes son insuficientes para manejar la diversidad de los datos en el contexto actual. Esta diversidad no supone un problema para la materialización, pero este proceso debe optimizarse para generar grafos de gran tamaño de manera eficiente.
El primer problema de investigación abordado en esta tesis es la optimización de la materialización. Para ello, proponemos el particionamiento de las reglas de mapeo, dividiéndolas en grupos que generan subgrafos sin solapamiento. Presentamos dos estrategias para optimizar la materialización: la paralelización de los grupos de mapeo, que reduce los tiempos de ejecución, y el procesamiento secuencial, que disminuye el consumo de memoria. Proponemos algoritmos para particionar las reglas y validamos su efectividad en varios benchmarks y casos de uso. Comparamos empíricamente la materialización con particionamiento frente a una referencia sin particionamiento y otros sistemas. Los resultados demuestran que nuestra propuesta disminuye de forma significativa los tiempos de ejecución y el uso de memoria.
Basándonos en lo anterior, abordamos un segundo problema de investigación: la virtualización genérica sobre múltiples fuentes de datos diversas. Para ello, proponemos cambiar el enfoque clásico de traducción de consultas a uno de traducción de datos. La idea es fusionar al vuelo el subconjunto relevante de datos para una consulta SPARQL en una representación intermedia. Traducir datos heterogéneos a esta representación es más sencillo que traducir consultas a los lenguajes potencialmente diversos de las fuentes locales. De esta manera, introducimos la arquitectura ITT, que se basa en la selección de reglas de mapeo con forma de estrella, la materialización eficiente de resultados intermedios en una tabla de tripletas empleando particionamiento de las reglas, y la traducción de consultas SPARQL a SQL sobre la tabla de tripletas. Los experimentos con fuentes de datos mixtas demuestran el carácter genérico de ITT. En comparación con la traducción de consultas con Ontop, los experimentos arrojan un mejor rendimiento de ITT en muchos casos. Aunque ITT hace un uso intensivo de la memoria, a diferencia de Ontop no supera los límites de tiempo establecidos en ningún caso.
La tesis también aborda otros retos en la construcción de grafos de conocimiento. El primero es la generación de RDF-star, para lo que proponemos el lenguaje de mapeo RML-star, un algoritmo de materialización y un método para la extracción automática de RML-star a partir de un grafo de propiedades, con el fin de mitigar el desarrollo laborioso de los mapeos. En cuanto a desafíos en la transformación de los datos, extendemos las vistas de RML para procesar ficheros tabulares, utilizando SQL para superar limitaciones de RML respecto a joins complejos. Además, proponemos la traducción de las transformaciones de datos definidas en RML-FNML a vistas de RML, permitiendo que los sistemas de virtualización basados en la traducción de consultas soporten RML-FNML mediante un preprocesamiento previo. Finalmente, implementamos funciones definidas por el usuario en Python para permitir transformaciones de datos más flexibles utilizando un lenguaje de programación de alto nivel.
Heterogeneous data is typically integrated into a knowledge graph using declarative mappings. There are two ways of constructing the graph with the mappings: materialization and virtualization. Historically, virtualization has focused on relational databases due to their predominance and because of the possibility of pushing down costly computations in SQL. However, the current prevalence of diverse data has rendered existing virtualization techniques insufficient. This diversity is not a problem in materialization, but it must be optimized to create large graph dumps.
The first research problem addressed in this thesis is the optimization of materialization. We propose mapping partitioning, which divides rules into groups with non-overlapping outputs. Two strategies are introduced to optimize materialization: parallel processing of the mapping groups reduces execution times, and sequential processing reduces the consumption of memory. We devise algorithms for partitioning a mapping and validate their effectiveness on several benchmarks and use cases. We empirically compare materialization with mapping partitioning against a baseline without partitioning and state-of-the-art systems. The results demonstrate the positive impact of partitioning on materialization with a large reduction in execution times and memory usage.
Building on optimized materialization, we address our second research problem: generic virtualization over multiple and diverse sources. We propose shifting from the established query translation approach to a data translation approach. The idea is to converge on the fly the relevant subset of data for a SPARQL query into an intermediate representation. Coalescing heterogeneous data into this representation is easier than translating queries into the potentially diverse query languages of the local sources. We present the ITT architecture, based on star-shaped mapping candidate selection to find the relevant set of rules, rapid materialization of intermediate results into a triple table, and unfolding SPARQL queries to SQL over the triple table. Experiments with mixed data sources demonstrate the generic nature of ITT. Compared to query translation with Ontop, the experimental results showed that ITT outperformed query translation in many cases. While ITT exhibited a more intensive use of memory, it did not experience timeouts, unlike Ontop.
The thesis also addresses other challenges in KG construction arising from the emergence of the RDF-star graph model and the need for flexible data transformations. For RDF-star, we devise the RML-star mapping language, a baseline materialization algorithm, and a method for the automatic extraction of RML-star from property graphs to mitigate labor-intensive mapping development. Regarding flexible data transformations, we extend RML views to tabular files to leverage SQL, overcoming RML’s limitations with complex joins and composite data values. We also propose unfolding data transformations defined in RML-FNML to RML views, enabling query translation-based virtualization systems to process RML-FNML with prior unfolding of the mappings. Finally, we implemented Python user-defined functions in RML to allow more flexible data transformations using a high-level programming language; their positive impact on knowledge graph construction has been demonstrated at an industry scale in the chemical sector.
RESUMEN
La integración de datos heterogéneos en un grafo de conocimiento se realiza comúnmente mediante reglas de mapeo declarativas. Existen dos formas de construir el grafo con estas reglas: materialización y virtualización. Históricamente, la virtualización se ha centrado en las bases de datos relacionales debido a su predominancia y a la posibilidad de delegar tareas computacionalmente intensivas mediante SQL. No obstante, las técnicas de virtualización existentes son insuficientes para manejar la diversidad de los datos en el contexto actual. Esta diversidad no supone un problema para la materialización, pero este proceso debe optimizarse para generar grafos de gran tamaño de manera eficiente.
El primer problema de investigación abordado en esta tesis es la optimización de la materialización. Para ello, proponemos el particionamiento de las reglas de mapeo, dividiéndolas en grupos que generan subgrafos sin solapamiento. Presentamos dos estrategias para optimizar la materialización: la paralelización de los grupos de mapeo, que reduce los tiempos de ejecución, y el procesamiento secuencial, que disminuye el consumo de memoria. Proponemos algoritmos para particionar las reglas y validamos su efectividad en varios benchmarks y casos de uso. Comparamos empíricamente la materialización con particionamiento frente a una referencia sin particionamiento y otros sistemas. Los resultados demuestran que nuestra propuesta disminuye de forma significativa los tiempos de ejecución y el uso de memoria.
Basándonos en lo anterior, abordamos un segundo problema de investigación: la virtualización genérica sobre múltiples fuentes de datos diversas. Para ello, proponemos cambiar el enfoque clásico de traducción de consultas a uno de traducción de datos. La idea es fusionar al vuelo el subconjunto relevante de datos para una consulta SPARQL en una representación intermedia. Traducir datos heterogéneos a esta representación es más sencillo que traducir consultas a los lenguajes potencialmente diversos de las fuentes locales. De esta manera, introducimos la arquitectura ITT, que se basa en la selección de reglas de mapeo con forma de estrella, la materialización eficiente de resultados intermedios en una tabla de tripletas empleando particionamiento de las reglas, y la traducción de consultas SPARQL a SQL sobre la tabla de tripletas. Los experimentos con fuentes de datos mixtas demuestran el carácter genérico de ITT. En comparación con la traducción de consultas con Ontop, los experimentos arrojan un mejor rendimiento de ITT en muchos casos. Aunque ITT hace un uso intensivo de la memoria, a diferencia de Ontop no supera los límites de tiempo establecidos en ningún caso.
La tesis también aborda otros retos en la construcción de grafos de conocimiento. El primero es la generación de RDF-star, para lo que proponemos el lenguaje de mapeo RML-star, un algoritmo de materialización y un método para la extracción automática de RML-star a partir de un grafo de propiedades, con el fin de mitigar el desarrollo laborioso de los mapeos. En cuanto a desafíos en la transformación de los datos, extendemos las vistas de RML para procesar ficheros tabulares, utilizando SQL para superar limitaciones de RML respecto a joins complejos. Además, proponemos la traducción de las transformaciones de datos definidas en RML-FNML a vistas de RML, permitiendo que los sistemas de virtualización basados en la traducción de consultas soporten RML-FNML mediante un preprocesamiento previo. Finalmente, implementamos funciones definidas por el usuario en Python para permitir transformaciones de datos más flexibles utilizando un lenguaje de programación de alto nivel. Read More
Related posts:
Intermediate triple table: A general architecture for virtual knowledge graphs
Declarative generation of RDF-star graphs from heterogeneous data
Interview: Manish Jethwa, chief technology officer, Ordnance Survey
What is network mapping?
What is data lineage? Techniques, best practices and tools
An ontological approach for representing declarative mapping languages