Shape Trees Specification

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:

• [RDF]'s foundation in unambiguous identifiers provides an infrastructure that allows for interoperability, but does not specifically encourage or enforce it.

• Shape languages (e.g. [ShEx] and [SHACL]) provide machine-readable, enforceable data structure definitions on single resources.

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 managed instance is a resource assigned to and in conformance with one or more shape trees via a shape tree manager. The primary resource in a managed instance is called a managed resource.

Every managed resource has an associated shape tree manager. A shape tree manager 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 manager is associated with it through the § 4.2 Plant Shape Tree operation.

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

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.

PREFIX st: <http://www.w3.org/ns/shapetrees#>
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX ex: <http://www.example.com/ns/ex#>

<> st:describedBy ex:project-en, ex:project-es, ex:project-nl, ex:project-ko .

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

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

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

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

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:referencesShapeTree, and the shape path through which it is linked via either st:viaShapePath, or st:viaPredicate.

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

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

<#VirtualMilestoneTree>
  a st:ShapeTree ;
  st:expectsType st:Resource ;
  st:shape ex:MilestoneShape ;
  st:references [
    st:referencesShapeTree <#VirtualTaskTree> ;
    st:viaPredicate ex:hasTask
  ] ,
  [
    st:referencesShapeTree <#VirtualIssueTree> ;
    st:viaPredicate ex:hasIssue
  ] .

<#VirtualTaskTree>
  a st:ShapeTree ;
  st:expectsType st:Resource ;
  st:shape ex:TaskShape ;
  st:references [
    st:referencesShapeTree st:NonRDFResourceTree ;
    st:viaShapePath "@ex:TaskShape~ex:hasAttachment"
  ] .

<#VirtualIssueTree>
  a st:ShapeTree ;
  st:expectsType st:Container ;
  st:shape ex:IssueShape ;
  st:references [
    st:referencesShapeTree st:NonRDFResourceTree ;
    st:viaShapePath "@ex:IssueShape~ex:hasAttachment"
  ] .

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

• An { ST st:expectsType T } triple identifies the resource type T of a corresponding managed resource R in STI where T MUST be one of st:Resource, st:Container, or st:NonRDFResource.

• An { ST rdfs:label L } triple indicates that there is at most one corresponding managed resource R in STI and it has the name L. L is a static resource.

• An { ST st:shape SH } triple indicates that managed resource R has at most one node which conforms to shape SH.

• An { ST st:contains ST2 } triple identifies a nested shape tree ST2.

• An { ST st:references STR } triple indicates that the shape tree identified in shape tree reference STR, is referenced through the instance data of STI.

  • An { STR st:referencesShapeTree ST3 } triple indicates a shape tree referenced through the instance data of STI

  • An { STR st:viaShapePath PATH } triple identifies the shape path through which a managed instance of ST3 can be found via the instance data of STI

  • An { STR st:viaPredicate PRED } triple identifies the RDF predicate through which a managed instance of ST3 can be found via the instance data of STI

2.1. Shape Tree Schema

<#ShapeTreeShape> {
  a [st:ShapeTree] ;
  (
    st:expectsType [st:Container] ;
    st:contains @<#LocalOrExternalShape> * ;
    |
    st:expectsType [st:Resource st:NonRDFResource]
  ) ;
  rdfs:label xsd:string ? ;
  st:references @<#ReferenceShape> * ;
  st:shape IRI ?
}

