Effects of Network Structure Improvement on Distributed RDF Querying - Data Management in Cloud, Grid and P2P Systems - page 66

data IDs. The DHT implementations then provide a routing structure to store
and look up data items with a lookup time, for instance, for Chord [11] with
O

(log n ). Fair load-balancing and logarithmic lookup time achieve scalability
where the network performance does not decrease considerably with the size of
the network.

Tree-Based Overlay Networks. GridVine and 3rdf are distributed RDF sys-
tems using search-tree based overlay networks, such as P-Grid [9] and 3nuts [10].
The fundamental difference when using a search tree instead of a hash table is
omitting any hashing of data keys in order to preserves the order of data keys in
key space. In addition to logarithmic point queries this achieves ecient range
queries in key space, whereas hash tables do not provide an ecient implemen-
tation for range queries and the complete table has to be searched. Therefore,
when applications such as distributed RDF systems can organize data in key
space so that RDF triples needed during query evaluation have nearby keys in
key space, (e.g. a similar prefix in the search key equivalent to a small key range),
the advantage of range queries can be exploited and lookup time is significantly
reduced. The price for ecient range queries in this class of overlays is more
complicated and up to a constant factor larger routing structure being more
dicult to uphold under churn and data sets with high dynamics.

3.2 RDF Data and Query Model

Each node in the distributed RDF system can publish RDF resources in the net-
work. In RDF, resources are expressed as subject-predicate-object expressions,
called triples. The subject in a RDF triple denotes the resource, and the predicate
expresses a relationship between the subject and the object. Let U and L repre-
sent URIs and Literals, respectively in RDF, a triple ( v 1 ,v 2 ,v 3 ) ∈ U×U× ( U ∪ L )
over certain resources U and L is called a RDF triple [2]. RDF data can also be
represented as graph where subject and object are nodes and the predicates are
edges.
RDF resources are normally represented by URIs [2], and resources belonging
to a particular application domain usually share common namespaces or prefixes
(e.g. the 'Professor', 'name', 'email', and 'teach' keys in triples of Listing 1.1
share a common prefix 'ubd0v0'). Thus, the support of ecient range queries in
tree-based overlays, which is equivalent to short lookup times between network
keys with the same prefix, achieves short querying time when RDF data with
the same prefix is associated in a query (see the example in Listing 1.1).
@prefix rdf : < http ://www.w3. org/1999/02/22 − rdf − syntax − ns# >
@prefix ubd0v0 : < http ://www. lehigh . edu/zhp2/2004/0401/univ − bench . owl# >
@prefix d0v0: < http ://www. Department0 . University0 . edu# >
d0v0 :P3 rdf : type ubd0v0 : Professor .

d0v0 :P3 ubd0v0 :name Georg .

d0v0 :P3 ubd0v0 : email georg@ub .com.

d0v0 :P3 ubd0v0 : teach d0v0 : course1 .

Listing 1.1. RDF triples about a resource d0v0:P3 encoded in RDF/N3 format