CN107291807B - SPARQL query optimization method based on graph traversal - Google Patents

Abstract

The invention discloses a SPARQL query optimization method based on graph traversal. The method is as follows: 1) Use the attribute graph to represent the triples in the RDF data, and then use the Bigtable model to store the RDF data to obtain the Bigtable data corresponding to the RDF data; 2) Convert the SPARQL query to traverse the RDF attribute graph; 3) According to the steps 2) The obtained traversal sequence traverses all nodes in the Bigtable data that meet the conditions, and completes the SPARQL query. On the one hand, the invention eliminates the dependence of traditional SPARQL query on data structures such as Hash, reduces the generation of intermediate data, and avoids the connection calculation of large-scale RDF data; on the other hand, it can effectively use Bigtable-based big data processing technology to store and Manage the massive amount of RDF related knowledge network data, and accelerate the query and analysis of RDF related data.

Description

A SPARQL Query Optimization Method Based on Graph Traversal

technical field

The invention relates to a SPARQL query execution method based on graph traversal, in particular to a method and system for storing and querying big data association.

Background technique

Graph data mining and analysis is a new field of big data. It supports information mining and scientific discovery based on data association by establishing association relationships between World Wide Web resources, microbial strain resources, and scientific research resources. Resource Description Framework (RDF) is a language used to express information about World Wide Web (World Wide Web) resources, capable of expressing any information that can be identified on the Internet, such as page title, author and modification time and the relationship between different data. The RDF specification provides a basic vocabulary for describing resources, and defines the rules that must be followed when applications in various fields such as WDCM (Mircen World Data Centre for Microorganisms) microbial description resource vocabulary. SPARQL (SPARQL Protocol and RDF Query Language) is a query language and data acquisition protocol developed for RDF. It is defined by the RDF data model recommended by the W3C International Standards Organization and is used to query any information resources that can be represented by RDF. The SPARQL Protocol and RDF Query Language (SPARQL) officially became a W3C Recommendation on January 15, 2008.

Because RDF uses structured XML data, retrieval and query can understand the precise meaning of metadata, and search becomes more intelligent and accurate, effectively avoiding the situation that retrieval often returns irrelevant data. The RDF file contains several resource descriptions, each resource description consists of several statements, and each statement consists of a triplet of resource, attribute type, and attribute value, indicating that the resource has an attribute. A resource corresponds to a subject in natural language, an attribute type corresponds to a predicate, and an attribute value corresponds to an object. Multiple RDF resource files constitute a complete resource description and association graph. With the increasing scale of data in relational networks, more and more data types are expressed and processed, posing challenges to the real-time performance of RDF data storage and SPARQL queries. Therefore, it is very important to adopt a new scalable big data architecture to improve the storage and management efficiency of RDF data, and to improve the SPARQL query speed and analysis capabilities. The graph data storage and management framework based on big graph data processing technologies such as Bigtable has become a new development direction of knowledge graph networks due to its excellent large-scale data processing capabilities.

At present, RDF data mainly uses relational database tables or KV data warehouse to store and manage RDF triples, and realize subgraph matching and SPARQL query of subject, predicate and object of RDF triples through self-connection, and support through Hash or Index Fast query and retrieval of local data, typically implemented as a Virtuoso RDF graph database. Its distributed version mainly adopts the federation method, which integrates the RDF data query and distributed computing framework into a unified framework. Specifically, the SPARQL query is parsed and distributed to each node, and each node runs subgraph matching calculation and then summarizes each node. matching results for each node. The architecture is simple and easy to implement, supports distributed query and fast return of RDF data, and simplifies the design and development of large-scale knowledge association networks.

However, based on the distributed query method of federation and subgraph matching, each query needs to decompose the SPARQL query into subgraph matching and distribute to multiple nodes, run subgraph matching and return the results, which easily leads to a large amount of node communication and intermediate data. . When the data scale is very large, the system faces the following problems:

1) Self-connection operation with high overhead. For distributed systems, the join operation of data tables results in a large amount of data communication between system nodes. When the amount of data is large and there are many machine nodes, the self-connection overhead is large, and the query delay increases significantly, which is not conducive to the horizontal expansion of the system.

2) A large amount of intermediate data. After the SPARQL query is decomposed, it is distributed to multiple nodes to run separately. Each node is equivalent to a query engine. Its operation generates a large amount of intermediate data, which increases the memory consumption of the system and reduces the number of SPARQL processed in parallel by the system.

3) High requirements for data fragmentation. Federated query distributes SPARQL queries to each node for completion, which requires higher quality of data sharding. If there are a large number of associations between different partitions, SPARQL subgraph matching cannot be performed in parallel on multiple data nodes, which reduces the operating efficiency of the system.

Due to the existence of these problems, it is difficult for SPARQL queries based on federated methods to effectively cope with the large-scale growth of large-scale RDF linked data and meet the real-time query requirements of knowledge network linked applications, and the query time increases with the growth of data scale. However, the data processing technology based on Bigtable is difficult to be applied to the processing of massive RDF knowledge network associated data due to the lack of large-scale table join operations.

SUMMARY OF THE INVENTION

Aiming at the problems existing in RDF big data SPARQL query, the purpose of the present invention is to provide a SPARQL query optimization method based on graph traversal.

The technical scheme of the present invention is:

A SPARQL query optimization method based on graph traversal, the steps are:

1) Use the attribute graph to represent the triples in the RDF data, and then use the Bigtable model to store the RDF data to obtain the Bigtable data corresponding to the RDF data;

2) Convert the SPARQL query to the traversal of the RDF property graph;

3) According to the traversal sequence obtained in step 2), traverse all the nodes in the Bigtable data that meet the conditions, and complete the SPARQL query.

The method of using the Bigtable model to store RDF data is as follows:

21) For each RDF triple (sub, pre, obj) in the RDF data, use the subject sub as the node v and store it as a row in the Bigtable model;

22) Determine the type of the object obj: a) If the object obj is rdf:literal, that is, the predicate pre is an attribute of the subject sub, then the object obj is used as the attribute value of the node v, and then the predicate pre is used as the attribute name of the node v , stored as a storage unit Cell of the row where the node v is located; b) If the object obj is rdf:resource, that is, the predicate pre is associated with the subject sub to the edge of other nodes, then the object obj is taken as an independent node w, stored as One row in the Bigtable model; then use the predicate pre as the outgoing edge of the node v, point to the node w, store it as a Cell of the row where the node v is located, and use the predicate pre as the incoming edge of the node w, from the node v, Stored as a Cell of the row where the node w is located.

Further, in step 2), the SPARQL query is converted into Gremlin graph traversal, so as to realize the traversal of the RDF property graph by converting the SPARQL query.

Further, the method for converting a SPARQL query into a Gremlin graph traversal is: for each triple (sub, pre, obj) in the where clause of the SPARQL query, if the triple is the predicate pre, it represents the property in the property graph. The triplet is converted into a filter has(pre,obj) for the node in the attribute graph represented by the subject sub, where obj is the filter condition, and pre is the attribute name represented by the predicate pre; if the triplet The group is a triplet whose predicate pre represents an edge in the attribute graph, then the triplet is converted into a traversal sub.out(pre)->obj from the node represented by the subject sub to the node represented by the object obj, and out represents the edge, pre represents the associated label of the edge represented by the predicate pre; the traversal sequence is obtained by processing all triples of the where clause.

Further, according to the traversal sequence obtained in step 2), the method for traversing all nodes that meet the conditions in the Bigtable data is: the traversing sequence is a traversing sequence composed of filtering and associated edges; first, a traversing path is formed according to the associated edges, and then filtering Eliminate invalid traversal paths to obtain valid traversal paths; then traverse all the nodes in the Bigtable data that meet the conditions according to the valid traversal paths, and then organize the attribute values of the nodes and edges of the valid traversal paths.