<#LocalOrExternalShape>
  @<#ShapeTreeShape> OR
  ((@<#ReservedShapeTree> OR IRI) AND {})

<#ReservedShapeTree> [
  st:ResourceTree
  st:ContainerTree
  st:NonRDFResourceTree
]

3. Assigning Shape Trees

3.1. Shape Tree Manager

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

A shape tree manager includes one or more shape tree assignments.

The server MUST advertise the URI of the shape tree manager for a given resource by responding to HTTP requests of that resource with an included HTTP Link header with a rel value of http://www.w3.org/ns/shapetrees#managedBy and the manager resource as the link target.

Conversely, the server MUST advertise the URI of the resource managed by a shape tree manager by responding to HTTP requests of the manager resource with an included HTTP Link header with a rel value of http://www.w3.org/ns/shapetrees#manages and the managed resource as the link target.

3.2. Shape Tree Assignment

A shape tree assignment is used to associate a given shape tree with a managed resource.

Shape tree assignments identify key contextual points in a physical hierarchy. A root shape tree assignment is set by the Plant Operation, and any subsequent assignment applied within that managed hierarchy reference it via st:hasRootAssignment.

If there is more than one shape tree assignment in a shape tree manager, they must all apply to the same managed resource associated with the shape tree manager.

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

Shape tree assignments in a given shape tree manager may have different focus nodes.

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#>

<>
  a st:Manager ;
  st:hasAssignment
    <#assignment1>,
    <#assignment2> .

<#assignment1>
  st:assigns ex:DataCollectionTree ;
  st:manages <https://storage.example/data/projects/>
  st:hasRootAssignment <https://storage.example/data/.shapetree#assignment1> ;
  st:focusNode <https://storage.example/data/projects/#collection> ;
  st:shape ex:DataCollectionShape .

<#assignment2>
  st:assigns ex:ProjectCollectionTree ;
  st:manages <https://storage.example/data/projects/>
  st:hasRootAssignment <https://storage.example/data/projects/.shapetree#assignment2> ;
  st:focusNode <https://storage.example/data/projects/#collection> ;
  st:shape ex:ProjectCollectionShape .

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#>

<>
  a st:Manager ;
  st:hasAssignment <#assignment1> .

<#assignment1>
  st:assigns ex:TaskTree ;
  st:manages <https://storage.example/data/projects/project-1/milestone-A/task-48> ;
  st:hasRootAssignment <https://storage.example/data/projects/.shapetree#assignment2> ;
  st:focusNode <https://storage.example/data/projects/project-1/milestone-A/task-48#task> ;
  st:shape ex:ProjectCollectionShape .

3.3. Shape Tree Manager Schema

<#ManagerShape> {
  a [st:Manager] ;
  st:hasAssignment @<#AssignmentShape> +
}

<#AssignmentShape> {
  a [st:Assignment] ;
  st:assigns IRI ;
  st:manages IRI ;
  st:hasRootAssignment IRI ;
  ( st:focusNode 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:

• Discover Shape Tree - determine the shape tree linked to some managed resource.

• Plant Shape Tree - declare that a resource will henceforth be managed by the provided shape tree.

• Unplant Shape Tree - assert that a managed resource should no longer be managed by the provided shape tree.

• Create Managed Instance - add a resource to a managed resource hierarchy.

• Update Managed Instance - modify a resource in a managed resource hierarchy.

• Delete Managed Instance - remove a resource in a managed resource hierarchy.

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

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.

Note: Server-side processing of changes to shape tree managers can support the addition and removal of multiple shape tree assignments at once. For simplicity, this specification provides discreet client-side operations to plant or unplant one shape tree at a time. However, it would not be inappropriate to provide client implementations that support requests to plant and unplant multiple shape trees for a given resource in a single request.

4.1. Discover Shape Tree

HEAD https://storage.example/data/projects/

HTTP/1.1 200 OK
Link: <https://storage.example/meta/c560224b>; rel="http://www.w3.org/ns/shapetrees#managedBy"
Link: <http://www.w3.org/ns/ldp#Container>; rel="type"
...other HTTP response headers omitted...

GET https://storage.example/data/projects/.shapetree

...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#>

<>
  a st:Manager ;
  st:hasAssignment <#assignment1> .
    
<#assignment1>
  st:assigns ex:DataCollectionTree ;
  st:manages <https://storage.example/data/projects/>
  st:hasRootAssignment <https://storage.example/data/.shapetree#assignment1> ;
  st:focusNode <https://storage.example/data/projects/#collection> ;
  st:shape ex:DataCollectionShape .

GET https://storage.example/data/projects/.shapetree

HTTP/1.1 404 Not Found

4.2. Plant Shape Tree

4.2.1. Client-side

PUT https://storage.example/data/projects/.shapetree

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#>

<>
  a st:Manager ;
  st:hasAssignment <#assignment1>, <#assignment2> .
  
<#assignment1>
  st:assigns ex:DataCollectionTree ;
  st:manages <https://storage.example/data/projects/>
  st:hasRootAssignment <https://storage.example/data/.shapetree#assignment1> ;
  st:focusNode <https://storage.example/data/projects/#collection> ;
  st:shape ex:DataCollectionShape .

<#assignment2>
  st:assigns ex:ProjectCollectionTree ;
  st:manages <https://storage.example/data/projects/>
  st:hasRootAssignment <https://storage.example/data/projects/.shapetree#assignment2> ;
  st:focusNode <https://storage.example/data/projects/#collection> ;
  st:shape ex:ProjectCollectionShape .

HTTP/1.1 204 No Content

4.2.2. Server-side

4.3. Unplant Shape Tree

4.3.1. Client-side

DELETE https://storage.example/data/projects/.shapetree

HTTP/1.1 204 No Content

4.3.2. Server-side

4.4. Create Managed Instance

4.4.1. Client-side

4.4.2. Server-side

4.5. Update Managed Instance

4.5.1. Client-side

4.5.2. Server-side

4.6. Delete Managed Instance

4.6.1. Client-side

4.6.2. Server-side

5. Shape Tree Algorithms

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

5.1. Assign Shape Tree to Resource

5.2. Unassign Shape Tree from Resource

5.3. Validate Contained Resource

5.4. Validate Resource

6. Describing Shape Trees

6.1. Shape Tree Description

While the RDF structure of shape trees enable machine readability, additional context is needed to make it human-friendly. A Shape Tree Description provides a human-readable information about a given shape tree.

Shape tree descriptions are organized into shape tree description sets.

<#DescriptionShape> {
  a [st:Description] ;
  st:inDescriptionSet @<#DescriptionSetShape> ;
  st:describes IRI ;
  st:describesInstance IRI ? ;
  skos:prefLabel xsd:string ;
  skos:definition xsd:string ? ;
  skos:narrower IRI ? ;
  skos:broader IRI? ;
}

