Shape Trees Specification

Editor’s Draft,

This version:
https://shapetrees.org/TR/specification/
Issue Tracking:
GitHub
Inline In Spec
Editors:
Eric Prud'hommeaux
Justin Bingham

Abstract

Semantic Web Applications interoperate by sharing semantics of terms and constellations of resource-oriented data structures. This specification defines shape trees, a mechanism for declaring and operating over constellations of resource-oriented data structures.

Status of this document

1. Introduction

This section is non-normative.

Realizing the value proposition of the Semantic Web lies in building useful and robust applications that can interoperate over linked data. Protocols such as [LDP] and [Solid] organize linked data graphs into resource hierarchies, providing a foundation upon which these robust and interoperable applications can be created.

Application interoperability depends on applications sharing semantics for relationships and data structures. Existing technologies fulfill portions of those dependencies:

For applications that operate on more complex and interconnected resources, Shape Trees express the layout of those resources and associate them with their respective shapes.

Shape trees marry [RDF] vocabularies, shapes, and resources into "little trees" that provide machine to machine interoperability, combining them into concepts that humans can easily comprehend, such as medical records, notes, notebooks, calendars, and financial records.

This allows one to treat a set of related resources as a single grouping, and apply that to a range of operations including access control, data organization, data validation, and data migration.

While shape trees are intended to adapt to different technology platforms that support the notion of containers and resources, examples in this specification will reflect usage in an [LDP] environment.

Shape trees are defined as an RDF graph structure that expresses a set of expected behaviors by agents that work with them. This provides a sort of type-safety of resource hierarchies called shape tree consistency. These semantics CAN be implemented by a server-side agent, or by a client-side agent that implements shape tree operations as primitive requests to a server.

Shape tree support by a server-side agent ensures shape tree consistency by managing all manipulations of data within a resource hierarchy (see managed resource).

1.1. ShapeTree Support From Proxy or Client-side Library

If a server does not support shape trees, some shape tree consistency can be achieved by implementing shape tree support in the client, typically in a library than can enforce consistency for any clients using the library. Primitive operations by other clients not using the library may leave the resource hierarchy in an inconsistent state.

For client-side shape tree libraries that operate by intercepting HTTP operations, this specification serves as an API for those client interactions. (Additionally, if shape tree support is later added to the server, the client’s execution of shape tree operations does not change.) In the remainder of this document, shape tree operations are described in terms of a client-side agent performing operations on a server-side agent with support for shape trees.

A proxy performing shape tree operations would be indistinguishable from server support except that clients performing primitive operations directly on the server (bypassing the proxy) may leave the server in an inconsistent state.

2. Shape Tree

A shape tree is a machine-readable template describing the expected layout of a tree of resources in a container-based ecosystem. A shape tree expresses a tree hierarchy by containing other shape trees. The terms used to express a shape tree are described using an [RDF] vocabulary.

A shape tree instance is a resource or set of resources assigned to and in conformance with a given shape tree. A resource in a shape tree instance is called a managed resource.

Every managed resource has an associated shape tree locator. A shape tree locator identifies the shape tree associated with a managed resource, and additional information needed to navigate nested hierarchies of managed resources. A resource becomes a managed resource when a shape tree locator is associated with it through the § 4.2 Plant Shape Tree operation.

The st:expectsType property specifies that the described managed resource be one of these three types:

st:Resource Regular RDF resource that is not a container
st:Container RDF resource that uses server-managed metadata to enumerate nested resources
st:NonRDFResource Non-RDF resource such as binaries or images

The st:shape property specifies that the described managed resource conforms to the stated [ShEx] or [SHACL] shape.

Shape trees prescribe physical hierarchies and can reference other shape trees to form virtual hierarchies.

For physical hierarchies, the st:contains property asserts that a managed resource is a container that explicitly contains another managed resource.

If shape tree S1 st:contains shape tree S2, S1 describes a container that contains another managed resource described by S2. For example, in [LDP], S1 describes an [LDP] container which ldp:contains nested resources described by S2. Shape tree S2 and the nested resources associated with it are considered to be in-scope of the containing shape tree S1.

The st:alsoAllow property in a containing shape tree identifies unmanaged resource types permitted beyond those in-scope:

st:AllowOnly Don’t allow anything else when no shape trees are found in-scope
st:AllowAll Allow all types of unexpected content when no shape trees are found in-scope
st:AllowResources Allow if the requested content is a st:Resource when no shape trees are found in-scope
st:AllowContainers Allow if the proposed content is a st:Container when no matching shape trees are found in-scope
st:AllowNonRDFResources Allow if the proposed content is a st:NonRDFResource when no shape trees are found in-scope
Shape tree validation of a physical hierarchy
Managed Resource Associated Shape Tree
/project-1/ ex:ProjectTree
-- /milestone-A/ ex:MilestoneTree
---- /task-43/ ex:TaskTree
---- /task-48/ ex:TaskTree
------ /attachment-aa89 ex:AttachmentTree
---- /task-61/ ex:TaskTree
---- /issue-22/ ex:IssueTree
------ /attachment-cd12 ex:AttachmentTree
------ /attachment-ef55 ex:AttachmentTree
---- /issue-31/ ex:IssueTree
PREFIX st: <http://www.w3.org/ns/shapetrees#>
PREFIX ex: <http://www.example.com/ns/ex#>

