Semantics and validation of recursive SHACL

Simple item page
dc.catalogadorgjm
dc.contributor.authorCorman, Julien
dc.contributor.authorReutter de la Maza, Juan
dc.contributor.authorSavković, Ognjen
dc.date.accessioned2024-05-23T17:13:43Z
dc.date.available2024-05-23T17:13:43Z
dc.date.issued2018
dc.description.abstractWith the popularity of RDF as an independent data model came the need for specifying constraints on RDF graphs, and for mechanisms to detect violations of such constraints. One of the most promising schema languages for RDF is SHACL, a recent W3C recommendation. Unfortunately, the specification of SHACL leaves open the problem of validation against recursive constraints. This omission is important because SHACL by design favors constraints that reference other ones, which in practice may easily yield reference cycles. In this paper, we propose a concise formal semantics for the so-called “core constraint components” of SHACL. This semantics handles arbitrary recursion, while being compliant with the current standard. Graph validation is based on the existence of an assignment of SHACL “shapes” to nodes in the graph under validation, stating which shapes are verified or violated, while verifying the targets of the validation process. We show in particular that the design of SHACL forces us to consider cases in which these assignments are partial, or, in other words, where the truth value of a constraint at some nodes of a graph may be left unknown. Dealing with recursion also comes at a price, as validating an RDF graph against SHACL constraints is NP-hard in the size of the graph, and this lower bound still holds for constraints with stratified negation. Therefore we also propose a tractable approximation to the validation problem.
dc.fuente.origenORCID
dc.identifier.doi10.1007/978-3-030-00671-6_19
dc.identifier.eisbn978-3030006709
dc.identifier.urihttps://doi.org/10.1007/978-3-030-00671-6_19
dc.identifier.urihttp://www.scopus.com/inward/record.url?eid=2-s2.0-85054790834&partnerID=MN8TOARS
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/85762
dc.information.autorucEscuela de Ingeniería; Reutter de la Maza, Juan; 0000-0002-2186-0312; 126898
dc.language.isoen
dc.nota.accesocontenido parcial
dc.pagina.final336
dc.pagina.inicio318
dc.publisherSpringer Verlag
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.rightsacceso restringido
dc.subjectFormal Semantics
dc.subjectLower bounds
dc.subjectRecursive constraints
dc.subjectSchema language
dc.subjectStratified negation
dc.subjectTruth values
dc.subjectValidation problem
dc.subjectValidation process
dc.subject.ddc600
dc.subject.deweyTecnologíaes_ES
dc.titleSemantics and validation of recursive SHACL
dc.typecomunicación de congreso
dc.volumen11136
sipa.codpersvinculados126898
sipa.trazabilidadORCID;2024-05-20
Files
Collections
Artículos de conferencia