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

3.4 Query Processing
Data of several peers has to be combined for evaluating conjunctive queries, and
we use the query processing algorithm, Query Chain (QC), originally presented
in [5], where the triple patterns contained in the query are iteratively resolved
by a chain of nodes. The query evaluation starts with a single triple pattern of
the query by doing a lookup for the peer responsible for the evaluation of this
triple pattern. This peer adds to an intermediate result all triples of its local
database qualified for the evaluated triple pattern. The intermediate result is
then extended by doing a lookup for a second triple pattern and joining the
results. This operation is executed until all triple patterns of the query have
been processed.
When triples are indexed six times for good load balancing, the triple storage
cost is 23% more for our test data than using three indexes. But we can exploit
this extra storage to achieve a better distribution of query processing load and
faster query response time by bundling bandwidth with parallelism. The Spread
By Value (SBV) query processing, presented in [5], extends the ideas of QC by
exploiting the values of matching triples found during processing triple patterns
incrementally; it rewrites the next triple pattern and distributes the responsi-
bility of evaluating it to more peers than QC. In our experiment we consider
the case where triples are indexed three times, and thus we use QC query pro-
cessing. Due to the small triple overhead of 23% caused by grouping of data
with same data in the same subtree, we will only get parallelism for identifiers
of triple components with a large set of triples managed by several peers. But if
the number of triples correlates with the result data size, it is not a bad thing.
Exploiting 3nuts Locality Features. The 3nuts information locality fea-
ture preserves key ordering; therefore for triple patterns with lookup keys shar-
ing the same prefixes (e.g. the 'UndergraduateStudent', 'name', 'advisor', and
'teacherOf' etc lookup keys in Listing 1.2 share a common prefix 'ubd0v0'), the
number of hops required to reach all these keys is reduced (at best, some keys
are managed by the same peer).
The number of hops required to evaluate triple patterns of a query can be
further reduced through a so-called feature interest locality provided in the dis-
tributed search tree of 3nuts. It allows peers responsible for triples components
(subject, predicate, or object) to establish few additional routing links, short-
cuts , to other frequently occurring components (subject, predicate, or object) of
relevant triples. These routing shortcuts can be established with only a constant
increase of the peer's routing tables. To support the creation of shortcuts, each
peer in the network responsible for the triple components' values (i.e. subject,
predicate, or object) creates a link to the peer, sharing at least one of the com-
ponents' values of the same triple. In this way peers create Peers Link Graph
defined as follows:
Definition 1. A Peers Link Graph G is a tuple (N, E), where N is the set of
peers in G and E is the set of directed weighted edges in G. Two peers from N