<#ProjectTree>
  a st:ShapeTree ;
  st:expectsType st:Container ;
  st:shape ex:ProjectShape ;
  st:contains <#MilestoneTree> ,
              st:AllowOnly .

<#MilestoneTree>
  a st:ShapeTree ;
  st:expectsType st:Container ;
  st:shape ex:MilestoneShape ;
  st:contains <#TaskTree>, <#IssueTree> ; 
  st:AllowOnly .

<#TaskTree>
  a st:ShapeTree ;
  st:expectsType st:Container ;
  st:shape ex:TaskShape ;
  st:contains <#AttachmentTree> ,
  st:AllowOnly .

<#IssueTree>
  a st:ShapeTree ;
  st:expectsType st:Container ;
  st:shape ex:IssueShape ;
  st:contains <#AttachmentTree> ,
  st:AllowOnly .

<#AttachmentTree>
  a st:ShapeTree ;
  st:expectsType st:NonRDFResource .

A virtual hierarchy is defined by shape tree references that link to other shape trees by the st:references property. A shape tree reference identifies the shape tree to be referenced via st:hasShapeTree, and the shape path through which it is linked via st:viaShapePath.

A shape path is a string that defines a traversal of a shape schema. [SHEXPATH]

Shape tree validation of a virtual hierarchy
Managed Resource Associated Shape Tree
/project-1 ex:VirtualProjectTree
/milestone-A ex:VirtualMilestoneTree
/task-43 ex:VirtualTaskTree
/task-48 ex:VirtualTaskTree
/attachment-aa89 ex:VirtualAttachmentTree
/task-61 ex:VirtualTaskTree
/issue-22 ex:VirtualIssueTree
/attachment-cd12 ex:VirtualAttachmentTree
/attachment-ef55 ex:VirtualAttachmentTree
/issue-31 ex:VirtualIssueTree
PREFIX st: <http://www.w3.org/ns/shapetrees#>
PREFIX ex: <http://www.example.com/ns/ex#>

<#VirtualProjectTree>
  a st:ShapeTree ;
  st:expectsType st:Resource ;
  st:shape ex:ProjectShape ;
  st:references [
    st:hasShapeTree <#VirtualMilestoneTree> ;
    st:viaShapePath "@ex:ProjectShape.ex:hasMilestone"
  ] .

<#VirtualMilestoneTree>
  a st:ShapeTree ;
  st:expectsType st:Resource ;
  st:shape ex:MilestoneShape ;
  st:references [
    st:hasShapeTree <#VirtualTaskTree> ;
    st:viaShapePath "@ex:MilestoneShape.ex:hasTask"
  ] ,
  [
    st:hasShapeTree <#VirtualIssueTree> ;
    st:viaShapePath "@ex:IssueShape.ex:hasIssue"
  ] .

<#VirtualTaskTree>
  a st:ShapeTree ;
  st:expectsType st:Resource ;
  st:shape ex:TaskShape ;
  st:references [
    st:hasShapeTree <#VirtualAttachmentTree> ;
    st:viaShapePath "@ex:AttachmentShape.ex:hasAttachment"
  ] .

<#VirtualIssueTree>
  a st:ShapeTree ;
  st:expectsType st:Container ;
  st:shape ex:IssueShape ;
  st:references [
    st:hasShapeTree <#VirtualAttachmentTree> ;
    st:viaShapePath "@ex:AttachmentShape.ex:hasAttachment"
  ] .

<#VirtualAttachmentTree>
  a st:ShapeTree ;
  st:expectsType st:NonRDFResource .

Let ST be a shape tree. Let STI be a corresponding shape tree instance.

Do we want a notion for static resources? Related Issue

A { ST st:hasShapeTreeDecoratorIndex DI } triple indicates the location of an index of SKOS hierarchies that describes ST.

2.1. Shape Tree Schema

ShEx Schema for a Shape Tree
PREFIX st: <http://www.w3.org/ns/shapetrees#>
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX xsd: <http://www.w3.org/2001/XMLSchema#>

<#ShapeTree> {
  a st:ShapeTree ;
  (
    st:expectsType [st:Container] ;
    st:contains @<#ShapeTree> + ;
    ( st:alsoAllow st:AllowAll? |
    st:alsoAllow [ st:AllowResources st:AllowContainers st:AllowNonRDFSources st:AllowOnly ]* )
    |
    st:expectsType [st:Resource st:NonRDFResource]
  ) ;
  rdfs:label xsd:string ? ;
  st:references @<#ReferencedShapeTree> * ;
  st:shape IRI ? ;
  st:contains IRI ? ;
  st:supports IRI ? ;
}

<#ReferencedShapeTree> {
  st:hasShapeTree IRI ;
  st:viaShapePath xsd:string
}

3. Shape Tree Locator

A shape tree locator associates a managed resource with one or more shape trees. No more than one shape tree locator may be associated with a managed resource.

For example, in [Solid] a shape tree locator would be stored in an auxiliary resource associated with a given managed resource.

A shape tree locator includes one or more shape tree locations via st:location. Each shape tree location identifies a shape tree associated with the managed resource, the focus node for shape validation, and the information needed to navigate the physical hierarchy in which that managed resource resides.