The invention includes Bigtable data storage, SPARQL to Gremlin traversal conversion, and Gremlin graph traversal execution.

Its functions are described as follows:

1) Store RDF data based on the Bigtable model

RDF is an Internet-oriented graph data format. It uses <subject, predicate, object> triples to represent graph data, the subject (Subject) represents the graph node, the predicate is the attribute name of the sub subject node, and the corresponding object obj is the attribute . Object mainly includes two cases: rdf:literal and rdf:resource. The former represents the attribute of the subject node, and the attribute name is the predicate; the latter represents other nodes associated with the subject node, and the predicate identifies the edge that the subject is related to other nodes. Edge labels are predicates. The attribute graph corresponding to the RDF graph is shown in Figure 1(a), and its Bigtable representation is shown in Figure 1(b).

The present invention uses Bigtable to store RDF graphs, and for RDF data triples: subject (Subject), predicate (Predicate), object (Object), according to its characteristics and RDF model (that is, RDF ontology), its structure analysis is as follows:

For the "sub pre obj." RDF triple, take the subject sub as the node v, and store it as a row in the Bigtable model.

If the object obj is rdf:literal, the object obj is used as the attribute value of the node v, the predicate pre is used as the attribute name of the node v, and it is stored as a Cell (storage unit) in the row where v is located. Otherwise, store obj as an independent node w as a row in Bigtable. Take the predicate pre as the outgoing edge of the subject sub node v, point to the node w, and store the predicate pre as a Cell in the row where the node v is located; take the predicate pre as the incoming edge of the object obj node w, from the node v (that is, the incoming edge of the predicate pre The starting point is node v), which is stored as a Cell in the row where node w is located.

Among them, rdf:lieral is a type of object, which is parsed by Apache Jena or other RDF tools. Among them, Bigtable is a storage structure for massive data, which can efficiently support the storage and management of massive graph data. 2) Convert SPARQL query to Gremlin graph traversal

As shown in Figure 2, a SPARQL query expresses subgraph matching using a sequence of multiple RDF triples of where clauses. The invention uses graph traversal to realize SPARQL subgraph matching, and converts the triplet sequence in the where clause of the SPARQL query into filtering and traversing of nodes and edges in the graph. For each "sub pre obj." triplet in the where clause, the transformation process is as follows: For the triplet of the attribute in the attribute graph represented by the predicate pre, it is transformed into the filtering of the nodes in the attribute graph represented by sub has(pre,obj), obj is the filter condition, and pre is the attribute name represented by the predicate pre. For the triplet of the edge in the attribute graph represented by the predicate pre, it is converted into the traversal of the node represented by sub to the node represented by obj. The gremlin code is sub.out(pre)->obj, out represents the edge, and pre represents the predicate pre The associated label of the edge represented.

By processing all triples of the where clause, a traversal sequence consisting of filtered and associated edges is obtained.

3) Graph traversal execution

For the traversal sequence obtained in step (2), traverse all nodes that satisfy the conditions in the Bigtable data obtained by storing the RDF data based on the Bigtable model in step 1). Its associated edges make up traversal paths, and filtering is used to eliminate invalid traversal paths. After the traversal is completed, organize the attribute values of the nodes and edges of the valid traversal path, and return them according to user requirements. Due to the direct access to Bigtable, there is basically no intermediate data generated during the query process. The RDF data refers to the graph data representation method defined by the W3C International Standards Organization, using triples to represent the relationship between data and the data, and the subject, predicate, and object refer to the standard data structure of RDF data. The Gremlin refers to a standard language for graph data traversal.

The beneficial effects of the present invention are:

Aiming at the problems of poor scalability and low query efficiency of large-scale RDF graph data storage, a method for storing and querying RDF graph data based on Bigtable is proposed. Horizontal expansion of graph data; by converting SPARQL queries into Bigtable data access based on graph traversal, the problems of high overhead and poor scalability caused by RDF data connections are avoided, and the generation of intermediate data in the query process is reduced. And because the SPARQL query process is converted into Bigtable access, the cache can be used to reduce the number of accesses.

The invention solves the problems of distributed storage and low-latency query of massive large-scale RDF data, on the one hand, it eliminates the dependence of traditional SPARQL query on data structures such as Hash, reduces the generation of intermediate data, and avoids the connection of large-scale RDF data On the other hand, it can effectively use Bigtable-based big data processing technology to store and manage massive RDF related knowledge network data, and use caching technology and indexing technology to accelerate RDF related data query and analysis.

Description of drawings

Figure 1 is a representation of storing RDF data based on the Bigtable model;

(a) RDF data attribute graph, (b) RDF data graph based on Bigtable model;

Fig. 2 is the SPARQL query execution flow chart based on graph traversal;

Figure 3 is a comparison diagram of small data sets vs large data sets.

Detailed ways

In order to make the above-mentioned features and advantages of the present invention more obvious and easy to understand, the following embodiments are given and described in detail with the accompanying drawings as follows.

As shown in Figure 2, a graph traversal-based SPARQL execution engine consists of Bigtable data storage, SPARQL to Gremlin conversion, and graph traversal execution. According to the rdf:literal and rdf:resource characteristics of the object of the RDF triplet, the invention uses the attribute graph to represent the association relationship and literal value of the RDF triplet, uses the Bigtable data model to store and manage the RDF data, and uses the graph traversal to realize the SPARQL pairing Query and analysis of RDF linked data.

At present, the data warehouse for RDF data uses triples as the basic unit to store and manage RDF knowledge network data, and relies on table self-connection to achieve subgraph matching, thereby realizing SPARQL query and analysis of RDF data.

The present invention uses Bigtable to store and manage RDF data, converts SPARQL query and analysis into traversal of RDF attribute graph, and completes SPARQL query through Bigtable access. In this way, the present invention realizes the distributed expansion of the RDF massive data, and avoids the adverse effect of the connection operation on the SPARQL query. The following describes the Bigtable storage of RDF data and the SPARQL to Gremlin conversion designed as shown in Figure 1 to support fast retrieval and analysis of RDF data:

Bigtable data storage: As shown in Figure 1, for the RDF triple data, it is represented as an attribute graph as shown in Figure 1(a). For example, "<tax1><type><taxNode>.", whose object type is rdf:literal, is converted into the attribute value of the node represented by the subject tax1, and the attribute name is the predicate; "<tax1><x-taxon><gene1 >.", its object is rdf:resource, then the node represented by the subject tax1 points to the edge of the gene1 node represented by the object, and the predicate is the label of the edge, so that all the RDF triples and attribute graphs correspond, and use Bigtable data structures store attributes and edges.

SPARQL to Gremlin: Convert triples of where clauses in SPARQL queries into traversal of property graphs, where SPARQL is a query language for RDF data, and Gremlin is a traversal language for property graphs.

For the triplet "?tax<type><taxNode>." of the where clause, since type represents an attribute in the attribute graph, the association is converted into the filter has(type,taxNode)step of the node attribute type in gremlin , whose execution process is to filter BigTable data according to taxNode, reduce the traversal range and improve the traversal efficiency.

For "?tax<x-taxon>?gene.", since x-taxon is an edge between nodes in the attribute graph, this association is transformed into a traversal out(x- taxon) step, which implements this traversal through access to Bigtable data.

The invention selects the 300 million scale small data set, 3 billion scale large data set and 16 standard SPARQL queries of the microbial association data set WDCM to test the invention, and provides a big data-oriented graph traversal based method proposed in the invention to test the invention. A specific implementation process of the SPARQL execution engine, the query repetition process is 10 times, and the maximum and minimum values are removed.

