In recent years, the amount of structured RDF data available on the Web has been increasing rapidly. Efficient query processing that can scale to large amounts of RDF data has become an important topic. Significant efforts have been dedicated to the development of solutions for RDF data management. Along this line of research, we elaborate on a novel data partitioning strategy, which leverages the structure of the underlying data. This structure is represented in form of a parameterized structure index we propose for (RDF) data graphs called PIG. It is not only used for data partitioning but also has been designed to accelerate the matching of graph-structured queries against RDF data. In our benchmark against state-of-theart techniques, our structure-based approach for partitioning and query processing exhibits 7-8 times faster performance.
In recent years, the amount of structured data available on the Web has been increasing rapidly, especially RDF data consisting of triples of the form hs; p; oi, where s is the subject, p is a property, and o is the object. Such triples form a data graph G(V; L; E) where the vertices V denote resources and their values, which are connected by directed edges E, each endowed with a label from a label set L. One example is shown in Fig. 1. Supervises
Supervises
Supervises
Supervises 4
5 Name
Name
This development of a data web opens new ways for addressing
complex information needs. Search is no longer limited to
matching keywords against documents, but instead, structured queries
can be processed against web resources. In this regard,
conjunctive queries represent an important fragment of widely used
languages (SQL, SPARQL), which has been a focus of recent work on
RDF data management [
A match of a conjunctive query q on a graph G is a mapping h from the variables of q to vertices of G such that the according substitution of variables in the graph-representation of q would yield a subgraph of G. Therefore a query match h can be interpreted as a certain type of homomorphism (i.e. a structure preserving mapping) from the “query graph” to the data graph. Because the amount of data is enormous and largely increasing, scalability of this graph pattern matching on the data web has become a key issue.
for storing and querying RDF data such as Hexastore, RDF-3X and
SW-Store, can be distinguished along three dimensions: data
organization in terms of (1) partitioning and (2) indexing, and (3) query
processing. Vertical partitioning has been proposed to decompose
the data graph into n two-columns tables, where n is number of
properties. This has shown to be superior than the “one single giant
table” organization, and the use of property tables [
that improve the state-of-the-art in data partitioning and query processing:
work on XML data such as dataguide [
structure-based partitioning scheme, where triples about elements with the same structure are physically grouped. This is to obtain a contiguous storage of data that likely co-occurs in query answers.
the query against the structure index first, which is typically much smaller than the data graph (c.f. examples in Fig. 2). This helps to focus on data that satisfy the overall structure of the query and on this basis, to proceed with standard processing at the level of the data for only certain parts of the query.
B1: 3,7 t A rs k o W e m a
N B3: 8,9 B5:KIT, MIT
Our solution is complementary to the concepts for indexing and
query optimization [
Reduction of I/O Costs: We do not simply retrieve all data that matches some given triple patterns but focus on the one that satisfies the entire query structure.
needed only for some parts of the query. In the extreme cases where no structure index matches can be found, we can skip data access and joins at the data level completely.
In a benchmark against the state-of-the-art techniques for data
partitioning and query processing used in SW-Store [
Outline We introduce PIG in Section 2. Partitioning, query
processing and parameterization are discussed in Section 3, 4 and 5.
Experiments along with results are discussed in Section 6 before
we review related work in Section 7 and conclude in Section 8. For
more details, we refer the interest readers to our technical report
[
We introduce the notion of a parameterizable structure index for general graph-structured data (like RDF) called PIG.
PIG - Parameterizable Index Graph PIG is a special graph forming a compact representation of the data graph, whose vertices stand for groups of data graph elements that have a similar or equal structural “neighborhood”. We capture the concept of equal structural neighborhood by the well-known notion of bisimulation originating from the theoretical analysis of state-based dynamic systems. We adopt this notion to capture both directions of edges. We consider graph nodes v1; v2 as bisimilar (written: v1 v2), if they cannot be distinguished by looking only at their outgoing (forward bisimilarity) and incoming (backward bisimilarity) “edge trees”. For better control, we parameterize our notion of bisimulation by two sets of edge labels L1 and L2 that specify the labels of edges taken into account for determining the forward and backward bisimulation respectively:
DEFINITION 1. Given a data graph G = (V; L; E) and two edge label sets L1; L2 L, a L1-forward-L2-backward bisimulation on G is a binary relation R V V on the vertices of G such that for v; w 2 V , l1 2 L1 and l2 2 L2: vRw and l1(v; v0) 2 E implies that there is a w0 2 V with l1(w; w0) 2 E and v0Rw0, vRw and l1(w; w0) 2 E implies that there is a v0 2 V with l1(v; v0) 2 E and v0Rw0, vRw and l2(v0; v) 2 E implies that there is a w0 2 V with l2(w0; w) 2 E and v0Rw0, vRw and l2(w0; w) 2 E implies that there is a v0 2 V with l2(v0; v) 2 E and v0Rw0.
The relation is itself a bisimulation and can be represented by the set of its equivalence classes called extensions, where all vertices contained in one extension are pairwise bisimilar. These extensions form a partition of the vertices V of the data graph, i.e. a family P of pairwise disjoint sets whose union is V . The index graph G of G is defined in terms of extensions and relations between them:
DEFINITION 2. Let G = (V; L; E) be a data graph and its L1-L2-bisimulation. Vertices of the associated index graph G = (V ; L1 [ L2; E ) are exactly G’s -equivalence classes V = f[v] j v 2 V g, with [v] = fw 2 V j v wg. Labels of G are exactly the labels of G. An edge with a label e is established between two equivalence classes [v] and [w] exactly if there are two vertices v 2 [v] and w 2 [w] such that there is an edge e(v ; w ) in the data graph, i.e. E = fe([v ] ; [w ] ) j e(v ; w ) 2 Eg.
L1 = fWorksAt ; Supervises ; AuthorOf g and L2 = fWorksAt ; AuthorOf g. Elements that are indistinguishable in terms of their edge-labelled, incoming and outgoing paths are for instance 2, 4, and 6. Thus, they are elements of the extension B4.
Construction of PIG First, a bismulation for L1 and L2 is
calculated, using an adapted version of the algorithm for determining the
coarsest stable refinement of a partitioning [
KIT y B6
instantiates a variable of a query obviously depends on its structural properties, i.e. the incoming and outgoing edges resp. paths. Therefore, if nodes are physically grouped together based on structural similarity, a group would contain more candidates for variable instantiations. Thus, we apply structure-based partitioning to the data graph by creating a physical group (e.g. a table) for every vertex of the index graph, i.e. one group for every extension. Every group contains the triples, which “describe” elements contained in the corresponding extension. That is, triples are in the same group when they contain the same properties and their subjects belong to the same extension.
Query processing in our scenario is essentially finding a homomorphism from the query graph q = (Vvar ] Vcon; L; P ) to elements of the data graph G = (V; L; E). According to the following proposition, the structure index can be exploited to perform this task:
Proof Given a q-edge l(v1; v2), first observe that l(h(v1); h(v2)) is a G-edge since h is a homomorphism. Then we find that l(h (v1); h (v2)) = l([h(v1)] ; [h(v2)] ) is a G -edge due to the definition of the index graph. 2
Intuitively speaking, a mapping into G exists only if it does also exist into the associated index graph G . Further, the resulting extensions Bi = [h(v)] from V in G that match the nodes in q will obviously contain the data graph matches h(v). Thus, the procedure for query processing can be decomposed into two steps: (1) finding matching extensions Bi on the index graph G first, (2) then combining data elements retrieved for Bi to obtain the final data graph matches. In the following, we denote G Idx as the index used for the retrieval of elements from the index graph and GIdx is used for accessing elements of the data graph.
Just like an answer, an index graph match is the result of a homomorphic mapping h from the query graph q(Vq; Lq; P ) to the index graph G (V ; L; E ). Elements of an index graph match are vertices of G that are assigned to variables and constants of q. For this computation, we propose a join procedure that returns a result table R containing all matches h : Vq ! V . First, a set of index graph candidate edges El is retrieved from G for every query edge label l occurring in the query (using G Idx). Then, these candidate sets are joined along the vertices of q to obtain R. Figure 3 illustrates two matches.
The previous computation results in a set R of index graph matches h : Vq ! V . Every element of these matches is an extension which essentially is a set of vertices of the queried data graph G. According to Proposition 1, every match of the query against the data graph is “contained” in one of the index graph matches calculated so far (e.g. h(v1) is in h (v1) = [h(v1)] ). It suffices to focus on the index graph matches for the computation of the data graph matches because only data contained by them satisfy the overall query structure. We will now show that tree-shaped parts containing only undistinguished variables can even be pruned
DEFINITION 3. Every edgeless single-vertex rooted graph (G; r) with G = (frg; L; ;) is L1-forward-L2-backward treeshaped. Moreover let (G1; r1) and (G2; r2) with G1 = (V1; L; E1) and G2 = (V2; L; E2) be two L1-forward-L2backward tree-shaped graphs with disjoint vertex sets. Let v 2 V1 and let e 2 fl(v; r2) j l 2 L1g [ fl(r2; v) j l 2 L2g. Then the rooted graph (G3; r1) with G3 = (V1 [ V2; L; E1 [ E2 [ feg) is
Given such a tree-shaped query part, a stronger property can be asserted for the index graph matches, i.e. they contain all and only data graph matches such that no further processing at the level of the data graph is needed:
graph G (where is a L1-forward-L2-backward bisimulation) and let q be a L1-forward-L2-backward tree-shaped graph with root r. Let h0 be a homomorphism from q to G . Then for every data graph node v 2 h0(r), there is a homomorphism h from q to G with h(r) = v
Proof. We do an induction on the maximal tree-depth of G0. As base case, note that for tree depth 0, the claim is trivially satisfied. For any greater tree depth, subsequently consider every child node v0 of r in G0. Assume l 2 L1 and l(r; v0) 2 E0 (the backward case follows by symmetry). Then, by definition of bisimularity, there must exist a w 2 h(v0) with l(v; w) 2 E. We chose h(v0) = w. Now we invoke the induction hypothesis for the subtree of G0 with root v0 which yields us the values h(u0) for all successors of v0. So we have constructed h with the desired properties. 2
In words: if the query is of the aforementioned tree shape, then every data node from any extension associated to the query root r by an index graph match is a data graph match for r. Hence, before computing data graph matches, the respective query parts can be removed.
After pruning the query, we use another join procedure to
compute a result table where rows capture bindings to distinguished
query variables. These bindings are data elements contained in the
index graph matches h , which satisfy the structure as well as the
concrete elements (i.e. constants and distinguished variables)
mentioned in the query. Query edges are processed successively. At
every iteration, triples are retrieved from GIdx and are joined with
the (intermediate) results set. More precisely, given the query edge
p(x; y), the triples hx 7! s; p; y 7! oi matching p(x; y) are
considered. They are fetched from the corresponding block [s] of the
structure-based partitioned data graph index GIdx, where s 2 [s]
and h : x ! [s] . Intuitively speaking, only triples with subjects
that are contained in the index match [s] are retrieved from disk.
Thus, only subjects that are known to satisfy the query structure are
considered. This is different from the standard approaches [
working at the same place as their supervisors y, namely a place called KIT . One match on the index graph is h1 = fu 7! B3; x 7! B4; y 7! B1; z 7! B2; KIT 7! B5g. Based on this, we know that data elements belonging to extensions obtained from the index graph match satisfy the query structure, e.g. elements in B4 are authors of z, supervised by y, work at some place u that has a name. A tree-like part that can be pruned is AuthorOf (x; z). It produces the index graph match hB4 AuthorOf B2i. Since 2; 4; and 6 in B4 are already known to be authors of some z, no further data processing is needed for this query part. However, we have to look at the data to verify that elements in B4 work at KIT , and are supervised by some y also working at KIT . For this, we need to retrieve and join the triple matches for hx W orksAt ui, hy W orksAt ui, hu N ame KIT i, hy Supervises xi. Note that the query example here contains cycles. In practice, there are many queries exhibiting simpler structure, which offer greater potential for query pruning. In the extreme cases where no index graph matches can be found, we can skip the entire second step to avoid data access and joins completely.
The procedure presented in the previous section computes answers data matches for an index graph match h . In order to compute all data matches, this has to be repeated for all index graph matches h in R. However, the diverse matches might partially overlap. To formalize and computationally exploit this, we introduce the following notion:
DEFINITION 4. Let G be a data graph and G be an index graph. For a query q(Vq; Lq; P ), let P 0 P be a subset of the query atoms. We say that two matches h1 and h2 from q into G are in the same P 0-match class if for all l(v; w) 2 P 0 h1 (v) = h2 (v) and h1 (w) = h2 (w). The set of partial data matches of a P 0-match class M consists of all the functions : vertices(P 0) ! V satisfying 1. l( (v); (w)) 2 E for all l(v; w) 2 P 0 and
have [ (v)] 2 M such that for all v 2 vertices(P 0) we = h (v).
Fig. 4 displays the case for our example, where P 0 = P n fAuthorOf (x; z)g, i.e. the two matches h1 ; h2 overlap on all query edges (resp. atoms) except AuthorOf (x; z). Given such an equivalence between matches, the aforementioned na¨ıve strategy for the independent evaluation of matches might result in many redundant disk accesses and join operations. The following proposition enables a more efficient computation of data graph matches: PROPOSITION 3. Let G be a data graph, let G ated index graph, and let q be a conjunctive query. be the associ1. Every match of q(Vq; Lq; P ) into G is contained in the set of partial data matches associated to one of the P -match classes. 2. Let P 0 P and l(v; w) 2 P n P 0. For every P 0 [ fl(v; w)gmatch class M with a corresponding partial data match , there is a P 0-match class M 0 with corresponding data match 0 such that there is a h0 2 M 0 with
M = fh h0 (w)g, j h (v) =
h0 (v) and h (w) = 2 f 0g ./ ffv 7! v1; w 7! h0 (v); v2 2 h0 (w); l(v1; v2) 2 Eg. v2g j v1 2
Proof. The first part of the proposition is an immediate consequence of Proposition 1 and Definition 4. For the proposition’s second part, the claim follows from choosing M 0 = fh j h (v) = h0 (v) for all v 2 vertices(P 0) and some h0 2 M g and 0 : v 7! (v). 2
In words, the preceding proposition ensures that all data graph matches of a query can be obtained by a successive refinement of match classes and their associated data matches. Consequently, the optimized procedure for computing query data matches consists of two main parts: (1) update of match classes and (2) evaluation of match classes.
Match classes are defined w.r.t. query vertices. For the first part, match classes are thus created (updated) according to the query vertices that are added during the process of join processing. At first, there is only one initial match class R consisting of all index graph matches (line 1). During the processing of query atoms p(x; y), the set of classes M C becomes more and more “fine-grained”, as any matches not coinciding on how x and y are mapped to V will be distributed to different match classes (line 11). A hash map H, which associates pairs of index matches (x-y-instantiations) with match classes, is employed to check for overlaps. Note that during the processing of the atoms in P , the number of classes grows as high as the number of matches, i.e. every match constitutes its own class.
For answer computation, results are retrieved and stored in Ai for every match class Mi encountered during processing of atoms in P . Since every class groups together matches that overlap w.r.t. the already considered part of the query, all matches are evaluated only once during query processing. After all atoms have been evaluated for all match classes, intermediate data matches for each match class are combined to obtain the final data matches (line 20).
We briefly discuss the complexity of query processing and upon the results, elaborate on the parametrization of PIG.
Complexity For RDF query processing, we have
O(edgemaxjP j), where jP j denotes the number of query
atoms and edgemax is jl(v1; v2)j with l being the property
instantiated by the largest number of edges, e.g. the size of the
largest table used in [
PROPOSITION 4. For a query with jP j atoms, the time and space for calculating the answers through the computation of index matches and the subsequent processing of data graph matches is bounded by O(edgemaxidxjP j +jRj edgemaxdatajPprunedj). Algorithm 1: Evaluating Match Classes Input: G(V; L; E), q(Vq; Lq; P ), Index matches
R = fh1 ; h2 ; : : : ; hn : Vq ! V g.
Data: Two-columns table Ep containing matches h0 : fx; yg ! V retrieved for a predicate p, a set of match classes M C = fM1; M2; : : :g with Mi R, intermediate partial matches Ai for every match class Mi, partial hash map H : V V ! M C mapping pairs of index matches to match classes.
Result: Table A, where each row represents an answer. 1 set M C = fRg.
4 H ;
7 move h from Mi to the match class
H(h (x); h (y)).
This is because our approach involves an additional component, i.e. the cost O(edgemaxidxjP j) for computing index matches, where edgemaxidx = maxl2L jEl j is bounded by the size of the index graph. However, we need only to join along a pruned version Ppruned P of the query. So we obtain O(jRj edgemaxdatajPprunedj) where edgemaxdata = maxB1;B22V ;l2L jfl(v; v0) j v 2 B1; v0 2 B2gj. Thus, edgemaxdata is bounded by the size of the largest extension.
Parametrization of PIG In comparison, less data have to be retrieve from G, i.e. edgemaxdata edgemax, and also, fewer joins are required, i.e. jPprunedj instead of P . The overhead introduced to achieve this O(edgemaxidxjP j). The parametrization of L1 and L2 has the following effect on the overhead and gain introduced by our structure-based query processing:
When more labels are included in L1 and L2, the index graph becomes larger. Thus, edgemaxidx becomes larger. On the other hand, more labels can be considered for query pruning, thus potentially increasing the fraction of prunable query parts (jP n Pprunedj). Also, the physical groups obtained from structurebased partitioning become more fine-grained, thereby reducing the size of edgemaxdata.
Thus L1 and L2 shall be parameterized w.r.t the query workload to keep the index as small as possible. As a general strategy, the parametrization shall be computed based on frequent prunable query parts, i.e. search for prunable query parts in the workload and then, use labels occurring in these parts as parameters.
More optimized systems have been built that implement the
concepts of indexing and query optimization [
We now summarize the experiment reported in details in [
Performance In Fig. 5a+b, total query processing time is plotted for both approaches. Clearly, SQP is faster than VPQP. For DBLP in particular, SQP performs a factor of 7-8 faster. Further, we note that SQP exhibits much better performance than VPQP w.r.t. queries that have more complex structures, i.e. the queries Q4-Q15. SQP is slightly worse w.r.t. simple queries, i.e. the single triple patterns Q1-Q3. This suggests that with more complex queries, the overhead incurred by the additional structure-level processing can be outweighed by the accumulated gain.
Breaking down the results, we found that the gain in loading and join is small for single-atom queries, but substantial for more complex structured queries. In these cases, it outweighs the additional cost of index matching.
Scalability We measured the average query performance for LUBM with varying size (i.e. generated for 1, 5, 10, 20 and 50 universities). We found that the performance of our improves with the size of the data. In particular, the gain for load and join increases in larger proportion than the overhead incurred for index match. This is because match performance is determined by the size of the index graph. This depends on the structure but not on the size of the data graph. Thus, the match time does not necessarily increase when the data graph becomes larger. The positive effect of data filtering (IO reduction) and query pruning (load and join) however, correlates with the data size.
We already compare our approach against triple stores along different dimensions and now, discuss related work on XML and semi-structured data processing.
Structure Index Structural information has been exploited for
indexing semi-structured and XML data. Unlike Dataguide [
Query Processing Our structure-aware processing is similar to
the work on using structure indexes for (a) evaluating path queries,
and for (b) finding occurrences of twig patterns (tree-structure) in
a XML database based on multi-predicate merge join [
SQP load(VPQP‐SQP) join(VPQP‐SQP) # removed query nodes VPQP c) Time for Queries on DBLP types parent-child or ancestor-descendant whereas in our setting, both query and data are generally graph structured. We employ rather a combination of (a) and (b): similar to (a), we match the query against the index graph. Similar to (b), intermediate results are computed and then joined to obtain the final answers. While intermediate results in (b) are simple root-to-leaf paths of the twig pattern, we retrieve and operate only on data elements that satisfy the structural constraints of the entire graph-structured query.
We have proposed techniques for RDF data partitioning and query processing that can exploit the underlying structure to improve the management of RDF data, based on a novel structure index call PIG. In an principled manner, we showed that this approach is faster than the state-of-the-art, especially for complex structured queries.
As future work, we will elaborate on how existing work on RDF query optimization can be used for the proposed structure-based query processing technique. Further, strategies proposed for optimizing updates of XML structure indexes will be studied and adopted.