If there is more than one shape tree location, they all apply to the managed resource associated with the shape tree locator.

Shape tree locations identify key contextual points in a physical hierarchy:

Shape Tree Location properties
Property Description
st:hasShapeTree Identifies the shape tree to be associated with the managed resource
st:node Identifies the focus node for shape validation in the associated managed resource, and is only valid when the corresponding shape tree includes st:shape
st:shape Identifies the shape to which st:node must conform
st:hasRootShapeTree Identifies the root shape tree
st:hasRootShapeTreeInstance Identifies the root shape tree instance

A root shape tree, and its corresponding root shape tree instance can be planted within an existing managed hierarchy, alongside or within other root shape trees and root shape tree instances.

Shape tree locations in a given shape tree locator may have different focus nodes.

Navigating a physical shape tree hierarchy
Managed Resource Shape Tree Shape Tree Root Shape Tree Instance Root
/data/ ex:DataTree ex:DataTree /data/
-- /projects/ ex:DataCollectionTree
ex:ProjectsTree
ex:DataTree
ex:ProjectsTree
/data/
/data/projects/
---- /project-1/ ex:ProjectTree ex:ProjectsTree /data/projects/
------ /milestone-A/ ex:MilestoneTree ex:ProjectsTree /data/projects/
-------- /task-43/ ex:TaskTree ex:ProjectsTree /data/projects/
-------- /task-48/ ex:TaskTree ex:ProjectsTree /data/projects/
---------- /attachment-aa89 ex:AttachmentTree ex:ProjectsTree /data/projects/
-------- /task-61/ ex:TaskTree ex:ProjectsTree /data/projects/
-------- /issue-22/ ex:IssueTree ex:ProjectsTree /data/projects/
---------- /attachment-cd12 ex:AttachmentTree ex:ProjectsTree /data/projects/
---------- /attachment-ef55 ex:AttachmentTree ex:ProjectsTree /data/projects/
-------- /issue-31/ ex:IssueTree ex:ProjectsTree /data/projects/
Shape Tree Locator for /data/projects with multiple shape tree locations in a nested physical hierarchy
PREFIX st: <http://www.w3.org/ns/shapetrees#> 
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>  
PREFIX ex: <http://www.example/ns/ex#>

<> st:hasShapeTreeLocator <#locator> .

<#locator>
  a st:ShapeTreeLocator ;
  st:location [
    st:hasRootShapeTree ex:DataTree ;
    st:hasShapeTree ex:DataTypeTree ;
    st:hasRootShapeTreeInstance <https://storage.example/data/> ;
    st:node <https://storage.example/data/projects#collection> ;
    st:shape ex:DataCollectionShape ;
  ], [
    st:hasRootShapeTree ex:ProjectsTree ;
    st:hasShapeTree ex:ProjectsTree ;
    st:hasRootShapeTreeInstance <https://storage.example/data/projects/> ;
    st:node <https://storage.example/data/projects#collection> ;
    st:shape ex:ProjectCollectionShape ;
  ] .
Shape Tree Locator for /data/projects/project-1/milestone-A/task-48 with a single shape tree location in a nested physical hierarchy
PREFIX st: <http://www.w3.org/ns/shapetrees#> 
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>  
PREFIX ex: <http://www.example/ns/ex#>

<> st:hasShapeTreeLocator <#locator> .

<#locator>
  a st:ShapeTreeLocator ;
  st:location [
    st:hasRootShapeTree ex:ProjectsTree ;
    st:hasShapeTree ex:TaskTree ;
    st:hasRootShapeTreeInstance <https://storage.example/data/projects/> ;
    st:node <https://storage.example/data/projects/project-1/milestone-A/task-48#task> ;
    st:shape ex:ProjectCollectionShape ;
  ] .

A shape tree location may be used to provide shape validation only, in which case only the focus node and shape are provided, via st:node and st:shape, respectively.

A shape tree locator providing only shape validation
Managed Resource Shape Focus Node
/data/projects/project-1 ex:ProjectShape /data/projects/project-1#project
PREFIX st: <http://www.w3.org/ns/shapetrees#> 
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>  
PREFIX ex: <http://www.example/ns/ex#>
PREFIX project1: <https://storage.example/data/projects/project-1#>
  
<> st:hasShapeTreeLocator <#locator> .

<#locator>
  a st:ShapeTreeLocator ;
  st:location [
    st:node <https://storage.example/data/projects/project-1#project> ;
    st:shape ex:ProjectShape ;
] .

3.1. Shape Tree Locator Schema

ShEx Schema for a Shape Tree Locator
PREFIX st: <http://www.w3.org/ns/shapetrees#>
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>  
PREFIX xsd: <http://www.w3.org/2001/XMLSchema#>

<#ShapeTreeLocatorShape> {
  a [st:ShapeTreeLocator] ;
  st:location @<#ShapeTreeLocationShape>+
}  

<#ShapeTreeLocationShape> {
  st:hasRootShapeTree IRI ;
  st:hasShapeTree IRI ;
  st:hasRootShapeTreeInstance IRI ;
  ( st:node IRI ;
    st:shape IRI )?
  |
  st:node IRI ;
  st:shape IRI
}

4. Shape Tree Operations

Working with shape trees entails using several higher-level operations —each of which may represent one or more HTTP requests and/or pieces of processing logic.

