LOD initiative has made a major impact on data provision. Thus far, more than 800 datasets have been published, containing tens of billions of RDF triples. The sheer size of data has not resulted in a signi cant increase of data consumption. We contend that a new programming paradigm is necessary to simplify LOD data utilisation. This paper reports an early phase development towards programmable web of LOD data. We propose to tap into a distributed computing environment underpinning the popular statistical toolkit R. Where possible, native R operators and functions are used in our approach so as to lower the learning curve. The crux of our future work lies in the full implementation and evaluation.
As of mid 2013, totally 870 datasets had been published as
part of the Linked Open Data (LOD) cloud, exposing nearly
62 billion RDF triples in a computer-readable representation
format1. These numbers are still rapidly growing largely
attribute to open governmental data initiatives and \online"
high-throughput scienti c instruments. As greater amounts
of data become available through LOD cloud, the expected
virtuous cycle{more data leading to more consumption and
thus encouraged data publication{has not been clearly
witnessed. On the contrary, it is observed that, in many
occasions, after the initial spark of interest and test applications,
data use at many linked data hosting sites declined signi
cantly [
Thus far, data available through LOD Cloud are accessed primarily using SPARQL. Typically, this is conducted by submitting query scripts to a SPARQL endpoint and based on the query results, ltering/joining/aggregating (available from SPARQL 1.1) candidate results either on the server side or at the local clients. SPARQL is based on set algebra. This is both an advantage and a disadvantage. It resembles the prevailing SQL for RDB. People familiar with the latter can, therefore, enjoy a fast learning curve when making the paradigm shift. On the other hand, SPARQL is mainly a query language and thus does not stand-out for post-query data processing. In many cases, the results of SPARQL queries are extracted and converted into the native data structures of other programming languages (e.g. Java) for further manipulation.
Equipping and/or enhancing LOD with high
programmability beyond SPARQL has been investigated previously. The
(dis)similarity between RDF as the underlying data
structure of LOD and the general object oriented methodology
inspired ActiveRDF [
Unfortunately, the above integrations have not lowered the threshold to fully exploring LOD cloud. Among other reasons, the most prominent ones include the follows. It will be very di cult for such approaches to deal with missing values and sparse structures, which abound in uncurated or automatically produced collections. The size and quality of LOD cloud lends itself to statistical data analysis. Performing such analysis using SPARQL queries can become cumbersome in many cases, requiring recursive SPARQL queries and multiple join operations. Moreover, neither SPARQL nor the integrated framework enjoys native support to matrix operations and solving linear equations, while such characteristics become increasingly critical in processing large amounts of data.
R, as a dynamic and functional language, o ers good
capacity to enhance the programmability of LOD and remedy the
shortcoming of existing approaches.
1.2 Why R?
R is a programming language and a software toolkit for data
science. Though not outspoken, R is designed for domain
experts instead of conventional software programmers. It
focuses on transactions that are more familiar to the
former, e.g. organising data, manipulating spreadsheets and
data visualisation. R is open source with over 2,000
packages/libraries for a wide variety of data analytics2. The
most distinctive feature of R is its native support to vector
arithmetics. In addition, versatile graphics and data
visualisation packages as well as easy access to a large number of
specialist machine learning and predictive algorithms make
R a widely adopted computing environment in scienti c
communities (c.f. [
LOD Cloud provides a framework to access and navigate through apparently unrelated data, with conceptual models capable of explicating hidden knowledge. The logic based axioms (underpinning RDF) in many cases are not powerful enough to capture all the regularities in the data. We vision that a programming language, aiming to utilise and interact with LOD cloud (the datasets therein), is preferably to present the following characteristics.
Native support to LOD data structure. The underlying data structure of LOD is RDF triples which essentially compose a directed, labelled graph. SPARQL, the standard RDF querying language, transforms data into tabular form for better alignment with the RDB conventions. This extra formatting layer is not always necessary when the underlying data structure can be accessed with native graph operators. Native support to data analysis. Better data accessibility inherent to LOD presents itself as both an opportunity and a challenge. With better access, an LOD data consumer is exposed to data linked in through semantic relations, most of which he or she may not be aware of. More data is not always necessarily a merit. In this case, the consumer is likely to be overwhelmed by data with di erent formats and di erent semantics, making analysis struggling. A programming platform capable of dynamically handling di erent format becomes desirable.
Ready for distributed processing. Applications accessing LOD Cloud can easily be exposed to billions of triples, tantamount to terabyte-grade data transactions. Single machine and single threaded statistical o erings will nd themselves struggling in such situations. The programming platform should o er parallelisation capacity for good scalability. Inspecting R within the scope of the above requirements, we can make the following observations. Firstly, R is a functional language with lazy evaluation, wherein functions are lifted to become rst class citizen. Also, R has a dynamic type system. These t well with RDF's idiosyncrasy. Secondly, R is designed for statistical computing. Missing value support and sparse matrix handling permeates all R functions and operations. Finally, though R is single-threaded, for many machine learning tasks it is possible to distribute the underlying R data structures and facilitate process distribution over a layer of data abstraction.
The concept of programmable LOD is experimented on the BigGraph platform, denoted as BGR. BigGraph aims at a generic distributed graph storage with RESTful interface. Figure 1 illustrates the main building blocks of BGR. At the top, there is the user interface. An BGR user programs using R primaries with dedicated functions that facilitate the RDF to R data type mapping. BGR programs are submitted to a master node as the main entry point through which the user interacts with the system. The runtime at the master is responsible for the following tasks: 1) interpreting BGR programs; 2) interacting with the in-memory graph model for graph transactions; and 3) deciding which data server/worker it should directly query.
Program (extended R)
Master Node
Graph Model
R System Storage Driver ... ...
R System Storage
Driver N0 ... ...
Nn
In-memory Physical Storage The runtime on each data server mainly consists of two key components: R environment and storage driver. Each local R installation executes statistical analysis directly or exposes such analytical capacity through the in-memory graph model. A storage driver is responsible for I/O with the underlying storage unit.
The fundamental data structure for storing data in R is vector, where a single integer for example is seen as a vector of length one. Variations and extensions of vector data type include matrices, arrays and data frames. Though RDF graphs can be easily stored as adjacency matrices or adjacency lists, we would opt against a full conversion of LOD cloud, adding extra computing expenses. Rather, a direct one-to-one mapping between RDF resources (being classes and instances) and R variables can provide a seamless and smooth integration while at the same time ensures the integrity of the original data. For instance, an RDF instance becomes an R dataframe consisting of single-element vectors. Similarly, an RDF class can be assigned to a two dimensional dataframe with rows corresponding to instances and columns the properties. Instance values can be loaded either column wise or row wise depending on the analytical and performance requirements. In the following example, column-based initialisation is conducted.
P1 P2 ... > s <- data.frame(name=av, age=bv, email=cv) > s age 5 6 name foo john Note that in this example, a class resource is extensionally represented by the set of its instances at the snapshot of data loading.
In order to accommodate the sheer size of LOD Cloud and
leverage parallel data loading, a distributed storage is
necessary. We opt for an edge-based storage solution that ts
nicely with the principles of a Key-Value Store (KVS) [
An RDF triple is indexed three times each. Even though presenting a replication factor of at least three, our approach is under the consideration of query performance and fault recovery. Loading RDF data into R variables is normally taking the form of localised range queries, xing either the subject or object of the triples and replacing the rest with wildcards. For instance graph.find(s; null; null) retrieves all the triples of a resource while graph.find(null; p; o) presents an inverse traverse from object o. By replicating triples, data can be sorted according to not only subjects but also predicates and objects. This improves query execution.
For performance, LOD datasets are treated in the following ways. For datasets with RESTful API (e.g. DBpedia), the RDF resource to R variable mapping can be realised straightforwardly. Some datasets expose only SPARQL endpoints. SPARQL queries become necessary with the restriction that only local scans (e.g. hs; ; i or h ; ; oi) are permitted. Ideally, results of scan are used to construct local data graph. In the long run, on-demand data crawling can maintain local copies of frequently used datasets, helping to ensure data quality and manage mappings through local data curation.
R is inherently a single threaded application, though
parallelisation has been implemented using snow and snowfall
packages [
This OLAP-like data processing aims to emerge patterns
(such as hidden semantic relationships and semantic data
clusters) out of data held in LOD Cloud. Such a process
normally is performed on preloaded data and is not time
critical. While a plethora of R packages can be leveraged for data
mining, the main di culty lies in populating R dataframes
with LOD data that can facilitate R functions. By encoding
each RDF resource as one R variable, it is easy to construct
matrices that t with special purposes. For many predictive
machine learning tasks, voting based aggregation (e.g.
bagging [
Example. Given a dataset with patients data, the following code fragment splits the set of patient instances into 10 subsets4. Traversal with named vertices and edges can be carried out along both inbound and outbound directions. Here, we assume the entire set of patient instances will be loaded into memory. Alternatively, a partial loading can be executed to lower the demand for computing resources and latency. In the following example, edges of patient resource is indexed. Sampling is conducted against the index. Only selected instances are loaded. 1: patient_v <- graph_get_vertex("Patient") 2: patient_size <- graph_get_edge_count(patient_v, edge="rdf:type") 3: patient_index <- graph_edge_index(patient_v, edge="rdf:type") 4: n <- c(1:patient_size) 5: ns <- sample(n, size/10) 6: for (i in ns) { 7: ins<-graph_traverse(patient_v,edge=index[i]) 8: saveRDS(ins, file="...") 9: } The following code fragment intends to construct a randomforest-based prognosis model (line 11) for a certain disease based on a patient's gender and age. The patient data are loaded with a graph traverse transaction over the given patient instance vertices and the given outgoing edges (line 36, where wildcard indicates all the outgoing edges). Missing values are set to a default one (i.e. age = 75) for simplicity (line 9). 1: p_partition<-readRDS(file="...") 2: patients <- data.frame() 3: for(i in p_partition) { 4: p_data <- graph_traverse(vertex=i, out_edge="*"); 5: patients <-rbind(patients, p_data) 6: } 7: size <- length(patients) 8: training_set <- data.frame( age=patients$has_age, gender=patients$has_gender, ...) 9: training_set$age[is.na(training_set$age)] <- 75 10: labels <- as.factor(patients$status); 11: rfp <- randomForest(training_set, labels) In this example, we assume that the patient data partitions are passed using data le residing on the disk (line 1). This is for illustrative purposes only and does not exclude shared memory or message passing based solutions.
OLTP-like realtime data processing is supported through an event-driven mechanism that applies classi ers (obtained as 4Based on the literature, bagging should take a fraction between 1/2 to 1/50 depending on the size of the sample data. in the previous section) to data in an incremental fashion. This incremental characteristic is two-fold. Firstly, the system should detect the di erence between existing classi ed data and inputs so as to isolate the changes and restrain reclassi cation only against the di erences. Secondly, the system should update only those classi ers whose input data have changed since the most recent retraining. BGR accommodates both requirements through distributed logging of graph structural changes and localised event propagation observing graph structures. For instance, \OutEdgeCreatedEvent " is issued by the storage listener if an edge is inserted. This event instance carries information such as the edge (in triple form) and on which vertex (vs) this edge is created. Events propagate along paths that originate from vs to avoid global scans. As a result, a ected classi ers along the propagation routes are scheduled for update. Note that some machine learning algorithms can be easily adapted to ful ll the requirements (c.f. random forest [?]).
Versioning resources. An RDF resource normally consists of multiple triples jointly stating the constrains on the resource. Therefore, the event-driven incremental processing, which only has visibility of individual triples, requires a mechanism to obtain complete statements of the resource. We use versioning to ensure consistency when data are classi ed and when classi ers are retrained. Version information is stored at the value part of the key-value tuples and version updates are treated as atomic operations.
Multiple threads. Multi-threaded R is not likely to be available in the near future. As spawning threads is not possible, BGR runs multiple processes communicating through socket. For instance, one R process listens to the underlying storage driver for fetching graph structural events through a dedicate socket address. The events are then parsed to extract event types, triples that raise the events, and versions of the triples. Other R processes handle the events and dispatch them for further actions when necessary, again by writing to a socket address. Socket-based communication may not provide ideal performance; in many cases it becomes the main bottle neck of performance. It, however, o ers the most cost-e ective solution to increase parallelism without dismantling R.
We advocate and practice a declarative and resource-centric approach in BGR. More speci cally, expected analytics are constructed at the resource level and are associated with the target resource through RDF property declarations. For instance the following RDF triples assign an R random-forest classi er (de ned in section 3.4.1) to a resource (i.e. the \Patient" class). :Patient a owl:Class ; rdfs:subClassOf [ a owl:Restriction ; owl:onProperty :has_behaviour ; owl:someValuesFrom [ a owl:Class ; owl:oneOf (:new_patient_behaviour
:update_patient_behaviour)]]. ... :new_patient_behaviour a :Behaviour , owl:NamedIndividual ;
This essentially de nes how a resource (e.g. Patient) reacts to (or behaves against) events (e.g. onNewInstanceAsserted event), realised using the attached process (e.g. R:rfp). At the ontology class level, enumeration (owl:oneOf) is used to establish conceptual relationship between the Patient class and the desired functionalities w.r.t. the corresponding events. The actual implementation of behaviour instances can be realised, for example, in R. Depending on the size of the compiled code, the implementation can be stored either entirely at the value part of the KV tuple of h:new_patient_behaviour, :has_handler, "R:rft"i or separately with a pointer from the value part of the tuple. When a new patient instance is asserted, an event is raised which will trigger the embedded R function to react to such a change in the storage.
Several advantages are evident by assigning behaviour and storing its implementation close to a resource. Firstly, for a distributed data storage, this implies a close proximity of data and process localities. Secondly, behaviour enhances the reactive programming principle by packing small process units against very speci c data units. Thirdly, data behaviours and their implementations are conceptualised with well-formed RDFS constructs. This facilitates ontological inferences when necessary, though with caveats: i) increased inference complexity and ii) anonymous resources complicating RDF query handling.
BGR is still under development. This section reports the system design that has been considered so far and lists out potential future work.
The underlying graph storage is a distributed KVS based on HBase. HBase also handles data partition, locality, replication and fault tolerance. Jena graph introduces the necessary abstraction layer for indexing and retrieving triples in the KVS. A simple graph programming interface is responsible for graph traversal and scan operations. It follows the Tinkerpop Blueprint convention5 and currently talks to Jena graph so as to construct resource subgraph from the edge based storage data structure. The use of Jena is mainly for the convenience of leveraging Jena models when in-memory ontology inference becomes necessary. In the future, direct communication between storage and graph API is expected to improve the overall system performance. This is at the price of reduced ontological inference capacity.
Both storage and graph modules are implemented in Java.
R communicates with the storage driver through an R-Java
interfacing library, rJava package [
This paper calls for user-friendly and programmable LOD by leveraging and enhancing R, a free software toolkit for statistical computing and graphics.
Note that there are a few R packages (e.g. bigmemoRy) that aims in particular at Big Data computing. There are also R packages (e.g. foreach, ff, etc.) for strengthening R parallelism. Our proposal is not to compete with such existing solutions but to advocate a collaboration of two independent e orts and provide solutions that t the visions and requirements of linked data paradigm.
We also do not see competition with the RESTful movement, such as Linked Data Platform (LDP, [?]) which already gained momentum in the LOD community. LDP works at a layer lower than the proposed LOD/R integration, assisting data exposure so that the data can be consumed by the BGR functions and operators.