The test environment is 4 HBase clusters that support BigTable. The HBase version is 0.98.23.hadoop1. Each node has 32G memory, 12-core CPU, and 28T disk. The nodes are interconnected through 10G switches. The Gremlin query and analysis engine is Titan 1.0.0, and the SparQLToGremlin conversion is developed by the project team.

The query running time obtained using the system of the present invention is as follows:

As shown in Figure 3, for a small dataset with a scale of 300 million, the query takes about 1s.

For a large data set with a scale of 3 billion triples, since the graph traversal load is effectively distributed in multiple nodes, the time required for 16 query statements is less than 1s, which is better than the query time of small data sets.

The experimental results show that, for the increasing RDF data, the present invention can effectively utilize the advantages of Bigtable distributed data storage and graph traversal query, keep the query time constant, and solve the current SPARQL query time when the RDF data increases on a large scale. Significantly increased problems.

The above implementation is only used to illustrate the technical solution of the present invention and not to limit it. Those of ordinary skill in the art can modify or equivalently replace the technical solution of the present invention without departing from the spirit and scope of the present invention. Protection of the present invention The scope should be as stated in the claims.

Claims (4)

1. A SPARQL query optimization method based on graph traversal comprises the following steps:

1) representing the triples in the RDF data by using the attribute map, and then storing the RDF data by using a Bigtable model to obtain Bigtable data corresponding to the RDF data;

2) converting the SPARQL query into traversal of the RDF attribute graph;

3) traversing all nodes meeting the conditions in the Bigtable data according to the traversal sequence obtained in the step 2), and completing SPARQL query;

the method for storing RDF data by using the Bigtable model comprises the following steps: 21) for each RDF triple (sub, pre, obj) in the RDF data, storing a subject sub as a node v as one line in a Bigtable model; 22) judging the type of the object obj: a) if the object obj is rdf, i.e. the predicate pre is the attribute of the subject sub, taking the object obj as the attribute value of the node v, and then taking the predicate pre as the attribute name of the node v to be stored as a storage unit Cell in the row of the node v; b) if the object obj is rdf, resource, namely the predicate pre is the edge of the subject sub associated to other nodes, the object obj is taken as an independent node w and is stored as one line in the Bigtable model; then, the predicate pre is taken as the outgoing edge of the node v, points to the node w, and is stored as a Cell of the row where the node v is located, and the predicate pre is taken as the incoming edge of the node w, comes from the node v, and is stored as a Cell of the row where the node w is located.

2. The method of claim 1, wherein in step 2), converting the SPARQL query into a Gremlin graph traversal, implements converting the SPARQL query into a traversal of the RDF attribute graph.

3. The method of claim 2, wherein the method of translating the SPARQL query into a Gremlin graph traversal is by: for each triple (sub, pre, obj) in the where clause of the SPARQL query, if the triple is a triple in which a predicate pre represents an attribute in an attribute graph, converting the triple into a filter has (pre, obj) of a node in the attribute graph represented by a subject sub, where obj is a filter condition and pre is an attribute name represented by the predicate pre; if the triple is a triple of which the predicate pre represents an edge in the attribute graph, converting the triple into traversal sub.out (pre) - > obj from a node represented by the subject sub to a node represented by the object obj, wherein out represents the edge, and pre represents an associated label of the edge represented by the predicate pre; and processing all the triples of the where clause to obtain the traversal sequence.

4. The method of claim 1, wherein the method of traversing all nodes satisfying the condition in the Bigtable data according to the traversal sequence obtained in step 2) is: the traversal sequence is formed by filtering and associated edges; firstly, forming a traversal path according to the associated edges, and then eliminating an invalid traversal path by filtering to obtain an effective traversal path; and traversing all nodes meeting the conditions in the Bigtable data according to the effective traversal path, and then organizing the attribute values of the nodes and edges of the effective traversal path.

Images