In regular use, a client-side agent manipulates resources on a resource server running a server-side agent. That server-side agent applies logic for shape tree validation and navigation where applicable when processing requests from client-side agents.

The key operations used to manage shape trees are:

These operations make use of reusable, internal algorithms defined in Shape Tree Algorithms.

Note: Shape tree logic can be applied by server-side agents implementing different protocols such as [LDP] or [Solid]. The operations defined herein defer to the implementing protocol as to the appropriate status code and composition of HTTP responses.

4.1. Discover Shape Tree

Description
This operation is used by a client-side agent to discover any shape trees associated with a given resource.

If URI is a managed resource, the associated Shape Tree Locator will be returned.

Inputs
RESOURCEURI The URI of the resource to discover shape trees for
Outputs
LOCATOR Shape tree locator associated with the managed resource
  1. Perform an HTTP HEAD or GET on the provided RESOURCEURI.

HEAD https://storage.example/data/projects/
HTTP/1.1 200 OK
Link: <https://storage.example/meta/c560224b#locator>; rel="http://www.w3.org/ns/shapetrees#ShapeTreeLocator"
Link: <http://www.w3.org/ns/ldp#Container>; rel="type"
...other HTTP response headers omitted...
  1. Let LOCATORURI be the URI of a shape tree locator associated with RESOURCEURI with a relation type of http://www.w3.org/ns/shapetrees#ShapeTreeLocator. Depending upon the implementing protocol, this relation may be discovered in an HTTP Link header, or in the HTTP response body.

  2. If LOCATORURI is empty, the resource at RESOURCEURI is not a managed resource, and no shape tree locator will be returned.

  3. Perform an HTTP GET on LOCATORURI

GET https://storage.example/meta/c560224b#locator
...HTTP response headers omitted...
PREFIX st: <http://www.w3.org/ns/shapetrees#>
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX ex: <http://www.example/ns/ex#>

<> st:hasShapeTreeLocator <#locator> .

<#locator>
  a st:ShapeTreeLocator ;
  st:location [
    st:hasRootShapeTree ex:DataTree ;
    st:hasShapeTree ex:DataTypeTree ;
    st:hasRootShapeTreeInstance <https://storage.example/data/> ;
    st:node <https://storage.example/data/projects#collection> ;
    st:shape ex:DataCollectionShape ;
  ], [
    st:hasRootShapeTree ex:ProjectsTree ;
    st:hasShapeTree ex:ProjectsTree ;
    st:hasRootShapeTreeInstance <https://storage.example/data/projects/> ;
    st:node <https://storage.example/data/projects#collection> ;
    st:shape ex:ProjectCollectionShape ;
  ] .
  1. If a corresponding resource at LOCATORURI cannot be found, it MUST be considered an unmanaged resource.

GET https://storage.example/meta/c560224b#locator
HTTP/1.1 404 NOT FOUND
  1. If LOCATORURI is a valid shape tree locator, the resource at RESOURCEURI MUST be considered a managed resource.

4.2. Plant Shape Tree

Description
This operation marks an existing resource as being managed by one or more shape trees, by associating a shape tree locator with the resource, and turning it into a managed resource.

If the resource is already managed, the associated shape tree locator will be updated with another shape tree location for the planted shape tree.

If the resource is a container that already contains existing resources, and a recursive plant is requested, this operation will perform a depth first traversal through the containment hierarchy, validating and assigning as it works its way back up to the target root resource of this operation.

Note: Whether a recursive plant operation should be supported is currently under debate. Related Issue

4.2.1. Client-side

Inputs
TR The URI of the resource to plant on
TST A URI representing the shape tree to plant for TR
FN A OPTIONAL URI representing the target subject within TR used for shape validation
RECURSIVE An OPTIONAL boolean flag that is FALSE by default. When TRUE, it specifies a recursive plant over a physical hierarchy of already existing resources
Outputs
LOCATORURI An HTTP response containing a Location header with the URI of the Shape Tree Locator that TST was planted in
  1. Discover if TR is a managed resource.

  2. Perform an HTTP PUT or PATCH on LOCATORURI to create or update the Shape Tree Locator for TR

    • If TR is already managed, add a new st:ShapeTreeLocation to the existing st:ShapeTreeLocator

    • If TR is not already managed, create a new st:ShapeTreeLocator, with a corresponding st:ShapeTreeLocation LN

    • Let LN hasShapeTree be TST

    • Let LN hasRootShapeTree be TST

    • Let LN hasRootShapeTreeInstance be TR

    • If TST has an st:shape

      • Let LN st:shape be the object value of TST st:shape

      • Let LN st:node be FN

4.2.2. Server-side

Inputs
REQ An HTTP PUT or PATCH request on LOCATORURI from the previous sequence
Outputs
LOCATORURI An HTTP response containing a Location header with the URI of the planted Shape Tree Locator

