State Machines (ASMs) as the formal basis for dealing with changes in Linked Data, which is the combination of the Resource Description Framework (RDF) with the Hypertext Transfer Protocol (HTTP). We provide a synthesis of ASMs and Linked Data and show how the combination aligns with the relevant specifications such as the Request/Response communication in HTTP, the guidelines for updating resource state in the Linked Data Platform (LDP) specification, and the formal grounding of RDF in model theory. Based on the formalisation of Linked Data resources that change state over time, we present the syntax and operational semantics of a small rule-based language to specify user agents that use HTTP to interact with Linked Data as the interface to the environment. We show the feasibility of the approach in an evaluation involving the specification of automation in a Smart Building scenario, where the presented approach serves as a theoretical foundation.
Data in languages such as RDF (Resource Description Framework)1, RDFS (RDF Schema)2, and OWL (Web Ontology Language)3 is widely deployed on the web4 and allow for data representation and integration. The technologies around Linked Data [3] facilitate the publication of and access to such data: data publishers make RDF files available on web servers; user agents can then access the published RDF files using HTTP (Hypertext Transfer Protocol) 5. On such read-only web data, developers can build data integration systems based on queries and ontologies, i. e. approaches grounded in mathematical logic, where most of the operations are carried out by query processors and reasoners. However, to integrate such data from read-only sources is only a first step; many scenarios, for example on the Web of Things, require to change data. With HTTPbased write access to Linked Data, we have a uniform interface on both the data and the interaction level, easing system integration. But while the W3C’s LDP (Linked Data Platform) specification 6 combines read-only Linked Data (via the HTTP GET operation)
2http://www.w3.org/TR/rdf-schema/ 3http://www.w3.org/TR/owl2-overview/ 4See e.g. the datasets in the Linking Open Data cloud at http://lod-cloud.net/ 5http://www.ietf.org/rfc/rfc7230.txt 6http://www.w3.org/TR/ldp/ with read-write capabilities (HTTP PUT, POST, and DELETE operations) for the interface to writeable resources, most systems that interact with LDP servers are still programmed in imperative code. We would like to specify the behaviour of user agents in a language grounded in mathematical logic.
A high-level language for the specification of the behaviour of user agents would allow expressing executable specifications, which are shorter and cheaper to create than imperative code, and which are easier to validate (e. g. with subject matter experts) and to analyse (e. g. using formal methods). The language could also serve as execution substrate for agent specifications created using planning approaches from Artificial Intelligence.
Several approaches exist for specifying user agents on read-only
Linked Data. These user agents process queries and have the ability
to follow links, which can lead to the discovery of additional data
during query processing [5], [16], [12], [
We present an approach for programming user agents for Linked Data. Following a hypermedia architectural style, the approach operates on a set of resources, with a resource’s state described in RDF. The resource state descriptions contain references to other resources (links). Resource state can be manipulated via HTTP operations. To formalise the user agent specifications, which cause an evolution of Linked Data over time, we build on Abstract State Machines (ASMs) [11] rooted in mathematical logic. We believe that ASMs are the right starting point: ASMs encode state in firstorder logic, which is a superset of the RDF-family of languages; on top, ASMs require only rules to represent state change, and rules have been proposed for RDF data processing7,8 In our operational semantics derived from ASM semantics, the execution of rule-based programs (user agents) leads to a series of HTTP requests.
Our contributions are as follows: • We provide a formal account of the standards around Linked Data in combination with Abstract State Machines (ASMs). With the synthesis between Linked Data, which provides a way to represent and manipulate resource state, and ASMs, which provides operational semantics based on rules and stepwise execution of these rules, we are able to specify user
agent behaviour with the entire user agent state maintained in RDF on web-accessible resources. • We present a syntax for a rule language (based on Notation37, a superset of the RDF Turtle language) to define conditions that trigger updates based on HTTP state manipulation operations. We give an operational semantics of the language based on the ASM execution semantics. • We conduct an evaluation of a prototype rule processing system in a Smart Buildings scenario and show the applicability of the approach.
The paper is structured as follows: we start in Section 2 with an introduction to a Smart Building scenario, in which we set the examples and the evaluation. We continue in Section 3 with basic definitions of Linked Data and ASMs. In Section 4, we propose a synthesis on the level of state representation (interpretations) in ASMs and RDF model theory. In Section 5, we present an evaluation using a benchmark and point to successful applications of our approach. In Section 6, we relate our work to the state of the art and in Section 7 we conclude with a summary and an outlook.
Throughout the paper, we use examples from the Smart Building domain, inspired by recent work in Building Management Systems: NIST identified interoperability as a major challenge for the building industry [10]. To raise interoperability in Building Management Systems, Balaji et al. developed Brick [2], an ontology to model buildings and corresponding building management systems.
We use a description of building 3 at IBM Research Dublin in Ireland. Balaji et al. provide a static description of this building using the Brick ontology9. The description covers the building and the building’s parts (e. g. rooms) and the diferent parts of the building’s systems (e. g. lights and switches). As there is nothing to automate in the static description, we introduce dynamics by adding information about the state of these system parts (e. g. on/of) in the form of properties from the SSN ontology10. We serve those properties as writeable Linked Data on localhost.
In the examples, we use our approach to program an user agent that controls one light in the building in a straight-forward fashion (turn the light of if the light is on). In the evaluation, we use more complex control schemes with up to 30 rules and control the lights of the entire building. 2.1
We express rule programs in a subset of the Notation3 (N3) syntax7,
for an example see Figure 1. N3 is a superset of the RDF Turtle
syntax11, hence we can express RDF in N3: In RDF, we use URIs
(Uniform Resource Identifiers 12) as names for resources, for
instance we use the abbreviated13 URI IBM_B3:Lighting_1F_M59
to identify the lights in room 21 on the first floor in wing 42 of
9https://github.com/BuildSysUniformMetadata/GroundTruth/blob/2e48662/
building_instances/IBM_B3.ttl
10http://www.w3.org/TR/vocab-ssn/
11http://www.w3.org/TR/turtle/
12http://www.ietf.org/rfc/rfc3986.txt
13We assume the usual definitions for the prefixes from standardised vocabularies
such as RDF, HTTP, and SSN, which can be found on http://prefix.cc/
building 3. In RDF, we can link resources to each other, thus
forming a graph. For instance, we link said lights to the ssn:Property
http://localhost/Lighting_1F_M59#it (cf. (1) in Figure 1). To
form rules, we use N3’s graph quoting (curly brackets) and
variables (terms starting with question marks). Note that in contrast to
RESTdesc [
We distinguish derivation and request rules. In both types of rules, the body consists of a set of triple patterns (triples with variables, cf. basic graph patterns (BGPs) in SPARQL14). In a derivation rule, the head also consists of a set of triple patterns (cf. (2) in Figure 1, which defines the inverse to ssn:hasProperty). Derivation rules are not in the focus of the paper, but are important when layering higher-level entailment regimes on top of the work presented in this paper. Here, we use the Simple Interpretation. In a request rule, the head specifies an HTTP request. The request specification includes an HTTP method, a request URI, and optionally a set of triple patterns to form the HTTP body (cf. Figure 1, where (3) dereferences an end of ssn:isPropertyOf links, and (4) changes the state of ssn:Properties that fulfil a certain condition). @prefix IBM_B3: <http://buildsys.org/ontologies/examples/IBM_B3#> . @prefix brick: <http://buildsys.org/ontologies/Brick#> . # (1) Language feature: RDF: IBM_B3:Lighting_1F_M59 a brick:Lighting ;
ssn:hasProperty <http://localhost/Lighting_1F_M59#it> . # (2) Language feature: Derivations: { ?thing ssn:hasProperty ?property . } => { ?property ssn:isPropertyOf ?thing . } . # Language feature: Conditional requests: ## (3) Defining how to retrieve world state (GET requests): { ?y ssn:isPropertyOf ?x . } => { [] http:mthd httpm:GET ; http:requestURI ?y . } . ## (4) Defining the logic (PUT, POST, DELETE requests): { ?light a brick:Lighting .
?property a ssn:Property ; foaf:primaryTopicOf ?ir ;
ssn:isPropertyOf ?light ; rdf:value "off" . } => { [] http:mthd httpm:PUT ; http:requestURI ?ir ; http:body
{ ?property a ssn:Property ; rdf:value "on" . } . } .
We informally give the operational semantics for the rule language by describing how an interpreter would execute the program in Figure 1: An interpreter evaluates the triple patterns of the body of the rules on RDF data that is either given initially (1) or downloaded as mandated by request rules with GET requests (3). Meanwhile, the interpreter adds data as mandated by derivation rules (2). The interpreter executes derivations and GET requests until it calculated the fixpoint. Last, the interpreter executes the PUT, POST, DELETE requests of all request rules whose body holds in the data (4). The 14http://www.w3.org/TR/sparql11-query/ interpreter operates in a looped fashion. The rationale behind this operational semantics is the subject of the paper. 3
In this section, we give foundational definitions of the technologies around Linked Data with a special focus on the aspects relevant to our proposed synthesis with Abstract State Machines, whose basic definitions form the rest of this section.
We assume a basic knowledge of the technologies Linked Data is built on: Uniform Resource Identifiers (URIs) 12 for identifying things, the Hypertext Transfer Protocol (HTTP)5 for interacting with things, and the Resource Description Framework (RDF)1 for static descriptions of things. As the technologies are about the transfer and the description of state information, we first discuss the relations of diferent kinds of state (e. g. world and resource state). Next, we go beyond the basics of HTTP and refresh the reader’s knowledge of the semantics of diferent HTTP requests and responses. The HTTP semantics are an important building block in our formalisation. Next, we refresh the reader’s knowledge of basic RDF model theory. We use model-theoretic semantics to describe static aspects in our formalisation. Subsequently, we outline a relation between Linked Data and the semantics of an RDF Dataset, which we need for our formalisation when it comes to the relation between a source of data and the data itself. Last, we introduce Abstract State Machines (ASMs), on which we base our formalisation of dynamic aspects. If two approaches use the same term, we introduce subscripts for the origin (·rdf vs. ·asm). 3.1
We distinguish diferent kinds of state: When successfully retrieving state using HTTP GET from a URI, we obtain a description the resource’s state, e. g. the light in a room. The corresponding HTTP request’s state can e. g. be “successful”. We call the union of the state information about all resources world state, i. e. all resources in the world. An application (e. g. implemented as rule program) can maintain state (e. g. in writeable resources), which then represents the application’s state, e. g. a note that something just happened. The application state is a subset of the world state. ASM terminology uses the term system state, which can be translated to our terminology as the subset of the world state that is relevant for an application, e. g. the building description and the weather report. 3.2
The Hypertext Transfer Protocol (HTTP) is a protocol to interact with a resource (called the target) in a request/response fashion5. In the spirit of Read-Write Linked Data, we consider the request methods that implement CRUD15: GET, PUT, POST, DELETE.
As our formalisation is based on world state, we only consider (of the responses to HTTP requests with diferent methods) the responses to successful HTTP GET requests: • We assume the responses to unsuccessful HTTP requests to be empty: The response to an unsuccessful HTTP request against a target does not contain information about the target, but on the request16. 15The basic operations of persistent storage: Create, Read, Update, Delete 16http://www.ietf.org/rfc/rfc7231.txt • We also consider the responses to successful HTTP PUT, POST, DELETE requests as empty, as they may be empty or carry no information about the state of resources6,16.
We now turn to the individual HTTP request methods and summarise their semantics16. For legibility, we neglect redirects in this paper. We sketch in Section 4.2 how they can be re-introduced.
The GET request is a means to retrieve state information about the request target. For instance, we can find out whether the lights are on or not in said room 21 using a GET request to http:// localhost/Lighting_1F_M59#it. By contract, the GET request is considered safe, i. e. a GET request must not change state.
The PUT request is a means to overwrite the state information at the request target. For instance, we can set the lights to be on in said room 21 using a PUT request to http://localhost/Lighting_ 1F_M59#it. For the formalisation in this paper, we assume all targets that we want to write to, to be writeable.
The POST request is a means to e. g. append a resource described in the body to a collection or to send data to a data handling process. In this paper, we restrict ourselves to the former.
The DELETE request is a means to delete the request target. For our considerations, we regard a DELETE request as a PUT request with an empty message body. 3.3
We use the graph-based data model Resource Description Framework (RDF) to describe things and their relations1. In an RDF Graph, typed connections between resources are stated in the form of triples, e. g. (1) in Figure 1, which relates a light to a ssn:Property. An RDF Graph is defined follows:
Definition 1 (RDF Graph, Triple). Let U, B, L be the respective sets of all URIs, Blank Nodes and Literals. The set of all RDF triples T is then defined as follows: T = U ∪ B × U × U ∪ B ∪ L. An RDF Graph G is a set of triples: G = {t |t ∈ T }.
The RDF standard uses model theory to specify the meaning of an RDF Graph (e. g. that the URI for the light is interpreted as the resource that represents the light). We paraphrase the definitions as they are given in the corresponding W3C Recommendation17.
Definition 2 (InterpretationRDF, name, vocabularyRDF, universe). An interpretation is defined as a mapping from U and L into some set called the universe. Both the mapping and the set can be constrained. A name is an element from the union U ∪ L. A set of names is also called vocabulary.
The basic interpretation for an RDF Graph is the simple interpretation. The simple interpretation defines the following mappings and constraints:
Definition 3 (Simple interpretation, extension). A simple interpretation is defined using the following sets and mappings: IR and IP denote the subsets of the universe that contain all resources and properties respectively. IEXT(p), called the extension of a property p, is a mapping IP → 2IR×IR that maps p to all pairs in IR that are connected by p. IS is a mapping U → IR ∪ IP. IL is a partial mapping L → IR. 17http://www.w3.org/TR/rdf11-mt/
To not to have to specifically address Blank Nodes, we assume ground RDF Graphs in this paper. The extension to Blank Nodes should be straight-forward. 3.4
To talk about RDF data from diferent sources, we use the notion of an RDF Dataset. An RDF Dataset1 is a collection of RDF Graphs. Each RDF Graph in an RDF Dataset is identified using a name, which can be a URI, a Blank Node, or empty. The RDF Graph with the empty name is called the default graph. For legibility, we denote the default graph with default in this paper.
While the RDF specification does not impose restrictions on the relation between the graph name and the RDF Graph in the RDF Dataset, we use the semantics defined in Section 3.5 of 18 as abstraction of Linked Data: The graph names are URIs and the RDF Graph with a given name in the RDF Dataset is the graph that can be obtained using an HTTP GET request with the graph name as target. If the request to a graph name fails or returns no RDF data, the RDF Graph is empty. In the evaluation, we contrast two ways of constructing the RDF Dataset about the current system state: Using download of a dump (D1), or following links (D2). 3.5 For the dynamic aspects of our approach, we use Abstract State Machines (ASMs). Concretely, ASMs help us to define how to evolve Linked Data, which we interpret as RDF Dataset. Here, we give the standard definitions for ASMs to make the paper self-contained. The approach of ASMs has been developed towards the end of the 1980s with the aim to bridge between the specification and computation of programs [11]. ASMs are meant to improve on Turing’s thesis. Turing Machines have proven too low-level to specify algorithms larger than toy examples. In ASMs however, the level of abstraction can be adapted to the requirements of the use-case. ASMs have been extensively used to give operational semantics to programming languages including C, Prolog, and Java19.
An ASM consists of an algebraic first-order structure and a set of transition rules on how to modify the structure. In the following, we give the basic definitions for ASMs.
Definition 4 (VocabularyASM, function name, relation name, characteristic function name, variable, term). The vocabulary ϒ be defined as a finite set of function names and their arity n ≥ 0. The vocabulary also contains the nullary function names undef, and the boolean constants true and false. Moreover, the vocabulary contains the usual boolean operators as functions. Relation names and characteristic function names are special function names. Terms can be defined recursively: Variables are terms. If f is an r -ary function and t1, . . . , tn are terms, then f (t1, . . . , tn ) is a term.
For the presentation in this paper, we characterise a function name with arity > 0 with their correctly sized argument list, e. g. to talk about an RDF Dataset for Linked Data, we define quad(·, ·, ·, ·), which defines the function name quad with an arity of 4. We omit the argument list for nullary function names. 18http://www.w3.org/TR/rdf11-datasets/ 19See the annotated ASM bibliography at http://web.eecs.umich.edu/gasm/ index.html
Definition 5 (Super-universe, function, relation, characteristic function). The super-universe X is a non-empty set. X contains e. g. all functions X n → X , true, false, and undef. The boolean functions behave the usual way on {true, false}. Relations are functions that map X n → {true, false}. A characteristic function for a set is a function X → {true, false} that maps to true if the operand belongs to the set.
Definition 6 (InterpretationASM, transition rule, function update, static and dynamic function). An interpretation I : ϒ → X maps the terms from an ASM vocabulary to a superuniverse. A transition rule R is a function update, e. g. f (t1, . . . , tn ) := t0, or a guarded function update, which has a boolean condition, e. g. if condition then function update(s). A function update changes the interpretation of a function name at given arguments. A static function is not subject to change by the function updates of an ASM, as opposed to a dynamic function.
Definition 7 (Value and evaluated form). The value of a term from the vocabulary ϒ is the term’s referent in the super-universe X under the current interpretation I. We denote the referent of a term t under an interpretation I using eval(t , I). If t is a tuple, we have: eval(t , I) := (eval(t1, I), . . . , eval(tn , I)). If t is a function, we have: eval(f (t1, . . . , tn ), I) := eval(f , I)(eval (t1, I), . . . , eval (tn , I))).A function update in its so-called evaluated form is eval(f (t1, . . . , tn ) := t0, I) = f (eval (t1, I), . . . , eval (tn , I))) := eval(t0, I).
Definition 8 (Algebra, state, run, step). A (static) algebra or state is a triple of a vocabulary, a super-universe, and an interpretation. A step is a transition from one state to the next by the means of firing transition rules. A run is a sequence of steps.
The transition rules to be fired in one step are composed in an update set.
Definition 9 (Update set). The update set to be fired in an interpretation I under the transition rule set T can be defined as updates(I, T ) := {eval(u, I)|u ∈ T ∧(the condition of u holds in I ∨ u has no condition)}
In ASM, we assume discrete time. Time progresses from one state to the next, i. e. in a run, there is an ordered sequence of system states. There may be multiple transition rules that fire in one state. If multiple transition rules want to update the interpretation of a function name for the same arguments, then the system halts because of the conflict.
Definition 10 (Abstract State Machine). An Abstract State Machine (ASM) can be defined as a quadruple of a vocabulary, a super-universe, an interpretation for time t0, and a set of transition rules: ASM := (ϒ, X , I0, T )
We now introduce variables to be able to range over names in conditions and updates. In ASM, we have to state from which set of individuals those individuals are to take that are to be bound to variables. Therefore, a variable declaration is of the following form:
Formally, the variables can be covered by the help of an auxiliary vocabulary that contains the variables as nullary function names [11]. 4
This section is about our proposed synthesis of ASM, and Linked Data + Rules with the help of RDF model theory and HTTP semantics. We first describe on a high level the commonalities between ASM and RDF model theory, which motivate our synthesis, and then the diferent foci of both approaches. After that, we provide a synthesis of ASM and Linked Data + Rules. While the formalisation has the user agent in the focus, which regards Linked Data as external functions, we next sketch how a server fits into the picture. Then, we sketch how the synthesis can be used for specifying computation. Subsequently, we use the synthesis to give semantics to a rule language and discuss our findings. Last, we derive requirements for a Linked Data user agent specification language. 4.1
While both, ASMs and RDF are defined in terms of interpretations of vocabularies into a (super-)universe, the focus of both approaches is diferent: RDF model theory is about whether diferent RDF Graphs entail each other or whether models can exist for an RDF Graph. Therefore, conditions on the universe are in the focus. The interpretation is static in RDF model theory. ASMs are all about the evolution of system state, which manifests itself in the evolution of the interpretation of a vocabulary into a super-universe. Therefore, the transition function T is in the focus, in which updates to the interpretation are stated and the conditions under which the updates happen. Linked Data is about the publication and the updating of RDF data on the web using HTTP, where the RDF describes the state of a resource.
The high-level idea of the synthesis, which is described in the subsections of Section 4.2, is to (1) define RDF model theory for Linked Data using RDF Datasets, (2) define ASM functions statement(·, ·, ·) and quad(·, ·, ·, ·) for Linked Data/RDF Datasets and the functions’ interpretations, (3) define an ASM transition function for Linked Data/RDF Datasets using rules with HTTP requests in the head (4) define how the ASM evaluation of the statement(·, ·, ·) function and the ASM updates to the quad(·, ·, ·, ·) function can be done in accordance with the semantics of HTTP requests, and (5) use above definitions in the definition of an ASM. 4.2
In this section, we take the definitions from the simple interpretation from RDF model theory and use them, slightly amended for RDF Datasets, in the definition of an ASM. The synthesis allows us to specify the evolution of an RDF Dataset using ASM semantics. Note that the terms vocabulary and interpretation used in ASM and RDF model theory mean the same. The term universe in RDF maps to the term super-universe in ASM.
4.2.1 Define RDF model theory for Linked Data using RDF Datasets. We base our considerations on two semantics for RDF Datasets that have been discussed in Sections 3.2 and 3.5 of a note of the W3C RDF Working Group18.
We start out with definitions to simplify our presentation: Like the W3C Recommendation on model-theoretic semantics for RDF17, we use as vocabulary the infinite sets of all URIs U and Literals L in our definitions, in contrast to the fixed vocabulary used by the Linked Data sources under consideration. Correspondingly, IS and IL interpret all U and L, and IR has corresponding elements. We point to17 for how to amend the definitions to finite vocabularies. To further ease the presentation, we assume ground graphs. Moreover, be IP = IR, such that we only need to address IEXT in our considerations. When working with RDF Datasets, we assume that the same elements of the vocabularies of the diferent graphs have the same referent when interpreted using IS and IL. We do not consider redirects in the definitions, although they can be layered on top by defining a function for the correspondence between a non-information resource and an information resource. In the definitions, we also assume all Linked Data sources to be in N , the named graphs of our RDF Dataset, i. e. we assume webcompleteness in the terminology of [15]. By restricting N , we can implement other completeness classes.
Of the W3C RDF WG Note on RDF Dataset semantics18, two sections are of particular use for our considerations: 3.5 “Named graph are in a particular relationship with what the graph name dereferences to” defines an interpretation for each graph in the RDF Dataset, hence we can define an extension function per dereferenceable source
IEXT c := Extension function of the graph available at c 3.2 “Default graph as union or as merge” defines the default graph of an RDF Dataset as RDF union or merge of all named graphs in the RDF Dataset. As we assume ground graphs, there is no diference in RDF union or merge. Hence, we can define the extension function of the union as:
IEXT union(p) := Ø IEXT c (p) c ∈N The default graph can be regarded as knowledge of the client, e. g. knowledge that is not available at any n ∈ N . The default graph can also be used in the case of higher-level entailment regimes for stating axiomatic triples in case they cannot be dereferenced from a Linked Data source.
4.2.2 Define ASM functions quad(·, ·, ·, ·) and statement(·, ·, ·) for Linked Data/RDF Datasets and the functions’ interpretations. We define
quad(s, p, o, c) : IR × IR × IR × N → {true, undef}
as the characteristic ASM function for IEXT c . Moreover, be
statement(s, p, o) : IR × IR × IR → {true, undef}
the characteristic ASM function for IEXT union. The statement
function has also been used in [
So far, we have defined Linked Data as static ASM functions. Now, we proceed by introducing dynamics.
4.2.3 Define how the ASM transition function for Linked Data/RDF Datasets can be stated. The rules can be given as usual in ASM in rules of the form if condition then update(s) modifying the interpretations of function names. We use conjunctions of the statement(·, ·, ·) function for the conditions (reflecting BGP queries from SPARQL14) and the conjunctions of the quad(·, ·, ·, ·) function for the updates. Both the conditions and updates can contain variables. 4.2.4 Define how the ASM evaluation of the statement(·, ·, ·) function and the ASM updates to the quad(·, ·, ·, ·) function can be done in accordance with the semantics of HTTP requests. For the evaluation of the conditions, we consider the statement(·, ·, ·) function as making HTTP GET requests to all n ∈ N and to evaluate statement(·, ·, ·) like an external function in ASM. For the default graph, no request needs to be made. The updates are done using the quad(·, ·, ·, ·) function, which takes an additional c as parameter. The updates correspond to HTTP PUT, POST, DELETE requests.
We perform the requests ordered in accordance with ASM steps, i. e. we first evaluate all HTTP GET requests, and collect the updates that are mandated by the transition functions. After we collected the updates to be performed, we carry out the corresponding requests in bulk, i. e. multiple HTTP PUT, POST, DELETE requests at a time. After all updates in the form of HTTP PUT, POST, DELETE requests have been performed, we continue with the next ASM step. The result of the HTTP PUT, POST, DELETE requests is dependent on server implementations, see Section 4.3.
4.2.5 Define the ASM. We define the ASM for Linked Data as:
ASM := (ϒ, X , I0,T ) The vocabulary ϒ contains all RDF names (all URIs and Literals), the boolean operator ∧, and constant names. We omit (1) the boolean name false and the boolean operator ¬ because of the open world assumption, which is typically made on the Semantic Web20, and (2) the operator ∨, because in a BGP, conditions are only connected using conjunctions. Disjunctions can be stated by using multiple rules. We add the function names statement and quad: ϒ := U ∪ L ∪ {true, undef} ∪ {∧} ∪ {quad, statement} The super-universe X is a set that contains elements for all RDF Graphs, and functions X n → X including the boolean and. To be able to visually tell the elements of ϒ and X from each other, we use typewriter font for the nullary function names and small caps for their counterparts in the super-universe.
X := IR ∪ IP ∪ {true, undef} ∪ { f | f : X n → X } The interpretation It of an element y of the vocabulary ϒ at time t , consists of IS(·) and IL(·) from RDF model-theoretic semantics for the RDF names, mappings for the boolean true, and undef, and functions for quad(·, ·, ·, ·) and statement(·, ·, ·), and ∧: IS(y) if y ∈ U IL(y) if y ∈ L It (y) := true if y = true undef if y = undef ∈ { f | f : X n → X } if y ∈ {quad, statement, ∧} 4.3
Although our formalisation is made for the user agent, we show for completeness the server behaviour, which reflects the update of the quad(·, ·, ·, ·) function for PUT, POST, and DELETE requests: A server processing a PUT request to the target information resource http://localhost/Lighting_1F_M59 with the body <http://localhost/Lighting_1F_M59#it> rdf:value "on". 20http://www.w3.org/TR/owl2-primer/ sets to true for the argument
quad(·, ·, ·, http://localhost/Lighting_1F_M59) (<http://localhost/Lighting_1F_M59#it>, rdf:value, "on") and undef for all other triples. A server processing a POST request with the target of a LDP container, e. g. http://localhost/ldbbc/ and the RDF payload payl first determines a new URI sub that is subordinate to the container resource, then defines a new graph by relativising all URIs in the payl against sub and PUTs the new graph at sub into the RDF Dataset. Moreover, a membership triple for sub is added to the representation of the container resource. 4.4
In this section, we give operational semantics to our conditionaction rule language using the synthesis. We use the program in Figure 1 as example: The program consists of RDF (1), derivations (2), and requests (3+4), the latter to interact with the environment. Remember that in an ASM step, updates are executed after the update set has been constructed entirely. To construct the update set, all rules have to be evaluated on the current state.
In our language, information about the current system state is given by RDF, by evaluating all derivations, and by evaluating all GET requests on the Linked Data sources until the fixpoint has been calculated. In our example, we know from the RDF (1) that the light IBM_B3:Lighting_1F_M59 has the ssn:Property http: //localhost/Lighting_1FM59#it. The derivation rule (2) adds the inverse link to the knowledge. With the inverse information available, the conditional GET request is triggered (3). The data obtained using the GET request is added to the knowledge, e. g. that the light is of. No further knowledge can be derived using rules, so the fixpoint is calculated. The updates in our language are the unsafe requests. The conditional PUT, POST, DELETE requests (4) are collected during the information gathering about the current state, and are executed after the fixpoint calculation. Note that using conditional requests, we can do hypermedia-style link following. In our example, the condition for the last rule holds in the knowledge after the fixpoint calculation. Hence, the light is turned on.
To execute programs in our language along the ASM step semantics, an interpreter operates in nested loops (see Figure 2 for its algorithm). The algorithm takes as input a rule program and emits a sequence of sets of safe and unsafe requests, depending on the available state information. Note that ASM steps in combination with GET requests implement polling. 4.5
ASMs are a model of computation, i. e. one can specify arbitrary computation using the model, e. g. algorithms and programs. In the previous section, we defined an ASM view on Linked Data. Hence, we now can specify arbitrary computation with the state of the computation represented in Linked Data. Our ASM-based formalisation of Linked Data is based on the assumption that we have exclusive read and write access to all relevant URIs during Require: assertions ▷ Triples to be asserted in every ASM step Require: rules ▷ Derivation and request rules var unsafeRequests: set<request> var data, oldData: set<triple> var fixpointReached: boolean while true do ▷ Loop of the ASM steps unsafeRequests.clear() data.clear() data.add(assertions) repeat ▷ Loop for determining the update set ifxpointReached <- true for rule : rules do if rule.matches(data) then ▷ Also empty rule bodies oldData = data.copy() if rule.type==derivation then
data.add(rule.match(data).data) else ▷ So the rule must be an interaction rule if rule.match(data).request.type==GET then
data.add(rule.match(data).request.execute())
else
an ASM step. When generalising to a setting with multiple agents,
ASMs typically assume circulating exclusive access to the system
state. As there is no central control in a web setting, we cannot
circulate the access right. Thus, there is no general solution to the
problem of concurrent access, but a number of remedies: (1) in
a realistic setting, we do not have the entire Linked Data in our
system state (i. e. web-completeness in the terminology of [15]),
but a considerably smaller subset. (2) on the web, most access is
typically reading, and only little is writing [
Using our ASM view on Linked Data, we can also implement
simple reflex agents for Linked Data, the simplest agent type in
Russell and Norvig [
What current languages to specify queries and updates are missing is a way of expressing the transition function T . In ASM, T is given using rules in the form if condition then function update(s). T is then executed in ASM steps. Thus, we need a language (1) that allows to express conditions on state information (2) that allows to define updates that send state information, (3) whose semantics adhere to ASM steps, i. e. one repeatedly ifrst evaluates all conditions of all rules and collects all updates, and then one evaluates all updates in bulk.
We chose N3 as rule language in the context of RDF data and gave
ASM-based semantics to N3. Other approaches including SPARQL
updates22 or RUL [
To describe our evaluation, we start out with defining the data and diferent scenarios for data access. Next, we present diferent workloads. Then, we describe experimental setup. Next, we present and discuss our results. Last, we showcase applications of our approach. 5.1
We evaluate our approach in the building automation setting of Section 2. We use the building’s lighting subsystem, as lamps and switches can be regarded as having a discrete state. We use building 39, as the building’s description includes a lighting subsystem.
The core classes of the Brick ontology are depicted in Figure 3. The first part of the ontology, Location and subclasses, allows for describing a building in terms of the subdivisions provided by the brickwork, e. g. floors and rooms. The second part of the ontology, Equipment and subclasses, allows for describing diferent systems that run the building, where we focus on the lighting system in this paper. Other systems include water, and HVAC (heating, ventilation, and air conditioning). The third part of the ontology, Point and subclasses, allow to talk about sensors and actuators in the building.
Building 3 is box-shaped with its long side oriented from north to south. In the RDF description, the building is subdivided into lfoors and wings. The rooms are assigned to their corresponding lfoor and wing (also has-part relationships). The lights are directly assigned to rooms or wings. A light system can consist in (1) an occupancy sensor that determines whether there are people in its vicinity, (2) a luminance command, in other words, a switch to control the lights, and (3) a luminance sensor that we consider to be triggered by daylight. We provide basic statistics in Table 1.
We bring the static building description “to life” by adding ssn: hasProperty links to dynamic Linked Data resources on localhost representing switches, occupancy sensors, luminance sensors, and lights. The state of each resource relevant for the evaluation is on/of for the lights, and a numeric value for the luminance sensors. 22http://www.w3.org/TR/sparql11-update/ :Location :Equipment :Point :Building :Floor :HVAC_Zone :Lighting_Zone :Room :Fire_Safety_System :HVAC :Lighting_System :Water_System :Alarm :Command :Sensor :Setpoint :Status
We use the engine Linked Data-Fu version 0.9.1223 to run the rule programs. We use LDBBC version 0.0.624 as LDP Container to serve the static building data. We implement the following dynamic sources: (1) an RDF weather API built from a sample file from OpenWeatherMap25, a JSON-LD context, and a sunset/sunrise simulation for Dublin, and (2) luminance sensor readings according to time of day and season. We run the experiments on a laptop with an Intel Core i7-5600U CPU, 12 GB of RAM, and Ubuntu Linux 17.04. After the dynamic sources simulated one year, i. e. one minute in wallclock time, we stop one experiment leading to repetition counts of up to 7’500 depending on the runtime of one ASM step. The evaluation system including data and rules can be found online26. 5.4
We present the results for D1 in Table 2 and for D2 in Table 3. We report median values as due to firing many requests, there are 23http://linked-data-fu.github.io/ 24http://github.com/kaefer3000/ldbbc/ 25http://www.openweathermap.org/ 26http://github.com/kaefer3000/rwld-brick-benchmark/ high outliers in the 99 % percentile, which spoil mean and standard deviation. The median, however, is stable. The order of magnitude of the measurements in varies in Table 3, in contrast to Table 2. This is owed to the fact that each ASM step, regardless of the data that is actually needed, the whole building description has to be transferred in D1, which is 2.3 MB per transfer. Compared to that, the link following approach D2 can access the building data as required. This fine granularity comes at the price of additional requests, which make the processing of the whole building more expensive. The drop in time between W2 and W3 can be explained by the reasoning that is employed in W2 to check whether the current day and hour is a working hour, which is not needed in W3. The increase between W3 and W4 underestimates the real cost of the computations, as we go from all lights in W3 to only those lights with sensors in W4, cf. Table 1. The drop between W4 to W5 can be explained by the smaller number of lights with luminance sensors. The rise in time for the workloads in Table 2 is due to that diferent workloads need to access diferent amounts of data. 5.5
In this section, we give examples of how we applied our approach.
our approach to connect diferent parts of Virtual Reality systems: In the i-VISION project, we connected a flight simulator to a workflow analysis software [22] (ca. 90 rules). In a demo [24], we connected a Microsoft Kinect sensor and APIs from the Web to a 3D engine (ca. 60 rules), where the interpreter running the rules performed about 30 ASM steps per second (i. e. the refresh rate of the Kinect sensor).
applications of ASMs to define the operational semantics of programming languages, we currently work on defining the operational semantics of a workflow language using our approach (ca. 30 rules).
Turing-Completeness To show the expressiveness of our approach, we implemented a Turing Machine using Linked Data and four rules. The rules together with instructions for the set-up can be found online27. While the Turing-completeness is, of course, an inherent property of the ASM part of the approach, it persists despite the restrictions we imposed to make ASM fit Linked Data. All parts of our approach are necessary: Read-Write Linked Data for tape and machine state, and request rules executed in ASM steps. 6
In this section, we discuss related work subdivided by topic.
agement, people studied updates to RDF Graphs, e. g.
schemapreserving updates [
Automation on the web Unlike automation systems such as
[
Descriptive works We monitored [23], analysed [20], and formally described [14] the dynamics of Linked Data. Those works are insuficient to specify computation.
Web Service descriptions A focus of Semantic Web Services
are service descriptions and the processing of such descriptions,
with some work on operational semantics [1], [
in a Semantic Web Services fashion have gained traction again,
especially on the Internet of Things [7], and even when working with
HTTP [
advent of RDF and Linked Data, the authors of [
of [19] executed queries in linear temporal logic (LTL) over evolving ontologies, which is complementary to our approach. Similar to our work, the author of [25] combined approaches for static and dynamic modelling for object-oriented modelling. While Graph Rewriting could serve as an alternative to ASM for the specification of the evolution of RDF Graphs, we think ASM is more compatible to the Semantic Web stack, as both are based on first-order logic. 28http://ifttt.com/ 29http://arktik.io/
We have presented a formal approach for capturing the dynamics of Linked Data with the aim of specifying user agents. To this end, we gave a synthesis of RDF model theory, ASMs, and HTTP, and described requirements for implementing the synthesis. We applied the approach to give semantics to a rule language such that we can specify Linked Data user agents. We presented application scenarios and showed our approach to be Turing complete (Section 5.5). We evaluated our approach in a Smart Building setting.
In the paper, we took the first step towards autonomous agents that operate on Linked Data: We presented a formal basis for the execution of agents. Still, there are more steps to take, a formal notion of (1) internal state in the agent, and (2) a notion of goals and capabilities, which we will address in future work.
Yet, we believe our work can already be applied today: Although
experts built the applications in Section 5, the experiments of van
Kleek et al. [
We thank Armin Haller for insights into ASMs in WSMO. This work is partially supported by the German federal ministry for education and research in AFAP, a Software Campus project (FKZ 01IS12051).