Graph-Based RDF Data Management

The Resource Description Framework (RDF) data model was originally proposed by W3C for modeling WebObjects as part of developing the semantic web. However, its use is now wider than the semantic web. For example, Yago and DBpedia extract facts from Wikipedia automatically and store them in RDF format to support structural queries over Wikipedia [5, 26]; biologists encode their experiments and results using RDF to communicate among themselves leading to RDF data collections, such as Bio2RDF (bio2rdf.org) and Uniprot RDF (http://​www.​uniprot.​org/​format/​uniprot_​rdf). Related to semantic web, Linking Open Data (LOD) project builds an RDF data cloud by linking more than 3000 datasets. The use of RDF has further gained popularity due to the launching of “knowledge graph” by Google in 2012.

An RDF dataset is a collection of triples of the form \(\langle\)subject, property, object\(\rangle\). A triple can be naturally seen as a pair of entities connected by a named relationship or an entity associated with a named attribute value. In contrast to relational databases, an RDF dataset is self-describing and does not need to have a schema (although one can be defined using RDFS). The simplicity of this representation makes it easy-to-use RDF for modeling various types of data and favors data integration.

There exist many large-scale RDF datasets, e.g., Freebase¹ has 2.5 billion triples [6] and DBpeida² has more than 170 million triples [17]. LOD now connects more than 3000 datasets and currently has more than 84 billion triples,³ with the number of data sources doubling within three years (2011–2014). The growth of RDF dataset sizes and the expansion of their use, coupled by the definition of a declarative query language (SPARQL) by W3C, have made RDF data management an active area of research and development, and a number of RDF data management systems have been developed.

As with any database management system (DBMS), an RDF data management system has to address the challenges of efficiency, scalability and usability. However, these exhibit themselves in somewhat different ways, as we describe below:There are two typical approaches to designing RDF data management systems: relational approaches and graph-based approaches [22]. The relational approaches map RDF data to a tabular representation in a number of ways and then execute SPARQL queries on them—sometimes mapping SPARQL queries to SQL. These can further be grouped into four categories:The second major category of systems is graph-based, which model both RDF data and the SPARQL query as a graph and evaluate the query by subgraph matching using homomorphism, e.g., [3, 34, 38, 39]. The advantage of this approach is that it maintains the original representation of the RDF data and enforce the intended semantics of SPARQL. Also, some graph database techniques, such as the structure-aware indices [38, 39] and graph-based query algorithms [34], are more suitable for RDF data. The challenge is to perform subgraph matching efficiently—this is a well-known computationally expensive problem. We have been developing a graph-based RDF data management system, called gStore, since 2009.⁶ In this paper, we review our research results and provide an overview of our graph-based data management techniques.

There are three pieces of gStore that warrant description. The first is a centralized graph-based RDF triple store that stores a RDF graph using adjacency lists [38, 39]. Two key techniques incorporated in gStore are (a) a neighborhood structure-aware index that encodes the neighborhood structure of vertices in data graphs into “signatures” and builds a tree-structured index over them, and (b) employing graph homomorphism-based subgraph match algorithm to find answers to SPARQL queries instead of relational join processing. Furthermore, gStore can also handle the dynamic updates to the RDF data efficiently. This is described in Sect. 3.

The second piece is a distributed version of gStore, called gStore-D [23] that addresses scale-out issues. The novel aspect of gStore-D is the adoption of “partial evaluation and assembly” framework. A large graph is divided into several fragments, each of which is resident at one site (we do not consider replication at this point). The key issue then becomes how to find the subgraph matches (of SPARQL query Q) that cross multiple fragments—these are called crossing matches. We address this using the partial evaluation approach where a SPARQL query is executed over each fragment of RDF graph to find local partial matches that are then assembled to compute the crossing matches. This is described in Sect. 4.

The third piece addresses usability. Although SPARQL is the standard query language for RDF, it is not an easy language to learn and use, especially for casual users. Therefore, we also design a RDF question/answering system, called gAnswer [37], to answer users’ natural language questions over RDF repositories. The core idea is to translate a natural language question to a semantic query graph and employ subgraph pattern-matching technique to figure out the answers. This is described in Sect. 5.

In this section, we provide an overview of RDF and SPARQL. Readers can refer to W3C documents (such as RDF primer⁷ and SPARQL 1.1 Recommendation⁸) for more details.

RDF represents data as a collection of triples of the form \(\langle\)subject, property, object\(\rangle\), where subject is an entity, class or blank node, a property is one attribute associated with one entity and object is an entity, a class, a blank node or a literal value. In RDF, entities, classes and properties are denoted by URIs (Uniform Resource Identifier) that refers to named resources. Blank nodes refer to anonymous resources that do not have a name.

A triple can be naturally seen as a pair of nodes connected by a named relationship. Hence, an RDF dataset can be represented as a graph where subjects and objects are vertices, and triples are edges with property names as edge labels. Note that there may exist more than one property between a subject and an object, that is, multiple-edges may exist between two vertices in an RDF graph.

A sample of RDF dataset is given in Table 1, whose corresponding RDF graph is given in Fig. 1a.⁹

SPARQL is the query language for RDF. The fundamental building block of SPARQL is the basic graph pattern (BGP), which is a collection of triples.

A match of BGP over RDF graph is defined as a partial function \(\mu\) from \(V_\mathrm{Var}\) to the vertices in the RDF graph. Formally, we define the match as follows:

The set of matches for Q over RDF graph G is denoted as \(\llbracket Q \rrbracket _G\), based on which, we return variable bindings that are defined in the SELECT clause.

The graph representation of this query is given in Fig. 1b. The answers to the query are bindings to variable ?moviename as shown bellow.

A general SPARQL query may contain FILTER, UNION, OPTIONAL clauses. Note that these are optional according to SPARQL syntax. Formally, a general graph pattern in SPARQL is defined as follows:

A SPARQL built-in condition is constructed using the variables in SPARQL, constraints, logical connectives (\(\lnot\), \(\wedge\), \(\vee\)), inequality symbols (\(\le\), \(\ge\), <, >), the equality symbol (\(=\)), unary predicates like bound, isBlank and isIRI, plus other features [24, 29]. We formally define the answers of SPARQL based on BGP matches.

The following example illustrates SPARQLs with “OPTIONAL”.

whose results are:

Note that most existing work focus on BGP query processing and optimization, which is also the focus of this paper, although gStore can support full graph pattern queries as defined in Definition 7.

gStore [38, 39] is a graph-based RDF data management system (or what is commonly called a “triple store”) that maintains the graph structure of the original RDF data. Its data model is a labeled, directed multiedge graph (called RDF graph—see Fig. 1a), where each vertex corresponds to a subject or an object. We also represent a given SPARQL query by a query graph Q (Fig. 1b). Query processing involves finding subgraph matches of Q over the RDF graph G. gStore incorporates an index over the RDF graph (called VS*-tree) to speedup query processing. VS*-tree is a height-balanced tree with a number of associated pruning techniques to speedup subgraph matching.

The increasing size of RDF data requires a solution with good scale-out characteristics. Furthermore, the increasing amount of RDF data published on the Web requires distributed computing capability. We address this issue by developing a distributed version of gStore that we call gStore-D [23].

Given a RDF graph G, we adopt a vertex-disjoint graph partitioning algorithm (such as METIS [16]) to divide G into several fragments, such as Fig. 6. In the vertex-disjoint graph partitioning, any vertex u is only resident at one fragment and we also say that vertex u is an inner vertex of the fragment. If a vertex u is linked to another vertex in the other fragment, u is called a boundary vertex. In our method, we allow some replica of the boundary vertices between different fragments. In Fig. 6, vertex 008 (in fragment \(F_2\)) is a boundary vertex, since it is linked to vertex 003 in fragment \(F_1\). Thus, we allow the replica of 008 in fragment \(F_1\). The replica is called an extended vertex in \(F_1\). We note that gStore-D does not require a specific graph partitioning strategy, although different partitioning strategies may lead to different performance. For now, we consider each fragment being placed at one site. The main challenge in gStore-D is that evaluating a query may involve accessing multiple fragments. Some partition of the query may be answered within a fragment (i.e., subgraph matches are evaluated locally) that we call local partial matches (defined in Definition 8). Others, however, may require determining matches across fragments that we call crossing matches. Local partial matches can be handled using the technique of the previous section, but evaluating crossing matches requires a new approach. For this, we adopt a “partial evaluation and assembly” strategy. We send the SPARQL query Q to each fragment \(F_i\) and find local partial matches of query Q over fragment \(F_i\). If a local partial match is a complete match of Q, it is called an “inner match” in fragment \(F_i\). The main issue of answering SPARQL queries over the distributed RDF graph is finding crossing matches efficiently. We illustrate the main idea of gStore-D using the following example.

As noted above, the key issue in the distributed environment is how to find crossing matches; this requires subgraph matching across fragments. For query Q in Fig. 7, the subgraph induced by vertices 003,006, 007,008, 012, 013 and 014 is a crossing match between fragments \(F_1\) and \(F_2\) in Fig. 6 (shown in the shaded vertices and red edges).

As mentioned earlier, we adopt the partial evaluation and assembly [15] strategy in our distributed RDF system design. Each site \(S_i\) treats fragment \(F_i\) as the known input s and other fragments as yet unavailable input \({\overline{G}}\). Each site \(S_i\) finds all local partial matches of query Q within fragment \(F_i\). We prove that an overlapping part between any crossing match and fragment \(F_i\) must be a local partial match in \(F_i\). Then, these local partial matches are assembled into the complete matches of SPARQL query Q.

Figure 8 demonstrates how to assemble local partial matches. For example, the subgraph induced by vertices 003, 006, 008 and 012 is an overlapping part between M and \(F_1\). Similarly, we can also find the overlapping part between M and \(F_2\). We assemble them based on the common edge \(\overrightarrow{008,003}\) to form a crossing match.

To summarize, there are three major steps in our method.Recall that each site \(S_i\) receives the full query graph Q (i.e., there is no query decomposition). In order to answer query Q, each site \(S_i\) computes the partial answers (called local partial matches) based on the known input \(F_i\). Intuitively, a local partial match \(\mathrm{PM}_i\) is an overlapping part between a crossing match M and fragment \(F_i\) at the partial evaluation stage. Moreover, M may or may not exist depending on the yet unavailable input \({\overline{G}}\) . Based only on the known input \(F_i\), we cannot judge whether or not M exists. For example, the subgraph induced by vertices 003, 006, 008 and 012 (shown in shaded vertices and red edges) in Fig. 6 is a local partial match between M and \(F_1\).

Step 3 (Assembly) Each site finds all local partial matches in the corresponding fragment. The next step is to assemble partial matches to compute crossing matches and compute the final results. We propose two assembly strategies: centralized and distributed (or parallel). In centralized, all local partial matches are sent to a single site for assembly. For example, in a client/server system, all local partial matches may be sent to the server. In distributed/parallel, local partial matches are combined at a number of sites in parallel.

We first define the conditions under which two partial matches are joinable. Obviously, crossing matches can only be formed by assembling partial matches from different fragments.

The first condition says that the same query vertex cannot be matched by different internal vertices in joinable partial matches. The second condition says that two local partial matches share at least one common crossing edge that corresponds to the same query edge.

The join result of two joinable local partial matches is defined as follows.

In the centralized assembly, all local partial matches are sent to a final assembly site. We propose an iterative join algorithm to find all crossing matches. In each iteration, a pair of local partial matches is joined. When the join is complete (i.e., a match has been found), the result is returned; otherwise, it is joined with other local partial matches in the next iteration. In order to reduce the join space of the iterative join algorithm, we divide all local partial matches into multiple partitions such that two local partial matches in the same set cannot be joinable; we only consider joining local partial matches from different partitions. In the distributed assembly, we adopt Bulk Synchronous Parallel (BSP) model [28] to design a synchronous algorithm for distributed assembly. A BSP computation proceeds in a series of global supersteps, each of which consists of three components: local computation, communication and barrier synchronization. In the local computation step, each site adopts the iterative join algorithm to assemble local partial matches within the site. If a join result is a complete match of query graph Q, it will be returned directly; otherwise, these join results (i.e., the intermediate results) will be sent to the other sites in the communication step. The details about the communication and system termination condition are discussed in [23].

As mentioned earlier, gStore and gStore-D aim to answer users’ structural languages (SPARQL) efficiently. As noted earlier, the complexity of the SPARQL syntax and the lack of a schema make it hard for end users to use SPARQL. Providing end users an easy-to-use interface to access RDF datasets in an effective way has been recognized as an important concern. This has lead to research for RDF question/answering (Q/A) systems [4, 32, 33, 37]. We have designed gAnswer [37] to address the problem from the perspective of a graph database.

Usually, there are two stages in RDF Q/A systems: question understanding and query evaluation. Existing systems in the first stage translate a natural language question N into SPARQL queries [11, 18, 32], which are evaluated in the second stage. The focus of the existing solutions is on query understanding.

The inherent hardness in RDF Q/A is the ambiguity of natural language. In order to translate N into SPARQL queries, each phrase in N should map to a semantic item (i.e., an entity or a class or a predicate) in RDF graph G. However, some phrases have ambiguities. For example, phrase “Philadelphia” may refer to entity \(\langle\)Philadelphia(film)\(\rangle\) or \(\langle\)Philadelphia(city)\(\rangle\). Similarly, phrase “play in” also maps to predicates \(\langle\)starring\(\rangle\) or \(\langle\)director\(\rangle\). Although it is easy for humans to know that the mapping from phrase “Philadelphia” (in question N) to \(\langle\)Philadelphia(city)\(\rangle\) is wrong, this is not easy for machines. Disambiguating one phrase in N can influence the mapping of other phrases. The most common technique is joint disambiguation [32]. Existing disambiguation methods only consider the semantics of a question sentence N. They have high cost in the query understanding stage; thus, it is most likely to result in slow response time in online RDF Q/A processing.

gAnswer [37] deals with the disambiguation in RDF Q/A from a different perspective. We do not resolve the disambiguation problem in the question understanding stage, i.e., the first stage. We take a lazy approach and push down the disambiguation to the query evaluation stage. The main advantage of our method is it can avoid the expensive disambiguation process in the question understanding stage and speedup the entire process. We illustrate the intuition of our method by an example as follows:

A challenge of our method is how to define a “match” between a subgraph of G and a natural language question N. Because N is unstructured data and G is graph structure data, we should fill the gap between two kinds of data. Therefore, we propose a semantic query graph \(Q^\mathrm{S}\) to represent the question semantics of N. We formally define \(Q^\mathrm{S}\) in Definition 12. An example of \(Q^\mathrm{S}\) is given in Fig. 9, which represents the semantic of the question N. Each edge in \(Q^\mathrm{S}\) denotes a semantic relation. For example, edge \(\overline{v_1v_2}\) denotes that “who was married to an actor.” Intuitively, a match of question N over RDF graph G is a subgraph match of \(Q^\mathrm{S}\) over G (formally defined in Definition 13).

In the running example of Fig. 9, \(\langle\)“be married to,” “who,” “actor”\(\rangle\) is a semantic relation, in which “be married to” is a relation phrase, “who” and “actor” are its associated arguments. We can also find another semantic relation \(\langle\)“play in,” “that,” “Philadelphia”\(\rangle\) in N. The two semantic relations are joined to form a semantic query graph, which is defined as follows.

There are offline and online phases in our solution. In the offline phase, we build a paraphrase dictionary D, which records the semantic equivalence between relation phrases and predicates. In the online phase, given a natural language question N, we interpret N as a semantic query graph \(Q^\mathrm{S}\) and find answers to N by matching \(Q^\mathrm{S}\) over RDF graph G.

In this paper, we review our recent work on graph-based RDF data management. Specifically, we give an overview of the systems developed in our project: gStore, gStore-D and gAnswer. The design philosophy behind our systems is to employ graph database techniques for RDF data management. As a native implementation, graph-based approaches maintain the original representation of the RDF data and enforces the intended semantics of RDF and SPARQL. The practice of our projects proved the effectiveness and efficiency of graph-based RDF data management techniques.

We note that gStore is not the only graph-based solution for RDF data management. To the best of our knowledge, GRIN [27] is the first work that considers a graph-structural index. It uses a distance-based height-balanced tree to index the RDF graphs. Specifically, each leaf node contains a set of vertices in RDF graph. The set of leaf nodes in the tree forms a partition of all vertices in RDF graph. Interior nodes are constructed by finding a “central” vertex, denoted c, and a radius value, denoted r. All vertices within the distance r from the center c are included in the interior vertex. Note that if interior node x is a child of y in GRIN tree, all vertices included in x are a subset of that included in y. During query evaluation, GRIN derives a set of inequality constraints based on the query graph structure. For example, if the distance between two query vertices \(v_1\) and \(v_2\) (in Q) is l, the distance between their matching vertices (in RDF graph G) is no longer than l. Based on these inequality constraints, some nodes of the index can be safely pruned to reduce the search space. The intuition of GRIN is similar to M-tree [10] that is designed to support similarity search in metric spaces.

Another system that we would like to mention is Trinity. RDF [34], a distributed, memory-based graph engine for web-scale RDF data. Due to the poor locality of graph operations, it is argued that maintaining the whole RDF graph in a memory cloud is feasible. Instead of join processing, graph exploration is used to boost the system’s performance. The exploration-based approach uses the binding information of the explored subgraphs to prune candidate matches in a greedy manner [34].