Note: The following sequence is invoked by the server in response to the HTTP PUT on LOCATORURI by the client-side agent in the previous sequence.

  1. Proceed if REQ contains an HTTP Link header with a relation of http://shapetrees.org/#PlantShapeTree

  2. If REQ attempts to alter an existing shape tree location, the server MUST return 409 Conflict

  3. Let LOCATORURI be the target URI of REQ

  4. Let TR be the target resource directly associated with LOCATORURI

  5. Let PC be the parent container of TR

  6. Let PCST be the shape tree associated with PC with an st:contains value

  7. Let RECURSIVE be FALSE unless REQ contains an HTTP Link header with a relation of http://shapetrees.org/#PlantShapeTreeRecursive

  8. For each new Shape Tree Location LN in REQ

    1. Let TST be the target shape tree LN st:hasShapeTree to plant for TR

    2. Let FN be an optional focus node for validation LN st:node

    3. If TR is a container call § 5.1 Assign Shape Tree to Container with inputs:

    4. If R is a non-container resource call § 5.2 Assign Shape Tree to Resource

  9. Return LOCATORURI in the HTTP Location header

4.3. Unplant Shape Tree

Description
This operation unassigns a planted root shape tree from a root shape tree instance. If the root shape tree instance is a managed container, it will also unassign contained resources.

If there are no remaining shape trees managing the resource, it would no longer be considered as managed.

4.3.1. Client-side

Inputs
TR The URI of the target managed resource to unplant
TST A URI representing the target shape tree to unplant for TR
Outputs
RESPONSE A standard HTTP response
  1. Let LOCATOR be the Shape Tree Locator returned from § 4.1 Discover Shape Tree with inputs: TR

  2. Return 422 Unprocessable Entity if LOCATOR has zero or more than one shape tree locations where st:hasShapeTree is TST

  3. If LOCATOR has a single shape tree location

    1. Perform an HTTP DELETE on LOCATOR to fully remove the Shape Tree Locator for TR

  4. If LOCATOR has more than one shape tree location

    1. Let LN be the shape tree location where st:hasShapeTree is TST

    2. Perform an HTTP PUT or PATCH on LOCATOR to remove LN

4.3.2. Server-side

Inputs
REQ An HTTP PUT, PATCH, or DELETE request on the shape tree locator LOCATOR from the previous sequence.
Outputs
RESPONSE A standard HTTP response
  1. Let LOCATOR be the shape tree locator associated with TR

  2. Let LN be the shape tree location associated with TR where:

    • LN st:hasShapeTree is TST

    • LN st:hasShapeTreeRoot is ROOTST

    • LN st:hasShapeTreeRootInstance is ROOTSTI

  3. If LOCATOR or LN are empty MUST return 404 Not Found

  4. If TR is a container

    1. Call § 5.3 Unassign Shape Tree from Container with inputs:

      • TR - Target Container

      • TST - Target Shape Tree to unassign

      • ROOTST - Root Shape Tree to unplant

      • ROOTSTI - Root Shape Tree instance to unplant

  5. If TR is a non-container resource

    1. Call § 5.4 Unassign Shape Tree from Resource with inputs:

      • TR - Target Resource

      • TST - Target Shape Tree to unassign

      • ROOTST - Root Shape Tree to unplant

      • ROOTSTI - Root Shape Tree instance to unplant

4.4. Create Shape Tree Instance

Description
This operation creates a shape tree instance within a managed container.

Note: This operation can be performed as a standard HTTP operation with no knowledge of shape trees. However, server-side processing is more efficient when the target shape tree and focus node for validation can be provided by the client-side agent.

4.4.1. Client-side

Inputs
TR The URI of the target resource
TST An OPTIONAL URI representing the target shape tree associated with the created resource
FN An OPTIONAL URI representing the target subject within TR used for shape validation
Outputs
RESPONSE A standard HTTP response
  1. Perform an HTTP POST or PUT on TR to create the shape tree instance including:

    • An HTTP Link header with the relation of http://shapetrees.org/#TargetShapeTree if SHAPETREEURI is provided

    • An HTTP Link header with the relation of http://shapetrees.org/#FocusNode if FNURI is provided

4.4.2. Server-side

Inputs
REQ A HTTP POST or PUT request on the managed container MC from the previous sequence
Outputs
RESPONSE A standard HTTP response
  1. Let TR be the proposed resource from REQ

  2. Let PC be the URI of the target container

  3. Let LR be the URI of a shape tree locator discovered for PC

  4. Let PCST be the URI of a shape tree with st:contains in LR

  5. If PCST exists

    1. Let TST be the target shape tree URI from an HTTP Link header with a relation of http://shapetrees.org/#TargetShapeTree

    2. Let FN be a focus node URI from an HTTP Link header with a relation of http://shapetrees.org/#FocusNode

    3. Let ROOTST and ROOTSTI be the root shape tree and root shape tree instance associated with the Shape Tree Location for PCST

    4. Let TSTMATCH be the return value of § 5.6 Find Matching Contained Shape Tree with inputs: PC, TR, TST, FN. TSTMATCH is an RDF graph containing:

      • st:hasShapeTree - matched shape tree in PC st:contains

      • st:shape - matching shape (if applicable)

      • st:node - focus node of shape match (if applicable)

    5. If TSTMATCH is not NULL

      1. Call § 5.5 Check Resource Conformance with inputs: TR, TSTMATCH st:HasShapeTree, TSTMATCH st:node

  6. Create resource TR

  7. If PCST exists

    1. Call § 5.2 Assign Shape Tree to Resource with inputs:

4.5. Update Shape Tree Instance

Description
This operation updates a managed resource for an existing shape tree instance.