6.2. Shape Tree Description Set

Shape tree descriptions are organized into a Shape Tree Description Set.

An RDF resource containing one or more shape trees can be OPTIONALLY linked to a shape tree description set to describe the contained shape trees in human-readable terms.

Each shape tree description set is made up of any number of shape tree descriptions.

SKOS constructs such as skos:narrower and skos:broader MAY be used to group or organize related shape trees in a given shape tree description set

<#DescriptionSetShape> {
  a [st:DescriptionSet] ;
  st:usesLanguage xsd:language
}

7. Definitions

• triple -- an RDF triple

• RDF graph -- an RDF graph as defined in [RDF].

The following terms are used throughout this specification:

• Client-side Agent -- A software component interacting with a server. A client-side agent will typically rely on the server for shape tree evaluation and/or validation, but may choose to apply it locally as well.

• Container -- the generalized notion of a collection of resources; implementations of shape trees MAY use a container implementation such as [LDP] (ldp:Container, ldp:BasicContainer, etc.)

• Ecosystem -- a software environment with resources organized in some hierarchical grouping that rely on shape tree concepts to better organize and validate structures of data

• Focus Node -- a node in an RDF graph. In the context of shape trees, one usage is directing shape validation to the appropriate node in an RDF graph.

• Managed Container -- any managed resource that is a container. A Managed Container MAY be an Instance Root or hierarchically nested within the resource hierarchy.

• Non-RDF Source -- the generalized notion of document not containing linked-data triples; this may include plain text or binary data.

• Resource -- the generalized notion of document containing linked-data; implementations of shape trees may use a resource implementation such as [LDP] (ldp:Resource, etc.)

• Server-side Agent -- A server-side software component. Server-side agents that support shape trees are responsible for data validation and maintaining shape tree managers.

• Shape -- a schema definition allowing validation of an RDF subject. Example specifications supporting the notion of shapes include [ShEx] and [SHACL].

• SKOS Graph -- an RDF graph conforming to [skos-reference] data model. For purposes of shape trees a SKOS Graph is used to describe a shape tree in human-readable terms.

• Unmanaged Resource -- any resource which does not have an associated shape tree.