We introduce the formalism of Linked Systems for specifying and executing dynamical systems that operate over ReadWrite Linked Data. Linked Systems cover user agents (components that emit HTTP requests) and servers (components that receive HTTP requests). The formalisation is inspired by automata theory and the concepts of state transition systems and state machines. For the proposed formalism to scale to the web, we try to minimise the burden on component providers. We thus assume a Read-Write Linked Data interface that offers only a few operations: resources identified via URIs can be created and deleted, and the state of resources is expressed in RDF and can be read and updated. Our near-term goal is to provide executable specifications of autonomous behaviour expressed in a rule-based language, without requiring formal service descriptions of the operations on resources. In the long term, we plan to use our formalism as basis for applying techniques from the fields of formal verification and artificial intelligence (AI) planning.
Users can gain access to arbitrary content and functionality on the web with a browser in one unified user interface. On mobile devices, however, the dominant user interface to content and functionality are apps. Each tailored app communicates with a backend server, often via web protocols. Universal user interfaces are desirable so that users can comfortably access any network-accessible component or combinations of components. Potential future universal user interfaces could be dialogue systems, such as chatbots and virtual assistants, or virtual reality environments.
A fundamental research challenge has been to find the appropriate abstractions for interfaces to networked components to facilitate the interaction with components and enable the interoperation between them. Realising the overall goal of enabling flexible access to content and functionality from a large number of sources requires at least the following from component providers: 1. A uniform protocol to decentralised components, to be able to manipulate and interact with components without writing adaptors. 2. A uniform data model, a suitable knowledge representation language and an associated query language, to be able to represent, integrate and query data on a global scale. 3. A uniform description of the behaviour of components, to be able to apply techniques from the fields of formal verification and AI planning.
With these uniform interfaces we could specify and
execute systems that operate autonomously; perform static
analysis, verification and simulation of these systems; and
automatically generate these systems, given component
descriptions and a goal. While these uniform interfaces been
available in closed systems (for example, in the field of
artificial intelligence), such a level of elaboration has been
elusive on the web, which is an open decentralised system with
many contributors. Different communities, however, work
towards providing (parts of) elaborate uniform interfaces in
open environments:
1. The followers of the architectural style
Representational State Transfer (REST) [
richardsonMaturityModel.html 3. Finally, different communities concerned with dynamical systems (for instance, control systems and cyberphysical systems) abstract from specific protocols and often use a simple data model. Formal descriptions of services or actions – the “laws” of a system – are central to the applied verification methods, such as model checking or simulation. The Semantic Web community had attempted to create a respectable amount of fully-described services, and the REST community is working towards having standardised input and output descriptions for APIs widely available.
Currently, we cannot assume that elaborate uniform interfaces to components are commonplace on the open web. Today, many APIs provide a resource-oriented modelling with constrained operations (REST). Linked Data is popular for read-access to RDF data. Read-Write Linked Data, as the combination of the two popular paradigms, could provide access to a sizable amount of components with a limited additional burden for component providers, for example as specified in the W3C Linked Data Platform recommendation2 with editors from IBM and Oracle.
Thus, in this paper, we focus on manual specification of systems that operate on components which have a ReadWrite Linked Data interface, but do not provide formal service descriptions. The goal is to have a formal model of systems that are able to use and provide Read-Write Linked Data resources. We present an approach for executable formal specifications. The approach can be extended to support formal verification and AI planning in case a sufficient amount of components with formal service descriptions should become available.
We have applied prototypes that implement the proposed
formalism for specifying interactive systems based on a
ReadWrite Linked Data interface in several settings. In the
German ARVIDA project3, we break up monolithic industrial
Virtual and Augmented Reality (VR and AR) systems into
components with a Read-Write Linked Data interface, and
specify and execute VR applications based on these
interfaces. In the European i-VISION project4, we provide means
to connect a workflow analysis software with a flight
simulator to perform Human Factors analysis of aircraft
cockpits in a VR environment at run-time; the components are
also based on Read-Write Linked Data interfaces. We have
demonstrated that the execution of the system specifications
achieved update rates sufficient for an immersive experience
in the VR environment [
We begin the remainder of the paper with related work in Section 2, introduce necessary definitions in Section 3, formalise the notion of a Linked System in Section 4, and conclude with a summary and a list of open issues in Section 5.
Dynamical systems are fundamental to many fields. Fields concerned with the “real” world – such as physics, control theory, and cyber-physical systems – study primarily continuous-time systems. In the digital world of computation, discrete-time systems are common, with a monotonically increasing sequence of integers denoting time (often written 2http://www.w3.org/TR/ldp
as t). Given the enormous breadth of dynamical systems, we can only provide a subjective selection of related work of the discrete-time variants.
In computational systems, Harel and Pneuli [
Formal models are popular for describing reactive systems
in closed environments [
McCarthy’s situation calculus is an early formalism to describe dynamical systems in the area of artificial intelligence. The situation calculus includes actions that can be performed in the world and fluents that describe the (changing) state of the world. As we conceptually operate on a single ternary triple predicate for representing state, we do not have the possibility to identify fluents (predicates that change over time). Also, we assume the open web as task environment rather than a closed system, and distinguish between user agents and servers.
Abstract State Machines (ASMs) [
Approaches for Web Service Composition [
The Guard-Stage-Milestone (GSM) framework for
artifactcentric workflows [
Semantic Web Services [
In the following, we provide definitions for web interfaces
based on a common access protocol and a common
knowledge representation language. We assume Read-Write Linked
Data [
The following definitions build on the notions of a resource a URI, an identifier for a resource.
Definition 1 (Resource, URI). A resource is an abstract notion for things of discourse, be they abstract or concrete, physical or virtual (e.g., a document on the web, a car, or the set of the natural numbers). A Uniform Resource Identifier (URI) is a character string that identifies a resource.
A URI has a scheme, which is the beginning of the character string until the first colon. The scheme specifies how to interpret the rest of the URI. We focus on the http scheme (the considerations analogously apply to the https scheme). Moreover, we provide an analogy for http URIs with the scheme file. Collections (e. g. lists, sets) are a particular kind of resources, treated later. 3.2
While a URI with the scheme http first is to identify a resource, the scheme also indicates that second we may be able to interact with the resource using the Hypertext Transfer Protocol (HTTP)6. HTTP is the prototypical variant of REST.
Definition 2 (HTTP Request, HTTP Response). A HTTP message is a tuple hS, H, Bi, where S is the mandatory start line, H is an optional list of header name/value pairs, and B is the message body, also optional. A HTTP request is a HTTP message in which the start line S consists of a request line (with the HTTP method and the request
URI and the version information). In a HTTP response message, the start line S consists of a HTTP status code and information on the used HTTP version.
Interaction with HTTP URIs is done in request/response pairs. The message body B of a HTTP message contains a representation of the current state of the resource identified via the request URI in the start line. Representations of state can vary over time, just like the resource can change.
A HTTP request has a HTTP method in its status line. The HTTP methods include GET, PUT, POST, and DELETE. Less popular methods include PATCH and OPTIONS7. There exists a rough mapping from the HTTP methods to the CRUD operations, create, read, update, delete – the basic operations for persistent storage, which we present as we describe the HTTP methods. We call methods that are free of side effects “safe”. The safe HTTP methods are: • A GET request retrieves the representation of the current resource state (corresponding to “read” in CRUD). • An OPTIONS request results in the methods that are allowed on a resource. The body of response messages to OPTIONS requests could contain formal service descriptions in a possible extension of our approach. We currently do not use OPTIONS.
Methods that change the state of a resource are called “unsafe” (e.g., PUT, POST, DELETE, PATCH). The unsafe requests (those are for “create”, “update” and “delete” in CRUD) are: • A PUT request with message body b assigns b as the representation of the resource state. PUT can be used to create a resource with a URI set by the client. • A PATCH request with body b updates a resource representation (remove and add data) based on the sent patch specification b. • A POST request can serve different purposes: – append data to an existing representation of a resource; – create a new resource with a URI determined by the server; or – perform RPC-style arbitrary data-processing (not possible on file URIs).
The POST request allows for data processing in a remote procedure call (RPC) fashion. Therefore, POST allows for invoking arbitrary operations (functions). To benefit from the uniform interface of REST, in this paper we only consider state updates, in-line with RMM level 2. • A DELETE request removes a resource.
If multiple applications of the same method yield the same result, we call these methods “idempotent” (e.g., GET because it is safe, PUT because if the resource state is overwritten multiple times with the same data, the resulting resource state is still the same).
Using the HTTP methods, we operate with resources identified by URIs with the http scheme. Alternatively, we
can define the HTTP methods also for URIs with the file scheme, i.e. URIs that identify files and directories. For example, GET on such a URI would retrieve the content of the file; PUT on a file URI would create the file with the payload; PUT on a file URI ending in a slash character would create a directory. 3.3
As indicated by the Linked Data principles, we assume that the representation of the state of resources is given using the Resource Description Framework (RDF) in an RDF graph.
Definition 3 (RDF Term, Triple, Graph). The set of RDF terms consists of the set of URIs U , the set of blank nodes B and the set of RDF literals L, all being pairwise disjoint. A tuple hs, p, oi ∈ (U ∪ B) × U × (U ∪ B ∪ L) is called an RDF triple, where s is the subject, p is the predicate, and o is the object of the triple. A set of triples is called RDF graph.
To be able to talk about the state representations retrieved from multiple resources, i.e. multiple RDF graphs, we introduce the notion of an RDF dataset.
Definition 4 (Named Graph, RDF Dataset). Let G be the set of RDF graphs and let U be the set of URIs. A pair hg, ui ∈ G × U is called a named graph. An RDF dataset consists of a (possibly empty) set of named graphs (with distinct names) and a default graph g ∈ G without a name.
To talk about the state of resources at different times, we introduce an index t, which denotes the point in time to which an RDF dataset D refers, thus yielding Dt. We assume discrete time represented as monotonically increasing integers.
In the following, we first introduce the general notion for dynamics in Linked Data which we call Linked Data Transition System. We then define user agents and servers, and next outline Linked Systems.
The Linked Data Platform (LDP) recommendation poses restrictions on how to interact with web resources, particularly collection resources, in a Linked Data context. Our Read-Write Linked Data interface as described in the following definitions adheres to LDP where it concerns HTTPbased interaction with collection resources. We omit the various header fields that are part of LDP.
On the web, we operate in a decentralised system in which we cannot control each participant. REST provides a limited set of constraints on the components that allow users to assume a certain behaviour. The use of resource-based CRUD operations is one such constraint. However, certain behaviours are under-specified. For instance, if we overwrite a resource state with PUT, the resulting state of the resource may differ from what has been sent in the message body of the PUT request. Also, changing the state of resource A may affect the state of resource B. In our definitions of the semantics of HTTP operations that follow, we allow such side effects only to occur between collection resources and element resources. 4.1
Let S be an RDF dataset. We write St for RDF dataset S at time t. With GET, we are able to obtain the resource state, so that we can process the resource state as part of our world model. Let u be a URI from U identifying not a collection resource. Let r a request/response pair involving u which relates to a named graph in S.
We contrast the current state t of an RDF dataset S before the request/response pair r with the state of S at t + 1 after the request/response pair r. Now we can formally define how PUT, POST and DELETE behave. We denote a “don’t-care” as a dot (“·”).
• PUT: Let r be a request/response pair hPUT u, ·, Bi, h200 OK, ·, ·i. Applying r to St yields St+1, where in St+1 the triples belonging to u are B. • POST: Let r be a request/response pair hPOST u, ·, Bi, h200 OK, ·, ·i. Applying r to St yields St+1, where in St+1 there are additional triples (related to those in B, if B 6= ∅) related to u. • DELETE: Let r be a request/response pair hDELETE u, ·, ·i, h204 No Content, ·, ·i. Applying r to St yields St+1, where in St+1 there is no representation available at u.
Now, let uc be a URI from U identifying a collection resource.
• PUT: PUT is not possible on collection resources (we assume collections are managed by the server). LDP does not require the PUT request to be supported in the context of collections either. • POST: Let r be a request/response pair hPOST uc, ·, Bi, h201 Created, H, ·i. Applying r to St yields St+1, where in St+1 there are additional triples (those in B) related to a newly created8 URI ue that is linked to uc. Also, uc is different now, as the link to the newly created resource identified via URI ue is part of the state of the collection resource. The set of headers H contains ue as the value of the Location header. In compliance with LDP, we assume no representation in the body of the response. • DELETE: Let r be a request/response pair hDELETE uc, ·, ·i, h204 No Content, ·, ·i. Applying r to St yields St+1, where in St+1 there is no representation available for uc. Whether deleting the collection resource uc also affects its associated element resources depends on the type of the relation between the collection and its elements (cf. the container types specified in LDP). 4.2
Having covered the semantics of one transition from t to t + 1, we now can define a transition system that describes resource states (represented as RDF datasets) over multiple transitions. That is, we can we say what happens with the resource state at t + 1 relative to resource state at t.
Definition 5 (Linked Data Transition System). Let Req, Resp be the set of all request/response pairs with unsafe operations. A Linked Data Transition System is a pair (S, →): 8Or taken from a pre-filled reservoir of URIs, for example as defined in ASMs. • A set of RDF datasets S representing resource states. • The transition relation → over S × 2Req,Resp × S. We can contrast the current state st with the next state st+1, given a transition occurs. A transition consists of a set of request/response pairs.
For Linked Data Transition Systems we assume an omniscient view, where we assume we can readily observe all request/response pairs in the system and all resource states. The states S are the states of all resources in the system. We write s0, s1 . . . sn to denote datasets at different time points. We write (so, ro, s1) ∈→ as so −r→0 s1. We can define the history of a system by a sequence so −r→0 s1 −→ s2 . . ., where r1 so, s1, s2 are states, and r0, r1 are sets of request/response pairs.
Next, we introduce a limited point of view, where we distinguish the direction of requests relative to a user agent or server. 4.3
We now can define the notion of a Linked Data User Agents and Linked Data Servers. A HTTP message exchange involves two parties: user agents and servers. The user agent creates the request and the server creates the response.
Definition 6 (User Agent, Action). Let Req be a HTTP request message, and Resp be a HTTP response message. The function send(Req, Resp) denotes a system emitting Req and receiving Resp. An action is an outgoing request/response pair. User agents are systems that emit actions.
We can group the actions into safe actions (GET) and unsafe actions (PUT, POST, DELETE and PATCH).
Definition 7 (Server, Event). Let Req be a HTTP request message, and Resp be a HTTP response message. The function receive(Req, Resp) denotes a system receiving Req and sending Resp. An event is an incoming request/response pair. Servers are systems that receive events.
We can group the events into safe events (GET) and unsafe events (PUT, POST, DELETE and PATCH).
The same request/response pair is regarded as an action in the user agent and as an event on the server. Informally, the difference between user agents and servers is similar to the difference between generators and recognisers in state machines. 4.4
We can now define the notion of a Linked System.
Definition 8 (Linked System). Let A be the set of all (outgoing) unsafe actions and let E be the set of all (incoming) unsafe events. A Linked System consists of the quadruple (S, s0, F, →): • A set of RDF datasets S representing resource states. • The initial state, s0 ∈ S. • A set of the final states, F ⊆ S. • The transition relation → over S × 2E × 2A × S. The transition consists of a set of events from E and a set of actions from A.
Linked Systems cover both user agents and servers. In case E is the empty set, we arrive at the special case of a Linked Data User Agent. In case A is the empty set, we arrive at the special case of a Linked Data Server.
We now can define the execution of a Linked System.
Definition 9 (Run, Step). A run of a Linked System M is a sequence of states, unsafe events, and unsafe actions. A run has multiple steps. One transition is a step. A successful run starts in s0 and ends in a state sn ∈ F , where n denotes the number of steps carried out during the run.
An example of a one-step run would be so −e−o−,a→0 s1, where s1 ∈ F .
In case the Linked System is a user agent only (and thus only emits actions), we can run the system from the command line. In case the Linked System is a server, we have to provide a HTTP interface to have the ability to receive events.
We start the execution of a Linked Data User Agent from the command line. We start with the initial state so. As the user agent does not receive events, we successively execute steps until a final state f ∈ F is reached. Each step t consists of the following: • Collect the resource state st by dereferencing the graph names in the RDF dataset st. We provide link traversal specifications using rules that yield the graph names to be dereferenced in a fixpoint procedure. We can also provide deduction rules to encode different semantics (such as RDFS or subsets of OWL). The result is a materialised version of the resource state st. • After computing the fixpoint to yield the overall resource state, carry out the unsafe requests as specified in the transition relation. The responses of the unsafe requests become part of st+1. • We also provide means to register queries that are continuously evaluated on the current internal resource state. To arrive at a fully streaming model, we are only supporting SPARQL basic graph pattern queries, which can be implemented in non-blocking operators.
As the default, a new step t + 1 immediately starts once step t has been finished. We are able to align the start of each step at specified interval boundaries, or specify a wait time between each step. We use the time-triggered execution in our VR demonstrators at 30 Hertz (one step each 33ms).
The execution of a Linked Data Server has to take into account events from the external environment. We thus arrive at an event-triggered execution model: the system runs once the incoming request (an event) arrives. The run proceeds as in the case of Linked Data User Agents. In case the run succeeds, the response to the event includes a HTTP status code in the 2xx range, denoting a successful run. Otherwise, a server error (HTTP status code 500) is returned. Per default, the union of the triples in the state st is serialised as RDF triples in the body of the response. Optionally, we can filter the triples with a query to reduce the amount of returned data.
We have provided a formal account of Read-Write Linked Data as a transition system. We have identified the two roles of user agents (components that emit actions) and servers (components that receive events), and have shown how both roles can be understood in terms of the transition system. We have outlined the notion of Linked Systems, which can be instantiated in user agent or server roles, or both.
We base the presented formalism on our experiences
collected with a prototype [
Our formalism can serve as the basis for parallel execution. Given that Linked Systems are based on fundamental notions common to many dynamical systems, the formalism could be extended to incorporate further functionality. For example, we could add invariants, which are observed and checked during execution. In case a substantial amount of descriptions for components become available, we could use AI planning to generate the transition relation in a Linked System from the descriptions of the components, given an initial and a final state. To be able to use verification techniques, we would likely define a reduced subset of the presented Linked System, for instance providing finite domains or reducing the flexibility of the RDF triples data model.
We thank Dieter Fensel for pointing out the possible connection between REST and Abstract State Machines, Martin Junghans for explaining IOPE descriptions and process calculi, and Aidan Hogan for fruitful discussions related to dynamics in Linked Data. We acknowledge support from the BMBF ARVIDA project (FKZ 01IM13001G) and AFAP, a BMBF Software Campus project (FKZ 01IS12051).