Note: This operation can be performed as a standard HTTP operation with no knowledge of shape trees. However, server-side processing is more efficient when the target shape tree and focus node for validation can be provided by the client-side agent.

4.5.1. Client-side

Inputs
TR The URI of the target resource
Outputs
RESPONSE A standard HTTP response
  1. Perform an HTTP PUT or PATCH on an existing resource TR to update the shape tree instance

4.5.2. Server-side

Inputs
REQ A HTTP PUT or PATCH request on the managed resource from the previous sequence
Outputs
RESPONSE A standard HTTP response
  1. Let TR be the target resource of REQ

  2. Let LR be the URI of a shape tree locator discovered for TR

  3. If LR exists

    1. For each shape tree location LN in LR

      1. Call § 5.5 Check Resource Conformance with inputs: TR, LN st:hasShapeTree, LN st:node

  4. Update resource TR

4.6. Delete Shape Tree Instance

Description
This operation deletes a managed resource for an existing shape tree instance.

Note: This operation should be performed as a standard HTTP operation with no knowledge of shape trees. It is included here for completeness

4.6.1. Client-side

Inputs
TR The URI of the target resource
Outputs
RESPONSE A standard HTTP response
  1. Perform an HTTP DELETE on an existing resource TR to delete the shape tree instance

4.6.2. Server-side

Inputs
REQ An HTTP DELETE request on the managed resource from the previous sequence
Outputs
RESPONSE A standard HTTP response
  1. Let TR be the target resource of REQ

  2. Delete resource TR

5. Shape Tree Algorithms

The following algorithms define a library of functions referenced in the above operations.

5.1. Assign Shape Tree to Container

Description
Assigns the target shape tree TST to the target container resource TR.

It will perform recursive assignment if the recursive plant option RECURSIVE is set.

Note: Whether a recursive plant operation should be supported is currently under debate. Related Issue

Inputs
TC The URI of the target container to plant shape tree TST
TST The URI of an Optional target shape tree to plant for TC
FN An Optional focus node to use for shape validation when TST st:shape is set
PC The parent container of TC
PCST The shape tree associated with PC with st:contains
ROOTST The root shape tree for the current physical hierarchy
ROOTSTI The root shape tree instance for the current physical hierarchy
RECURSIVE Boolean indicator to perform a recursive plant operation. Default is FALSE
Outputs
LOCATIONURI The URI of the Shape Tree Location assigned to TC
  1. Server MUST return 422 Unprocessable Entity if RECURSIVE is FALSE and TC contains any number of resources

  2. If TST is NULL:

    1. Let TSTMATCH be the return value of § 5.6 Find Matching Contained Shape Tree with inputs: PC, TR, NULL, NULL. TSTMATCH is an RDF graph containing:

      • st:hasShapeTree - matched shape tree in PC st:contains

      • st:shape - matching shape (if applicable)

      • st:node - focus node of shape match (if applicable)

    2. Return NULL if TSTMATCH is NULL

    3. Let TST be TSTMATCH st:hasShapeTree

    4. Let FN be TSTMATCH st:node

  3. If RECURSIVE is TRUE

    1. If TST st:contains is set:

      1. For each container contained in TC:

        1. Let CTC be the contained target container

        2. Call § 5.1 Assign Shape Tree to Container with inputs:

      2. For each non-container resource contained in TC:

        1. Let CTR be the contained target resource

        2. Call § 5.2 Assign Shape Tree to Resource with inputs:

  4. Let LOCATIONURI be the Shape Tree Location returned from § 5.2 Assign Shape Tree to Resource with inputs:

  5. Return LOCATIONURI

5.2. Assign Shape Tree to Resource

Description
Assigns the target shape tree TST to the target resource resource TR. Can be called for both container and non-container resources.
Inputs
TR The URI of the target resource to assign shape tree TST
TST The URI of the target shape tree to assign for TR
FN An Optional focus node to use for shape validation when TST st:shape is set
PC The parent container of TR
PCST The shape tree associated with PC with st:contains
ROOTST The root shape tree for the current physical hierarchy
ROOTSTI The root shape tree instance for the current physical hierarchy
Outputs
LOCATIONURI The URI of the Shape Tree Location assigned to TR
  1. Let LOCATOR be the Shape Tree Locator directly associated with TR, such as by calling § 4.1 Discover Shape Tree.

  2. If TST is NULL:

    1. Let TSTMATCH be the return value of § 5.6 Find Matching Contained Shape Tree with inputs: PC, TR, NULL, NULL. TSTMATCH is an RDF graph containing:

      • st:hasShapeTree - matched shape tree in PC st:contains

      • st:shape - matching shape (if applicable)

      • st:node - focus node of shape match (if applicable)

    2. Return NULL if TSTMATCH is NULL

    3. Let TST be TSTMATCH st:hasShapeTree

    4. Let FN be TSTMATCH st:node

  3. Call § 5.5 Check Resource Conformance with inputs:

    • TR - target resource to validate

    • TST - shape tree to validate against

    • FN - focus node for shape validation

  4. Create a new Shape Tree Location LN in LOCATOR with properties:

    • LN st:hasShapeTree - TST

    • LN st:hasRootShapeTree - ROOTST

    • LN st:hasRootShapeTreeInstance - ROOTSTI

    • LN st:node - FN

    • LN st:shape - TST st:shape

  5. return LN

