Dublin Core
Title
The expressiveness of SHACL and a tractable language fragment proposal.
Subject
005.758
Ciencias de la computación
RDF (Lenguaje de marcación de documentos)
Lenguajes de marcación de documentos
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2020
SHACL (Shapes Constraint Language) es una especificación para describir y validar
grafos RDF que recientemente se convirtió en recomendación de la W3C. La dificultad
principal que presenta su uso es la ausencia de una definición oficial para el manejo de restricciones
recursivas. Además, el hecho de que grafos RDF por lo general son accesibles
mediante alojamiento remoto a través de solo consultas SPARQL hace que la validación
dependa de dichos sistemas. En esta tesis, extendemos trabajo previo con el objetivo de
mejorar el entendimiento de lo conocido del problema de validación. Primero, investigamos
la posibilidad de validar un grafo contra esquemas no recursivos utilizando solo
procesamiento en memoria, y mediante el procesamiento de una única consulta general.
Para el caso recursivo, cuyo problema es NP-duro, revisamos la jerarquía de fragmentos
de SHACL conocidos y sus respectivas dificultades. Finalmente, proponemos un nuevo
fragmento de restricciones y mostramos un algoritmo que resuelve eficientemente el problema
de validación. Este último se puede utilizar cuando es necesario manejar restricciones
recursivas, pero manteniendo cotas de ejecución eficientes sin tener que recurrir a
maquinaria externa.
grafos RDF que recientemente se convirtió en recomendación de la W3C. La dificultad
principal que presenta su uso es la ausencia de una definición oficial para el manejo de restricciones
recursivas. Además, el hecho de que grafos RDF por lo general son accesibles
mediante alojamiento remoto a través de solo consultas SPARQL hace que la validación
dependa de dichos sistemas. En esta tesis, extendemos trabajo previo con el objetivo de
mejorar el entendimiento de lo conocido del problema de validación. Primero, investigamos
la posibilidad de validar un grafo contra esquemas no recursivos utilizando solo
procesamiento en memoria, y mediante el procesamiento de una única consulta general.
Para el caso recursivo, cuyo problema es NP-duro, revisamos la jerarquía de fragmentos
de SHACL conocidos y sus respectivas dificultades. Finalmente, proponemos un nuevo
fragmento de restricciones y mostramos un algoritmo que resuelve eficientemente el problema
de validación. Este último se puede utilizar cuando es necesario manejar restricciones
recursivas, pero manteniendo cotas de ejecución eficientes sin tener que recurrir a
maquinaria externa.
Creator
Florenzano Hernández, Fernando Alberto
Date
2020-05-18T15:28:10Z
2020-05-18T15:28:10Z
2020
Contributor
Reutter de la Maza, Juan
Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Rights
acceso abierto
Format
ix, 81 páginas
application/pdf
Language
en
Type
tesis de maestría
Identifier
10.7764/tesisUC/ING/28920
https://doi.org/10.7764/tesisUC/ING/28920
https://repositorio.uc.cl/handle/11534/28920