The expressiveness of SHACL and a tractable language fragment proposal.
Loading...
Date
2020
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2020