5.3. Unassign Shape Tree from Container

Description
Unassigns the target shape tree TST from the target container resource TC. This will perform recursive unassignment.
Inputs
TC The URI of the target container to unassign shape tree TST
TST The URI of the target shape tree to unassign for TC
ROOTST The root shape tree for the current physical hierarchy
ROOTSTI The root shape tree instance for the current physical hierarchy
Outputs
LOCATIONURI The URI of the Shape Tree Location assigned to TC
  1. Let LOCATOR be the shape tree locator associated with TC

  2. Let LN be the shape tree location associated with TC where:

    • LN st:hasShapeTree is TST

    • LN st:hasShapeTreeRoot is ROOTST

    • LN st:hasShapeTreeRootInstance is ROOTSTI

  3. Return NULL if LOCATOR or LN are not found

  4. If TST st:contains is set:

    1. Let TSTC be a set of shape trees linked via TST st:contains

    2. For each container CTC contained in TC

      1. Let CTCLR be the shape tree locator associated with CTC

      2. Let CTCLN be a location in CTCLR with a shape tree in TSTC

      3. Continue if CTCLN is empty

      4. Call § 5.3 Unassign Shape Tree from Container with inputs: CTC, CTCLN st:hasShapeTree, ROOTST, ROOTSTI

    3. For each resource CTR contained in TC

      1. Let CTRLR be the shape tree locator associated with CTR

      2. Let CTRLN be a location in CTRLR a shape tree in TSTC

      3. Continue if CTRLN is empty

      4. Call § 5.4 Unassign Shape Tree from Resource with inputs: CTR, CTRLN st:hasShapeTree, ROOTST, ROOTSTI

  5. Call § 5.4 Unassign Shape Tree from Resource on TC with inputs: TC, TST, ROOTST, ROOTSTI

5.4. Unassign Shape Tree from Resource

Description
Unassigns the target shape tree TST from the target resource resource TR. Can be called for both container and non-container resources.
Inputs
TR The URI of the target resource to unassign shape tree TST from
TST The URI of the target shape tree to unassign for TR
ROOTST The root shape tree for the current physical hierarchy
ROOTSTI The root shape tree instance for the current physical hierarchy
Outputs
LOCATIONURI The URI of the Shape Tree Location unassigned from TR
  1. Let LOCATOR be the shape tree locator associated with TC

  2. Let LN be the shape tree location associated with TC where:

    • LN st:hasShapeTree is TST

    • LN st:hasShapeTreeRoot is ROOTST

    • LN st:hasShapeTreeRootInstance is ROOTSTI

  3. Return NULL if LOCATOR or LN aren’t found

  4. Remove LN from LOCATOR

  5. Remove LOCATOR is there are no remaining shape tree locations

5.5. Check Resource Conformance

Description
This algorithm is responsible for determining whether a given resource conforms with a given
Inputs
TR The URI of the target resource to validate
TST The URI of the target shape tree to validate against TR
FN An Optional focus node to use for shape validation when TST st:shape is set
Outputs
Boolean TRUE if validation is successful. Returns an HTTP error code on failure.
  1. Server MUST return 422 Unprocessable Entity if the value of TST st:expectsType does not match the resource type of TR

  2. Server MUST return 422 Unprocessable Entity if the value of TST st:shape is not empty and shape validation of the RDF graph body of REQ fails.

    • If TST st:node is not empty, it should be considered as the focus node for shape validation. Otherwise, shape validation should be evaluated against all subject nodes in the RDF graph body of REQ

5.6. Find Matching Contained Shape Tree

Description
This algorithm is responsible for determining which shape tree within a set of shape trees mentioned in st:contains is applicable for a given proposed resource.

Note: This algorithm MAY be performed by either a client or server-side agent.

Inputs
PC The URI of the parent managed container that will contain the proposed resource
TR The proposed resource to be stored in PC
TST An OPTIONAL URI representing the shape tree corresponding with the proposed resource. No other shape trees from PC are considered when provided.
FN An OPTIONAL URI representing the target subject within TR used for shape validation.
Outputs
CSTMATCH An RDF graph containing:
  • st:hasShapeTree - matched shape tree in PC st:contains
  • st:shape - matching shape (if applicable)
  • st:node - matching focus node (if applicable)
  1. Let MST be the shape trees managing PC found through discovery

  2. Let CST be the shape tree within MST with an st:contains value(s)

  3. Let CSTC be the shape trees associated with CST st:contains. These will be the candidate shape trees that TR must match against

  4. If TST is specified

    1. and TST does NOT exist within CSTC this algorithm MUST return a 400 status code

    2. and TST exists within CSTC return an RDF graph containing:

      • st:hasShapeTree - TST

      • st:shape - TST st:shape

      • st:node - FN

  5. If TST is not specified, iterate each shape tree CSTC-ST in CSTC to determine match:

    1. Continue to the next iteration if the resource type of TR is not the same as CSTC-ST st:expectsType

    2. Continue to the next iteration if there is no subject node in TR that successfully validates against CSTC-ST st:shape

    3. Return an RDF graph containing:

      • st:hasShapeTree - CSTC-ST

      • st:shape - CSTC-ST st:shape

      • st:node - the matching subject node from successful validation of CSTC-ST st:shape

  6. If CSTC does not contain any of st:AllowAll, st:AllowResources, st:AllowContainers, st:AllowNonRDFSources, this algorithm MUST return a status code of 422

  7. If st:AllowOnly exists within CSTC, this algorithm MUST return a status code 422

  8. If st:AllowAll exists within CSTC, return NULL - indicating that while no match was found, PC has been configured to allow resources of any type to be created without matching the shape tree

  9. If st:AllowResources exists within CSTC:

    1. And the resource type of TR isn’t an st:Resource, this algorithm MUST return a status code of 422

    2. And the resource type of TR is a st:Resource, return NULL - indicating that while no match was found, PC has been configured to allow non-container resources to be created without matching the shape tree

  10. If st:AllowContainers exists within CSTC:

    1. And the resource type of TR is not an st:Container, this algorithm MUST return a status code of 422

    2. And the resource type of TR is an st:Container, return NULL - indicating that while no match was found, PC has been configured to allow containers to be created without matching the shape tree

  11. If st:AllowNonRDFSources exists within CSTC:

    1. And the resource type of TR is not an st:NonRDFResource, this algorithm MUST return a status code of 422

    2. And the resource type of TR is a Non-RDF resource, return NULL - indicating that while no match was found, PC has been configured to allow non-RDF resources to be created without matching the shape tree

