triple spaces

Definition of triple spaces

A triple space is a RDF graph stored in a shared memory location, that can be
accessed concurrently by any number of agents manipulating the triples in the graph.

Besides being a mean to store and manipulate semantic meta data, triple spaces
also offer coordination mechanisms among agents thanks to a small set of
operations over the triple space with well defined semantics. Origins of this formalism can be traced to the original Linda system created
by David Gelernter and the blackboard AI systems.

Some of the benefits of the coordination mechanism offered by this kind of
systems can be summarized as follows:

  • generality: different kind of distributed model can be implemented on top of it
  • orthogonality: provided by a small set of triple space operations
  • greater decoupling among agents

clj-plaza tries to offer an implementation of this computational model
accessible from Clojure applications.

Creation of triple spaces

The triple space model can be implemented in different ways and supports
different kinds of distribution, for example, in a single JVM or across different JVM nodes.
Applications built using clj-plaza can be ported to these different
distribution architectures just choosing a different kind of triple space without
changing the code of the application.

Currently, two implementations of triple spaces are supported: a
BasicTripleSpace that can be used by agents inside a single JVM or
a RemoteTripleSpace that can be used by agents in different JVMs.

The creation of a BasicTripleSapce can be achieved using the
following Clojure code:

(use 'plaza.triple-spaces.core)
(def-ts :test (make-basic-triple-space))

We have declared a new triple space and we have assigned it the name
:test.
If we would like to access the triple space, we can use the function
ts passing the name of the triple space as an argument:

(ts :test)
; output -> #<BasicTripleSpace plaza.triple-spaces.core.BasicTripleSpace@72433b8a>

Once the triple space has been created, it can be shared among the different agents
performing the computation. These agents can issue a set of operations that
modify the RDF graph stored in the triple space:

  • out: store triples in the triple store
  • rd: copy and returns triples stored in the triple store matching a pattern
  • in: removes and returns triples stored in the triple store matching a pattern
  • swap: replaces some triples matching a pattern by a new set of triples in a single atomic operation
  • rdb: blocking version of the rd operation
  • inb: blocking version of the in operation
  • notify: the agent receives a notification each time another agent tries to insert or remove triples from the triple space matching a pattern

The out operation

The out operation allows an agent to add new triples to a triple space. This
operation can be issued from Clojure using the function out
and a clj-plaza RDF triple set:

(out (ts :test) [[:a :b :c][:a :size (d 520)]])

The operation returns the triples just inserted in the triple space.
If an agent tries to insert the same triples again in the triple space, no new triples
will be inserted. The out operation is idempotent. Triples cannot be duplicated in the triple space.

The rd operation

The rd operation returns a list of triple sets built with the triples stored
in the triple space that match a particular pattern, described using clj-plaza
SPARQL patterns:

(out (ts :test) [[:a :b :c][:a :size (d 520)]])
(rd (ts :test) [[:a :b ?o][:a :size ?n]])
;([[#<PlazaResource http://plaza.org/ontologies/a>
;   #<PlazaResource http://plaza.org/ontologies/size>
;   #<PlazaTypedLiteral "520"^^<http://www.w3.org/2001/XMLSchema#int>>]
;  [#<PlazaResource http://plaza.org/ontologies/a>
;   #<PlazaResource http://plaza.org/ontologies/b>
;   #<PlazaResource http://plaza.org/ontologies/c>]])

In this example only one triple set matches the pattern, so a list with just one
element is returned, if more than one triple set matches the pattern, they will
be returned as different elements in the list:

(rd (ts :test) [[?s ?p ?o]])
;([[#<PlazaResource http://plaza.org/ontologies/a>
;   #<PlazaResource http://plaza.org/ontologies/size>
;   #<PlazaTypedLiteral "520"^^<http://www.w3.org/2001/XMLSchema#int>>]]
; [[#<PlazaResource http://plaza.org/ontologies/a>
;   #<PlazaResource http://plaza.org/ontologies/b>
;   #<PlazaResource http://plaza.org/ontologies/c>]])
(count (rd (ts :test) [[?s ?p ?o]]))
;; 2

The in operation

The in operation accepts a pattern as the argument and returns matching
triple sets from the triple space, removing these triples from the space:

(out (ts :test) [[:a :b :c][:a :size (d 520)]])
(in (ts :test) [[?s ?p ?o]])
;([[#<PlazaResource http://plaza.org/ontologies/a>
;   #<PlazaResource http://plaza.org/ontologies/size>
;   #<PlazaTypedLiteral "520"^^<http://www.w3.org/2001/XMLSchema#int>>]]
; [[#<PlazaResource http://plaza.org/ontologies/a>
;   #<PlazaResource http://plaza.org/ontologies/b>
;   #<PlazaResource http://plaza.org/ontologies/c>]])
(in (ts :test) [[?s ?p ?o]])
;; ()

If no triple matches the provided pattern, the in operation returns the empty
list.

The swap operation

The swap operation is combination of the in and conditional out operation
in a single atomic operation.
It accepts a pattern and a triple set, and tries to match the pattern in the
triple space and, in the case of any matches, removes the triple from the triple
space and inserts the provided triple set.

(out (ts :test) [[:a :b :c][:a :size (d 520)]])
(swap (ts :test) [[?s ?p ?o]] [[:e :f :g]])
;([[#<PlazaResource http://plaza.org/ontologies/a>
;   #<PlazaResource http://plaza.org/ontologies/size>
;   #<PlazaTypedLiteral "520"^^<http://www.w3.org/2001/XMLSchema#int>>]
;  [#<PlazaResource http://plaza.org/ontologies/a>
;   #<PlazaResource http://plaza.org/ontologies/b>
;   #<PlazaResource http://plaza.org/ontologies/c>]])
(rd (ts :test) [[?s ?p ?o]])
;([[#<PlazaResource http://plaza.org/ontologies/e>
;   #<PlazaResource http://plaza.org/ontologies/f>
;   #<PlazaResource http://plaza.org/ontologies/g>]])

If no triple matches the pattern passed as an argument, no substitution is done:

(swap (ts :test) [[:a ?p ?o]] [[:l :m :n]])
; []

(rd (ts :test) [[?s ?p ?o]])
;([[#<PlazaResource http://plaza.org/ontologies/e>
;   #<PlazaResource http://plaza.org/ontologies/f>
;   #<PlazaResource http://plaza.org/ontologies/g>]])

Blocking operations: rdb, inb

The RDF graph stored in triple space can be used by the agents as a coordination mechanism without
requiring explicit knowledge of the other agents taking part in the
computation.

The blocking versions of the rd and in operations are the basis of this
coordination mechanism. If a process issues a rdb or inb operation to a
triple space, and no triple matches the provided pattern, the agent will block,
suspending its execution until other agent writes triple matching that pattern:

(spawn! (rdb (ts :test) [[:a ?p ?o]]) (println "got some triples (a)"))
(spawn! (rdb (ts :test) [[:a ?p ?o]]) (println "got some triples (b)"))
;; both threads block

(out (ts :test) [[:a :b :c]])
;; both threads unblock
;; got some triples (a)
;; got some triples (b)

The spawn! function can be used to start a new agent whose
execution will start concurrently.

After finishing the execution of triple space processes, a call to shutdown-agents can be used to clean remaining agent threads.

The following diagram shows the three stages happening atomically in the triple
space:

If any agents block with a inb operation, all of them will receive a copy of
the read triples, and all of the triples will be removed from the triple space:

(spawn! (rdb (ts :test) [[:a :b ?o]]) (println "got some triples (a)"))
(spawn! (inb (ts :test) [[:a :c ?o]]) (println "got some triples (b)"))
(spawn! (inb (ts :test) [[:a :d ?o]]) (println "got some triples (c)"))
;; all threads block

(out (ts :test) [[:a :b :c][:a :c :d][:a :d :d]])
;; both threads unblock
;; got some triples (a)
;; got some triples (b)
;; got some triples (c)
(rd (ts :test) [[?s ?p ?o]])
;([[#<PlazaResource http://plaza.org/ontologies/a>
;   #<PlazaResource http://plaza.org/ontologies/b>
;   #<PlazaResource http://plaza.org/ontologies/c>]])

The notify operation

The last operation supported over a triple space is the notify operation. The
notify function implementing this operation receives three
arguments:

  • a notification type
  • a SPARQL pattern
  • an anonymous function

The type parameter signals which kind of operations will generate notifications.
It can have two values: :in and :out for operations
extracting triples from the triple space (in and successful swap operations) and
operations inserting triples in the triple space (out and successful swap
operations).

The pattern passed as an argument will be applied to the triples read or written
in the triple space and a notification will be generated only if the triples
match the pattern.

Finally, the anonymous function will be invoked with the triples read or written
each time a notification is generated:

(spawn! (notify (ts :test) :out [[:a ?p ?o]] #(println "got a notification...")))
;; blocked waiting for notifications

(out (ts :test) [[:a :b :c]])
;; got a notification...
(out (ts :test) [[:a :b :d]])
;; got a notification...

Using filters

Since the patterns passed as argument to the rd, in, rdb, inb, swap
and notify operations are SPARQL patterns, any plaza SPARQL filter can be
applied to the pattern.

All the functions receiving a pattern have a version receiving an additional
list of SPARQL filters that will be applied to the pattern:

(out (ts :test) [[:a :b (d 5)]])
(out (ts :test) [[:a :b (d 10)]])

(rd (ts :test) [[?s ?p ?o]] [(f :> ?o (d 1))])
;([[#<PlazaResource http://plaza.org/ontologies/a>
;   #<PlazaResource http://plaza.org/ontologies/b>
;   #<PlazaTypedLiteral "10"^^<http://www.w3.org/2001/XMLSchema#int>>]]
; [[#<PlazaResource http://plaza.org/ontologies/a>
;   #<PlazaResource http://plaza.org/ontologies/b>
;   #<PlazaTypedLiteral "5"^^<http://www.w3.org/2001/XMLSchema#int>>]])

(rd (ts :test) [[?s ?p ?o]] [(f :> ?o (d 1)) (f :> ?o (d 7))])
;([[#<PlazaResource http://plaza.org/ontologies/a>
;   #<PlazaResource http://plaza.org/ontologies/b>
;   #<PlazaTypedLiteral "10"^^<http://www.w3.org/2001/XMLSchema#int>>]])