@prefix foaf: . @prefix ns1: . @prefix ns2: . ns1:juan-l-reutter foaf:made ns2:iswc-2018-poster_and_demo-384 . ns1:ognjen-savkovic foaf:made ns2:iswc-2018-poster_and_demo-384 . @prefix ns3: . @prefix ns4: . ns4:proceedings ns3:hasPart ns2:iswc-2018-poster_and_demo-384 . @prefix rdf: . ns2:iswc-2018-poster_and_demo-384 rdf:type ns3:InProceedings . @prefix rdfs: . ns2:iswc-2018-poster_and_demo-384 rdfs:label "Tractable Notion of Stratification for SHACL" . @prefix dc: . ns2:iswc-2018-poster_and_demo-384 dc:creator ns1:juan-l-reutter , ns1:ognjen-savkovic , ns1:julien-corman ; ns3:abstract "One of the most promising schema languages for RDF is SHACL, a recent W3C recommendation.\nHowever, the original semantics of SHACL is undefined in the presence of recursive constraints.\nThis omission is important because SHACL by design favors constraints that reference other ones, which in practice may easily yield reference cycles.\nWe showed that extending the existing semantics to accommodate the recursion leads to intractability in the size of the graph for the so-called \"core constraint components\" of SHACL.\nIn fact, we show intractability already for stratified constraints, which may come as a surprise, considering that stratification guarantees tractability in well studied languages such as Datalog. \nIn our previous work we propose a syntactic fragment of SHACL that guarantees tractability. \nIn this paper instead we retain all SHACL operators, and strengthen the stratification condition.\nIn particular, we introduce a syntactic condition of shape constraints called \"strict stratification\", that guarantees that graph validation is in PTIME.\nWe also introduce an algorithm which runs in PTIME and decides graph validation over a set of shapes satisfying this requirement." . @prefix ns8: . ns2:iswc-2018-poster_and_demo-384 ns3:hasAuthorList ns8:iswc-2018-poster_and_demo-384 ; ns3:isPartOf ns4:proceedings . @prefix xsd: . ns2:iswc-2018-poster_and_demo-384 ns3:keyword "computational complexity"^^xsd:string , "formal semantics"^^xsd:string , "SHACL"^^xsd:string , "graph constraint language"^^xsd:string ; ns3:title "Tractable Notion of Stratification for SHACL" . ns1:julien-corman foaf:made ns2:iswc-2018-poster_and_demo-384 . @prefix ns10: . ns10:iswc2018-author-juan-l-reutter-iswc-2018-poster_and_demo-384 ns3:withDocument ns2:iswc-2018-poster_and_demo-384 . ns10:iswc2018-author-julien-corman-iswc-2018-poster_and_demo-384 ns3:withDocument ns2:iswc-2018-poster_and_demo-384 . ns10:iswc2018-author-ognjen-savkovic-iswc-2018-poster_and_demo-384 ns3:withDocument ns2:iswc-2018-poster_and_demo-384 .