6. Describing Shape Trees

While the RDF structure of shape trees enable machine readability, additional context is needed to make it human-friendly.

External SKOS graphs can be OPTIONALLY linked to describe the shape tree in human-readable terms.

ShEx validation of a Shape Tree Decorators
PREFIX st: <http://www.w3.org/ns/shapetrees#>
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX xsd: <http://www.w3.org/2001/XMLSchema#>
PREFIX skos: <http://www.w3.org/2004/02/skos/core#>

<#DecoratorIndex> {
  a [ st:ShapeTreeDecoratorIndex ] ;
  st:defaultLanguage xsd:language ? ;
  st:hasSet IRI*
}

<#DecoratorSet> {
  a [ st:ShapeTreeDecoratorSet ] ;
  st:usesLanguage xsd:language ;
  st:hasShapeTreeDecoratorResource IRI
}

<#Decorator> {
  a [ st:ShapeTreeDecorator ] ;
  st:hasShapeTree IRI ;
  skos:prefLabel xsd:string ;
  skos:definition xsd:string ?
}
  

SKOS constructs such as skos:narrower MAY be used to group or organize related shape trees.

7. Definitions

Two terms are imported from [RDF]:

The following terms are used throughout this specification:

Conformance

Document conventions

Conformance requirements are expressed with a combination of descriptive assertions and RFC 2119 terminology. The key words “MUST”, “MUST NOT”, “REQUIRED”, “SHALL”, “SHALL NOT”, “SHOULD”, “SHOULD NOT”, “RECOMMENDED”, “MAY”, and “OPTIONAL” in the normative parts of this document are to be interpreted as described in RFC 2119. However, for readability, these words do not appear in all uppercase letters in this specification.

All of the text of this specification is normative except sections explicitly marked as non-normative, examples, and notes. [RFC2119]

Examples in this specification are introduced with the words “for example” or are set apart from the normative text with class="example", like this:

This is an example of an informative example.

Informative notes begin with the word “Note” and are set apart from the normative text with class="note", like this:

Note, this is an informative note.

Conformant Algorithms

Requirements phrased in the imperative as part of algorithms (such as "strip any leading space characters" or "return false and abort these steps") are to be interpreted with the meaning of the key word ("must", "should", "may", etc) used in introducing the algorithm.

Conformance requirements phrased as algorithms or specific steps can be implemented in any manner, so long as the end result is equivalent. In particular, the algorithms defined in this specification are intended to be easy to understand and are not intended to be performant. Implementers are encouraged to optimize.

Index

Terms defined by this specification

References

Normative References

[RFC2119]
S. Bradner. Key words for use in RFCs to Indicate Requirement Levels. March 1997. Best Current Practice. URL: https://tools.ietf.org/html/rfc2119

Informative References

[LDP]
Steve Speicher; John Arwe; Ashok Malhotra. Linked Data Platform 1.0. URL: https://www.w3.org/TR/ldp/
[RDF]
Richard Cyganiak; David Wood; Markus Lanthaler. RDF 1.1 Concepts and Abstract Syntax. URL: https://www.w3.org/TR/rdf11-concepts
[SHACL]
Holger Knublauch; Dimitris Kontokostas. Shapes Constraint Language (SHACL). 20 July 2017. REC. URL: https://www.w3.org/TR/shacl/
[ShEx]
Eric Prud'hommeaux; et al. Shape Expressions Language 2.1. URL: http://shex.io/shex-semantics/index.html
[SHEXPATH]
Eric Prud'hommeaux. Shape Expressions ShExPath Language. URL: https://shexspec.github.io/spec/ShExPath
[SKOS-REFERENCE]
Alistair Miles; Sean Bechhofer. SKOS Simple Knowledge Organization System Reference. 18 August 2009. REC. URL: https://www.w3.org/TR/skos-reference/
[Solid]
Sarven Capasdisli; et al. Solid Protocol. URL: https://solidproject.org/TR/protocol

Issues Index

Do we want a notion for static resources? Related Issue