WO2018214097A1 - Ksp algorithm-based resource description framework query method and system - Google Patents

Abstract

A KSP algorithm-based resource description framework query method, configured to employ the KSP algorithm to search for a semantic position of a query keyword in an RDF graph. The query method is user-friendly because a user does not need to master a specialized query language and simply needs to input a query keyword. The query method returns a subtree containing all inputted query keywords and near a query position.

Description

Resource description framework query method and system based on KSP algorithm Technical field

The invention relates to a semantic network data retrieval technology, in particular to a resource description framework query method and system based on a KSP algorithm.

Background technique

ResourceDescriptionFramework (RDF) is a general framework for expressing metadata of WEB resources. It uses Uniform Resource Descriptors (URIs) to represent things, and uses simple attributes and attribute values to describe things. RDF represents data as <Subject, predicate, object>, which is used to identify the object as the subject, the part used to distinguish the different attributes of the subject object is the predicate, and the part of the statement used to distinguish the value of each attribute is called the object. Therefore, the RDF knowledge base can also be regarded as a directed graph, where vertices are resources, properties, words, descriptions, and edges are predicates used to describe the relationship between vertices.

The RDF knowledge base can be modeled as a directed graph where the vertices represent entities and the edges represent relationships between entities. In the RDF graph, we call the vertices of the spatial coordinates as the positions. We use v to represent any vertex in the RDF graph and p to represent the position vertex. Each RDF triple corresponds to a directed edge from one entity (subject) to another (object). In order to implement keyword search, each entity corresponds to a document, which is represented by ,, and the document is composed of keywords extracted from the corresponding resources, properties, characters, and descriptions of the entity. The semantic place is a subtree of the RDF graph, which is rooted at the position vertex p and contains all the query keywords. A plurality of semantic locations can be constructed starting from a given position vertex p.

Existing RDF data is accessed using a Structured Query Language, such as SPARQL (Simple Protocol and RDF Query Language). But standard SPARQL queries require the user to fully understand the language itself and understand the data domain. Therefore, SPARQL restricts data access mainly as a data domain expert because it is unfriendly to ordinary users. That is to say, when querying RDF data, the user needs to understand the query language and RDF semantics, otherwise the query cannot be performed.

Summary of the invention

The present invention aims to solve the technical problem in the prior art that requires the user to understand the query language and the RDF semantics, otherwise the query cannot be performed, and provides a resource description framework query method and system based on the KSP algorithm.

An embodiment of the present invention provides a resource description framework query method based on a KSP algorithm for searching a semantic location of a query keyword on an RDF graph by using a KSP algorithm, and the query method includes the following steps:

Initializing the result function H _k , wherein the result function H _{k is} used to save the conditional semantic position QSP, the qualified semantic position QSP is a subtree containing all the query keywords, and k is the number of eligible semantic positions QSP;

According to the preset document inverted index table and the radius word field table corresponding to all the preset query keywords, each keyword in the query keyword input by the user is looped through, and the input query keyword is inverted. Arranging the index table, and obtaining the value corresponding to each keyword, and loading it in the radius word field table corresponding to all the preset query keywords;

Constructing a dictionary structure according to the input query keyword and the inverted index table corresponding to the input query keyword, wherein the dictionary structure represents a node containing the input query keyword;

Initializing the value θ of the monotonic sort function, wherein the monotonic sort function represents sorting the plurality of most compact and eligible semantic positions searched according to the input query key, the most compact and eligible semantic position being represented as p root node The semantic location of the point with the least degree of looseness;

The root node enters the queue in the preset spatial index, and obtains the location node queue Q;

According to the input query keyword and the location node queue Q, traversing the preset spatial index to obtain the node e, and determining the node e;

When the node e is a vertex containing the spatial location information, it is determined whether e is a non-conforming conditional node. If e is a non-conforming conditional node, the current loop is terminated, and the next loop is entered, when the node e is a vertex containing the spatial location information, and When it is judged that the node e is not a non-conforming condition node, the function GETSEMANTICPLACE is executed to obtain the looseness value L(T _p ) of the subtree T _p and the subtree T _p of the semantic position that meet the condition, and determine whether it is L(T _p )= = + ∞, if so, the end of this cycle, and if not, calculating bulk value L (T _p) a ranking score f, and the bulk value L (T _p) and inserted into the corresponding ranking score for the result function H f _k and update the value θ of the monotonic sorting function;

和对应半径字的排序分数

当

时，则把对应节点e插入位置节点队列Q并返回所述根据输入的查询关键字和位置节点队列Q，在预设的空间索引中查找节点e的步骤，直到

When the node e is the node N, it loops through each node under the node N, and calculates the looseness value of the radius word corresponding to each node e under N.

And the sorting score of the corresponding radius word

when

And inserting the corresponding node e into the location node queue Q and returning the step of searching for the node e in the preset spatial index according to the input query keyword and the location node queue Q until

The query result is returned to the user according to the stored result function H _k .

The present invention further provides an KSP algorithm-based resource description framework query system for searching a semantic location of a query keyword on an RDF graph by using a KSP algorithm, the query system comprising:

The first initialization module is configured to initialize the storage result function H _k , wherein the storage result function H _{k is} used to save the conditional semantic position QSP, the qualified semantic position QSP is a subtree containing all query keywords, and k is a condition The number of semantic locations QSP;

The loop traversal module is configured to cycle through each keyword in the query keyword input by the user according to the preset document inverted index table and the preset radius word domain table corresponding to all the query keywords, and obtain the input Querying the inverted index table corresponding to the keyword, and obtaining the value corresponding to each keyword, and loading the radius word field table corresponding to all the preset query keywords;

a building module, configured to construct a dictionary structure according to the input query keyword and the inverted index table corresponding to the input query keyword, wherein the dictionary structure represents a node that includes the input query keyword;

a second initialization module for initializing the value θ of the monotonic sort function, wherein the monotonic sort function represents sorting the plurality of most compact and eligible semantic positions searched according to the input query keyword, the most compact and eligible semantic position Expressed as the semantic location with the least looseness of the root node with p as the root;

Generating a queue module, the root node for the preset spatial index enters the queue, and obtains the location node queue Q;

The lookup loop module is configured to: according to the input query keyword and the location node queue Q, traverse the preset spatial index to obtain the node e and determine the node e;

The vertex processing module is configured to determine whether the node e is a non-conforming condition node when the node e is a vertex including the spatial location information, and if the node e is not in the conditional node, the current loop is ended, and the next loop is entered, when the node e For the vertex containing the spatial position information, and the node e is not the non-conforming conditional node, the function GETSEMANTICPLACE is executed to obtain the looseness value L(T _p ) of the subtree T _p and the subtree T _p of the semantic position that meet the condition, and determine whether of _{L (T p) == + ∞} , if so, the end of this cycle, and if not, calculating bulk value L (T _p) sorted fraction F, and the bulk value L (T _p) and the corresponding ordering The score f is inserted into the result function H _k and updates the value θ of the monotonic sort function;

和对应半径字的排序分数

当

时，则把对应节点e插入位置节点队列Q并进入查找循环模块，直到

The node processing module is configured to cycle through each node under the node N when the node e is the node N, and calculate the looseness value of the radius word corresponding to each node e under N

And the sorting score of the corresponding radius word

when

Then, the corresponding node e is inserted into the location node queue Q and enters the lookup loop module until

The output result module is configured to return a query result to the user according to the stored result function H _k .

The present invention also provides a computer readable storage medium of an embodiment having stored thereon a computer program that, when executed by a processor, implements the steps of the above method.

Compared with the prior art, the technical solution of the present invention has the beneficial effects that the KSP algorithm is user-friendly, the user does not need to master a special query language, and only needs to input the keyword of the query, and the algorithm will return near the query position. A subtree containing all the keywords.

DRAWINGS

1 is a flow chart of an embodiment of a resource description framework query method based on the KSP algorithm of the present invention.

2 is a flow chart of another embodiment of a resource description framework query method based on the KSP algorithm of the present invention.

3 is a schematic diagram of an embodiment of a document inverted index table of the present invention.

4 is a flow chart of an embodiment of a method for creating a radius word domain table corresponding to all query keywords of the present invention.

FIG. 5 is a schematic structural diagram of an embodiment of a resource description framework query system based on a KSP algorithm according to the present invention.

detailed description

The embodiments of the present invention are described in detail below, and the examples of the embodiments are illustrated in the drawings, wherein the same or similar reference numerals are used to refer to the same or similar elements or elements having the same or similar functions. The embodiments described below with reference to the drawings are intended to be illustrative of the invention and are not to be construed as limiting.

Specifically, the query sequence q in the KSP algorithm is composed of three parts, including a query position q.λ, a query key q.ψ, and a semantic position number k.

Specifically, for a given kSP query sequence q, and an RDF graph G=<V, E>, where V represents the vertex of the RDF graph, E represents the edge of the RDF graph, and the eligible semantic location QSP is a tree T _p = <V', E'>, where the root node of T _p is p and satisfies

For convenience of introduction, <p,(v ₁ ,v ₂ ...)> is used to represent a semantic position, where p is the root node and (v ₁ , v ₂ ...) represents all other vertices. Given a query sequence q there may be multiple eligible semantic locations QSP, the eligible semantic locations QSP have the same root node p, but (v ₁ , v ₂ ...) are different. Thus T _p is also necessary to calculate the bulk of L (T _p).

表示从根节点p到包含关键字t_i的节点v的最短距离，其中t_i∈q.ψ，d(p，v)为p到v的最短距离，所以T_p的松散度值L(T_p)为：

如果松散度越小，根节点和其他节点覆盖了所有输入的查询关键字的相关性越高。因此对于一个给定的位置顶点p，以位置顶点p为根节点，我们要找的是最紧凑的符合条件的语义位置TQSP，表示以p为根节点的松散度值最小的QSP。Specifically, for a given QSP T _p = <V', E'>,

Represents the shortest distance from the root node p to the node v containing the key t _i , where t _i ∈q.ψ, d(p, v) is the shortest distance from p to v, so the looseness value of T _p is L(T _p ) is:

If the looseness is smaller, the correlation between the root node and other nodes covering all of the input query keywords is higher. So for a given position vertex p, with the position vertex p as the root node, we are looking for the most compact and qualified semantic position TQSP, which represents the QSP with the smallest looseness value with p as the root node.

In addition, on the RDF graph, for a given kSP query sequence q, the query result is K TQSPs, and the scores of the K TQSPs are the smallest of all TQSPs, and the looseness L(T _p ) The sorting score f is represented by the function f(L(T _p ), S(q, p)), L(T _p ) is the subtree T _p looseness, and S(q, p) is the q.λ query position and Euclidean distance between p. The function f(L(T _p ), S(q, p)) can be any monotonic ordering function, f(L(T _p ), S(q,p))=L(T _p )×S(q, p).

The KSP algorithm-based resource description framework query method is used to search the semantic position of the query keyword on the RDF graph by using the KSP algorithm. As shown in FIG. 1 , the constructing method includes the following steps:

Step S101, initializing the stored result function _Hk , wherein the stored result function _{Hk is} used to save the conditional semantic position QSP, the qualified semantic position QSP is a subtree containing all query keywords, and k is an eligible semantic position QSP quantity;

Step S102: Looping through each keyword in the query keyword input by the user according to the preset document inverted index table and the preset radius word domain table corresponding to all the query keywords, to obtain the input query keyword. Corresponding inverted index table, and obtaining a value corresponding to each keyword, and loading in a radius word field table corresponding to all preset query keywords;

Step S103, constructing a dictionary structure according to the input query keyword and the inverted index table corresponding to the input query keyword, wherein the dictionary structure represents a node that includes the input query keyword;

Step S104, initializing the value θ of the monotonic sorting function, wherein the monotonic sorting function indicates sorting the plurality of most compact matching conditions according to the input query keyword search, and the most compact and qualified semantic position is represented by p as the root node. The semantic position of the smallest looseness;

Step S105, the root node of the preset spatial index enters the queue, and obtains the location node queue Q;

Step S106, according to the input query keyword and the location node queue Q, traverse the preset spatial index to obtain the node e, and judge the node e. When the node e is a vertex containing the spatial location information, the process proceeds to step S107, where the node e Step N1, proceed to step S111;

Step S107, it is determined whether the node e is a non-conforming conditional node, if yes, the current loop is terminated, the next loop is returned to step S106, and if not, the process proceeds to step S108;

Step S108, executing a function GETSEMANTICPLACE, obtaining a looseness value L(T _p ) of the subtree T _p and the subtree T _p of the semantic position that meet the condition;

Step S109, it is determined whether L (T _p ) == + ∞, if yes, the end of the current loop returns to step S106, and if not, proceeds to step S110;

Step S110; loose calculated value L (T _p) a ranking score f, and the bulkiness value θ L (T _p) and inserted into the corresponding ranking score f for the result and updates monotonic function H _k sort function, the process proceeds to step S115 ;

和节点e对应半径字的排序分数

Step S111, looping through each node N to calculate the looseness value of the radius word corresponding to the node e

And node e correspond to the ranking score of the radius word

如果是，进入步骤S113，如果否，进入步骤S114；Step S112, determining whether

If yes, go to step S113, if no, go to step S114;

时，节点e符合条件，将对应的节点e插入位置节点队列Q，并返回S106；Step S113, when

When the node e meets the condition, insert the corresponding node e into the location node queue Q, and return to S106;

进入步骤S115；Step S114,

Go to step S115;

Step S115, returning the query result to the user according to the deposit result function _Hk , that is, returning a subtree containing all the input query keywords to the user, and the root node of the subtree is close to the query position.

H_k中的元素按照f(L(T_p)，S(q，p))排序；H_k中存放的是QSP，即存放最终的结果，其中QSP为包含所有查询关键字的子树。Step S101, specifically, initializing

H _k elements in accordance with _{f (L (T p),} S (q, p)) sorting; _k stored in the QSP is H, i.e., the final result is stored, wherein QSP subtree containing all of the query keywords.

Step S102 is specifically: looping through each keyword t _i in the query keyword q.ψ, and performing a process: first searching for the value of the keyword t _i from the preset document inverted index table I, And saving, and then loading the value corresponding to the keyword t _i from the preset radius word field table corresponding to all the query keywords, that is, the α-radius word neighborhood table I ^α , and saving.

Step S103, specifically, establishes a dictionary structure _Mq.ψ , and the structure is {node, (t ₁ , t ₂ , . . . )} represents a node containing a query keyword.

In step S104, specifically, θ=+∞ is initialized; θ is the value of Ranking Score f.

In step S105, the preset spatial index is established before the query, so the spatial index corresponding to input different query keywords is the same. In addition, the location node queue Q stores a plurality of location nodes, where the plurality of location nodes meet the query requirements, wherein the location node includes location information, and the ordinary node does not include location information.

Step S106, specifically: the search loop condition is e=GETNEXT(Q, R, q), and the function GETNEXT indicates that the node e is searched by using an enhanced NN algorithm on the R-tree, and if the node e is a position vertex, The vertex including the spatial position information proceeds to step S107, and if the node e is not the position vertex, the process proceeds to step S111.

When the node e is a position vertex, the following processing is performed: first, if the node e does not meet the deletion rule 1, the current loop is skipped and the next loop is entered; again, returning to step S106, a new loop is started; then, the function GETSEMANTICPLACE is executed to obtain value T _p; if _{L (T p) == + ∞} , description is not found, out of this cycle, enters the next cycle; Next, L is calculated (T _p) of the Ranking Score, and L (T _p) And the corresponding Ranking Score f is inserted into H _k , that is, H _k .add(T _p , f); finally, the value of θ is updated, and the flow proceeds to step S115.

删除规则2，接着计算节点e的α-bound on the ranking score

删除规则3，最后根据删除规则2，3可以判定，当

是，对应的节点e符合条件，可以插入队列Q，即

to Q，直到

进入步骤S115。When the node e is the node N, loop through each node e under N to do the following operations; for each node: First, calculate the α-bound on the looseness of the node e

Delete rule 2, and then calculate the α-bound on the ranking score of node e

Delete rule 3, and finally judge according to the deletion rule 2, 3, when

Yes, the corresponding node e meets the condition and can be inserted into the queue Q, that is,

To Q, until

Go to step S115.

Specifically, the conditional semantic position QSP in the storage result function _Hk is sorted according to the sorting score size of the most compact and qualified semantic position.

In a specific implementation, in step S108, the execution function GETSEMANTICPLACE, as shown in FIG. 2, specifically includes:

Step S201, the initialization sub-tree T _p, where, T _p p expressed as a vertex, a sub-tree containing all the query keywords;

Step S202, initializing the looseness value L(T _p ) of the subtree T _p such that L(T _p )=1;

Step S203, the queried keyword q.ψ is saved in the digital set B;

Step S204, starting from the vertex p, using the BFS (breadth-first-search) method to traverse the RDF graph and the number set B is not empty;

Step S205, the obtained embodiment BFS added to the subtree node v in T _p;

Step S206, searching for a query keyword included in the node v in the dictionary structure;

Step S207, it is determined whether the intersection of the query keyword and the number set B included in the node v is empty, if not, proceeds to step S208, and if yes, proceeds to step S209;

Step S208, if no, output L(T _p )=+∞ and T _p =NULL;

Step S209, if yes, obtain the looseness value L(T _p ) of the subtree T _p according to the number of intersection elements of the query key and the number set B included in the node v and the distance between the node v and the vertex p. ;

Step S210, deleting the intersection of the query key and the number set B included in the node v from the digital set B to obtain the current digital set B;

Step S211, whether the current number set B is empty, if not, returns to step S204, and if yes, proceeds to step S208, that is, until the number set B is empty, and outputs L(T _p )=+∞ and T _p = NULL.

Specifically, the calculation formula of step S209 is as follows:

L(T _p )+=|B∩v.ψ _q |×d(p,v);

Where |B∩v.ψ _q | represents the number of elements in the intersection of B and v.ψ _q , and d(p, v) is the shortest distance from the position vertex p to the node v.

That is to say, the KSP algorithm executes the SP and GETSEMANTICPLACE functions to output the returned result of the input query key. The SP function internally calls the GETSEMANTICPLACE function, and the content of the function SP(q, R, G, I, I ^a ) is specifically The process from step S101 to step S115. The content of the function GETSEMANTICPLACE(q.ψ, p, G, M _q.ψ ) is specifically the process of step S201 to step S211, and the function of the function is to output T _p and L(T _p ), where q represents a query sequence. R denotes a preset spatial index, G denotes an RDF graph, I denotes a preset document inverted index table, and I ^α denotes a preset radius word domain table corresponding to all the query keywords.

In a specific implementation, the query method further includes the following steps: creating a preset spatial index. Specifically, before step S101, a preset spatial index is created.

The step of creating a preset spatial index is specifically:

The data containing the coordinate information is extracted from the RDF data to obtain a preset spatial index. Because the RDF graph data is relatively large, in order to improve the speed of the query, the data containing the coordinate information is first extracted from the RDF data, and the preset spatial index R-tree is created, so that the query speed can be effectively improved.

In a specific implementation, the query method further includes the steps of: performing an inverted index on a keyword in a document of each node to obtain a preset document inverted index table, where the format of the inverted index table is (keyword, a node), specifically, before step S101, an inverted index is created for a keyword in a document of each node to obtain a preset document inverted index table I, and the format of the inverted index table of the document is (keyword, node) ),As shown in Figure 3.

In a specific implementation, as shown in FIG. 4, the query method further includes the following steps:

Step S401, traversing the RDF graph by using the BFS method from the vertex p;

Step S402, when traversing to the node v, traversing the keyword t in the document of the node v, if (t, d(p, v)) does not appear in WN(p), then (t, d(p) , v)) added to the radius word field table corresponding to all the preset query keywords, where WN(p) represents the set of the shortest distance from p to each query key t _i {(t _i ,d _g ( p, t _i ))}, d _g (p, t _i ) ≤ α represents the shortest distance from the root node p to the vertex containing the query key t _i , and (t, d(p, v)) represents the vertex v Corresponding document information, including a query keyword t;

Step S403, after obtaining the radius word fields of all the leaf nodes, calculating the value of WN(N) according to the order from the leaf node to the non-leaf node, and WN(N) indicating all the position vertices of the non-leaf node N {p _j } corresponds to the union of WN(p _j ), and the non-leaf node N contains a series of position vertices {p _j };

Step S404, for the non-leaf node N, {e _i } represents the node under N, WN(N) is initialized to be empty, and if (t, d _g (e _i , t)) has no corresponding value in WN(N) Add (t, d _g (e _i , t)) to the radius word field table corresponding to all the preset query keywords, and if there is a value, the value corresponding to the non-leaf node N in the radius word neighborhood table Updated to min(d _g (N,t), d _g (e _i ,t)), where (t,d _g (e _i ,t)) is the keyword t corresponding to the radius word neighborhood table Value.

Specifically, the vertex p may be a root node, and if it is a root node, location information is included. The vertex p can be a node containing location information, so it is all possible nodes containing location information, including the root node. In addition, the preset radius word domain table corresponding to all the query keywords is established according to a tree, wherein the leaf node p and the non-leaf node N in the tree first calculate the value of the leaf node, and then calculate the value. The value of the leaf node, so it is a leaf node to a non-leaf node, is a bottom-up order. For example, the table shown below is the radius word field table corresponding to all the preset query keywords.

Q.ψ Abbey ... Ancient Catholic Roman History ... d _g (p ₁ , t _i ) 0 ... 1 1 1 - ... d _g (p ₂ , t _i ) - ... - 0 0 1 ... d _g (N, t _i ) 0 ... 1 0 0 1 ...

Specifically, the initialization is started, so that the radius word field table corresponding to all the preset query keywords is empty, and the step S401 - step S404 is to fill the table.

Where: abbey, ancient, catholic, roman, history is the keyword in the radius word field table. (t, d(p, v)): In the document information indicating the vertex v, if there is a query keyword t, the corresponding value is inserted into the radius word neighborhood table. (t, d _g (e _i , t)): represents the value of the keyword t in the radius word neighborhood table. Here, e _i is p ₁ , p ₂ in the above table, that is, d _g (e _i , t) is the value corresponding to d _g (p ₁ , t _i ) in the table. Min(d _g (N,t), d _g (e _i ,t)): is the value of d _g (N, t _i ) in the table to remove the minimum value of the column. For example, the column where catholic is located has a value of 1,0 so the value of min(d _g (N,t), d _g (e _i ,t)) is 0, which is the value of d _g (N,t _i ).

Since TQSP is constructed according to the KSP algorithm, the following two situations may be encountered: (i) T _p containing the input query keyword is not found after traversing the graph, (ii) T _{p is} found, but T _p f [theta] is greater than the ranking score (current have been found in the K-th ranking score T _p). Among them, TQSP is the case with the least loose QSP.

表示以p为根节点子树不能包含所有的查询关键字。对于给定的查询关键字序列q.ψ，若

此时的p节点为不符合条件节点。 For the case of (i), in the RDF diagram, let

Indicates that p is the root node. The subtree cannot contain all the query keywords. For a given query keyword sequence q.ψ, if

The p node at this time is a non-compliant node.

For the case of (ii), in order to improve the efficiency of the algorithm, WN(p) is defined, and for the position vertex p, its WN(p) represents the set of the shortest distance from p to each query key t _i {(t _i , d _g (p, t _i ))}, where d _g (p, t _i ) ≤ α, represents the shortest distance from the root node p to the vertex containing the query key t _i .

显然d_g(N，t_i)≤α。Based on the word neighborhood description of a point in the above, we can derive the definition of the word neighborhood of node N, such as the vertex N in the R-tree. Defining WN(N), for node R of R-tree, contains a series of position vertices {p _j }, WN(N) is a series of {(t _i , d _g (N, t _i ))}, where WN(N) is a union of WN(p _j ) corresponding to all position vertices {p _j } under node N, where for each keyword t _i ,

Obviously d _g (N, t _i ) ≤ α.

According to the definition WN(p) and the definition WN(N), the radius word domain table I ^α corresponding to the node may be created, that is, the preset radius word domain table (α-radius word neighborhood table) corresponding to all the query keywords is used to improve Algorithm efficiency.

并且

Further, in order to improve the efficiency of the algorithm, Lemma 1: Since WN(p) represents the alpha-radius word neighborhood of the position fix p. For a given query key q.ψ={t ₁ ,...,t _j ,...t _m }, for the sake of generality, assume that the jth keyword already has a value in WN(p), Then the radius-word looseness (α-bound on the looseness) of T TSP of T _p with p as the root node can be expressed as

and

表示以p为根节点的T_p的TQSP的半径字松散度，则对于给定的查询序列q对应的T_p的半径字排序分数(α-bound on the ranking score)可表示为

且

Lemma 2: Because

P is represented by a radius looseness TQSP word root node of T _p, the radius for a given word ranking score T _p of the query sequence corresponding to q (α-bound on the ranking score ) may be expressed as

And

并且

Lemma 3: Since WN(N) represents the alpha-radius word neighborhood of the vertex N, the query key q.ψ={t ₁ ...,t _j ...,t _m }, in order not to loss of generality, assume that the j-th keyword in the WN (N) has a corresponding value, the node N p is the root node corresponding to T _p can be expressed as all TQSP

and

表示以在节点N下以p为根节点的T_p的TQSP对应的半径字松散度，对于给定的查询序列q，则在节点N下以p为根节点的所有的T_p的半径字松散度可表示为

其中S(q，N)表示q和N之间最小的空间距离，且

Lemma 4: Because

Represented at node N p is the root node in a T _p of a radius corresponding to the word TQSP looseness, for a given query sequence q, at the node N p is the radius at the root of all the word loose T _p Degree can be expressed as

Where S(q,N) represents the smallest spatial distance between q and N, and

According to Lemma 2, we get the deletion rule 2, and according to Lemma 4, the deletion rule 3 is obtained to improve the efficiency of the algorithm. The specific deletion rules are as follows:

表示以p为根节点的T_p的TQSP的α-bound on the ranking score。当

时T_p不是我们要查的结果，p可以被删除。Delete rule 2: For a given query sequence q, θ represents the ranking score of the kth candidate TQSP.

The α-bound on the ranking score of the TQSP representing T _p with p as the root node. when

When T _p is not the result we want to check, p can be deleted.

表示节点N下以p为根节点的T_p的TQSP的α-bound on the ranking score，若

则在N节点下任何节点都不满足条件，N可以被删除。Delete rule 3: For a given query sequence q, θ represents the ranking score of the kth candidate TQSP,

The α-bound on the ranking score of the TQSP representing the T _p at the node N with p as the root node.

Then, under the N node, no node satisfies the condition, and N can be deleted.

The resource description framework query method based on KSP algorithm mainly implements the search of keywords on the graph and the search of keywords on RDF data: due to the friendliness of keyword retrieval, not only users retrieve network data, but also retrieve XML documents. , relational databases, and graphs. Traditionally, the search algorithm converts queries into searches on feature spaces, such as paths, frequent patterns, and sequences. This search algorithm pays more attention to the structure of the graph than to the semantic content of the graph. The query of the keywords on the graph determines a set of densely linked nodes in the graph by utilizing both the content and the link structure. Due to the re-implementation of these two kinds of information, the overall quality of the results can be improved. The search for keywords on RDF data can also provide query efficiency because RDF data is a special type of graph data.

The present invention also provides a computer readable storage medium having stored thereon a computer program that, when executed by a processor, implements the steps of the above method.

In an embodiment of the present invention, a KSP algorithm query system based on a resource description framework is provided for searching a semantic position of a query keyword on an RDF graph by using a KSP algorithm. As shown in FIG. 5, the query system includes:

The first initialization module 51 is configured to initialize the storage result function H _k , wherein the storage result function H _{k is} used to save the conditional semantic position QSP, and the qualified semantic position QSP is a subtree containing all the query keywords, where k is consistent The number of semantic locations of the conditional QSP;

The loop traversing module 52 is configured to cycle through each keyword in the query keyword input by the user according to the preset document inverted index table and the preset radius word domain table corresponding to all the query keywords, and obtain an input. The inverted index table corresponding to the query keyword, and the value corresponding to each keyword, and loaded in the radius word field table corresponding to all the preset query keywords;

The building module 53 is configured to construct a dictionary structure according to the input query keyword and the inverted index table corresponding to the input query keyword, where the dictionary structure represents a node that includes the input query keyword;

The second initialization module 54 is configured to initialize the value θ of the monotonic sorting function, wherein the monotonic sorting function indicates that the most compact and qualified semantic positions searched according to the input query keyword are sorted, and the most compact and qualified semantics The position is expressed as the semantic position with the least looseness of the root node with p;

a generating queue module 55, the root node for the preset spatial index enters the queue, and obtains the location node queue Q;

The lookup loop module 56 is configured to traverse the preset spatial index according to the input query keyword and the location node queue Q Obtaining node e and judging node e;

The vertex processing module 57 determines whether the node e is a non-conforming condition node when the node e is a vertex including the spatial location information, and terminates the current loop if the node e is not in compliance with the conditional node, and enters the next loop, when the node e For the vertex containing the spatial position information, and the node e is not the non-conforming conditional node, the function GETSEMANTICPLACE is executed to obtain the looseness value L(T _p ) of the subtree T _p and the subtree T _p of the semantic position that meet the condition, and determine whether of _{L (T p) == + ∞} , if so, the end of this cycle, and if not, calculating bulk value L (T _p) sorted fraction F, and the bulk value L (T _p) and the corresponding ordering The score f is inserted into the result function H _k and updates the value θ of the monotonic sort function;

和对应半径字的排序分数

当

时，则把对应节点e插入位置节点队列Q并进入查找循环模块，直到

The node processing module 58 is configured to loop through each node under the node N when the node e is the node N, and calculate the looseness value of the radius word corresponding to each node e under N.

And the sorting score of the corresponding radius word

when

Then, the corresponding node e is inserted into the location node queue Q and enters the lookup loop module until

The output result module 59 is configured to return a query result to the user according to the storage result function H _k .

Specifically, the conditional semantic position QSP in the storage result function _Hk is sorted according to the sorting score size of the most compact and qualified semantic position.

In a specific implementation, the vertex processing module 57 is further configured to:

Initializing a subtree T _p , where T _p represents a subtree containing p as a vertex and containing all query keywords;

Initializing the looseness L(T _p ) of the subtree T _p such that L(T _p )=1;

The keyword q.ψ of the query is saved to the number set B;

Beginning with the vertex p using the BFS (breadth-first-search) method to traverse the RDF graph and the number set B is not empty;

BFS way to get added to the subtree of node v in T _p;

Finding a query keyword included in the node v in the dictionary structure;

Determining whether the intersection of the query key and the number set B included in the node v is empty;

If no, the output L(T _p )=+∞ and T _p =NULL;

If yes, according to the number of intersection elements of the query keyword and the number set B of the node v and the distance between the node v and the vertex p, the looseness value L(T _p ) of the subtree T _p is obtained;

Deleting the intersection of the query key and the number set B contained in the node v from the digital set B to obtain the current digital set B;

Whether the current number set B is empty, and if not, performing content that traverses the RDF graph from the vertex p using the BFS (breadth-first-search) method and the number set B is not empty;

If so, the outputs L(T _p )=+∞ and T _p =NULL, that is, until the set of numbers B is empty, the outputs L(T _p )=+∞ and T _p =NULL.

Specifically, the formula for calculating the value of the looseness L(T _p ) of the subtree T _p according to the number of intersection elements of the query key and the number set B of the node v and the distance between the node v and the vertex p is obtained. as follows:

L(T _p )+=|B∩v.ψ _q |×d(p,v);

Where |B∩v.ψ _q | represents the number of elements in the intersection of B and v.ψ _q , and d(p, v) is the shortest distance from vertex p to node v.

In a specific implementation, the query system further includes a creating module for creating a preset spatial index. Specifically, the creation module is also used to:

The data containing the coordinate information is extracted from the RDF data to obtain a preset spatial index. Because the RDF graph data is relatively large, in order to improve the speed of the query, the data containing the coordinate information is first extracted from the RDF data, and the preset spatial index R-tree is created, so that the query speed can be effectively improved.

In a specific implementation, the creating module is further configured to: perform an inverted index on a keyword in a document of each node to obtain a preset reverse index table of the document, where the format of the inverted index table is (keyword, node), As shown in Figure 3.

In a specific implementation, as shown in FIG. 4, the creation module is further used to:

Traversing the RDF graph using the BFS method starting from the position vertex p;

When traversing to node v, traverse the keyword t in the document of node v, if (t,d(p,v)) does not appear in WN(p), then (t,d(p,v) ) is added to the radius word field table corresponding to all the preset query keywords, where WN(p) represents the set of the shortest distance from p to each query key t _i {(t _i ,d _g (p,t _i ))}, d _g (p, t _i ) ≤ α represents the shortest distance from the root node p to the vertex containing the query key t _i , and (t, d(p, v)) represents the document corresponding to the vertex v Information, including the query keyword t;

After obtaining the radius word fields of all the leaf nodes, the value of WN(N) is calculated in the order from the leaf node to the non-leaf node, and WN(N) represents all the position vertices {p _j } under the non-leaf node N. The union of WN(p _j ), the non-leaf node N contains a series of position vertices {p _j };

For a non-leaf node N, {e _i } represents a node under N, and WN(N) is initialized to be empty. If (t, d _g (e _i , t)) has no corresponding value in WN(N), then (t , d _g (e _i , t)) is added to the radius word field table corresponding to all the preset query keywords, and if there is a value, the value corresponding to the non-leaf node N in the radius word neighborhood table is updated to min (d _g (N, t), d _g (e _i , t)), where (t, d _g (e _i , t)) is the value corresponding to the keyword t in the radius word neighborhood table.

Specifically, the vertex p may be a root node, and if it is a root node, location information is included. Vertex p can be a containing bit The node that sets the information, so it is all possible nodes that contain location information, including the root node. In addition, the preset radius word domain table corresponding to all the query keywords is established according to a tree, wherein the leaf node p and the non-leaf node N in the tree first calculate the value of the leaf node, and then calculate the value. The value of the leaf node, so it is a leaf node to a non-leaf node, is a bottom-up order. For example, the table shown below is the radius word field table corresponding to all the preset query keywords.

Q.ψ Abbey ... Ancient Catholic Roman History ... d _g (p ₁ , t _i ) 0 ... 1 1 1 - ... d _g (p ₂ , t _i ) - ... - 0 0 1 ... d _g (N, t _i ) 0 ... 1 0 0 1 ...

Specifically, the initialization is started, so that the radius word field table corresponding to all the preset query keywords is empty, and the working process of creating the module is to fill the table.

Among them: abbey, aneient, catholic, roman, history is the keyword in the radius word field table. (t, d(p, v)): In the document information indicating the vertex v, if there is a query keyword t, the corresponding value is inserted into the radius word neighborhood table. (t, d _g (e _i , t)): represents the value of the keyword t in the radius word neighborhood table. Here, e _i is p ₁ , p ₂ in the above table, that is, d _g (e _i , t) is the value corresponding to d _g (p ₁ , t _i ) in the table. Min(d _g (N,t), d _g (e _i ,t)): is the value of d _g (N, t _i ) in the table to remove the minimum value of the column. For example, the column where catholic is located has a value of 1,0 so the value of min(d _g (N,t), d _g (e _i ,t)) is 0, which is the value of d _g (N,t _i ).

Since TQSP is constructed according to the KSP algorithm, the following two situations may be encountered: (i) T _p containing the input query keyword is not found after traversing the graph, (ii) T _{p is} found, but T _p f [theta] is greater than the ranking score (current have been found in the K-th ranking score T _p). Among them, TQSP is the case with the least loose QSP.

表示以p为根节点子树不能包含所有的查询关键字。对于给定的查询关键字序列q.ψ，若

此时的p节点为不符合条件节点。For the case of (i), in the RDF diagram, let

Indicates that p is the root node. The subtree cannot contain all the query keywords. For a given query keyword sequence q.ψ, if

The p node at this time is a non-compliant node.

For the case of (ii), in order to improve the efficiency of the algorithm, WN(p) is defined, and for the position vertex p, its WN(p) represents the set of the shortest distance from p to each query key t _i {(t _i , d _g (p, t _i ))}, where d _g (p, t _i ) ≤ α, represents the shortest distance from the root node p to the vertex containing the query key t _i .

显然d_g(N，t_i)≤α。Based on the word neighborhood description of a point in the above, we can derive the definition of the word neighborhood of node N, such as the vertex N in the R-tree. Defining WN(N), for node R of R-tree, contains a series of position vertices {p _j }, WN(N) is a series of {(t _i , d _g (N, t _i ))}, where WN(N) is a union of WN(p _j ) corresponding to all position vertices {p _j } under node N, where for each keyword t _i ,

Obviously d _g (N, t _i ) ≤ α.

According to the definition WN(p) and the definition WN(N), the radius word domain table I ^α corresponding to the node may be created, that is, the preset radius word domain table (α-radius word neighborhood table) corresponding to all the query keywords is used to improve Algorithm efficiency.

并且

Further, in order to improve the efficiency of the algorithm, Lemma 1: Since WN(p) represents the alpha-radius word neighborhood of the vertex p. For a given query key q.ψ={t ₁ ,...,t _j ,...t _m }, for the sake of generality, assume that the jth keyword already has a value in WN(p), Then the radius-word looseness (α-bound on the looseness) of T TSP of T _p with p as the root node can be expressed as

and

表示以p为根节点的T_p的TQSP的半径字松散度，则对于给定的查询序列q对应的T_p的半径字排序分数(α-bound on the ranking score)可表示为

且

Lemma 2: Because

P is represented by a radius looseness TQSP word root node of T _p, the radius for a given word ranking score T _p of the query sequence corresponding to q (α-bound on the ranking score ) may be expressed as

And

并且

Lemma 3: Since WN(N) represents the alpha-radius word neighborhood of the vertex N, the query key q.ψ={t ₁ ...,t _j ...,t _m }, in order not to loss of generality, assume that the j-th keyword in the WN (N) has a corresponding value, the node N p is the root node corresponding to T _p can be expressed as all TQSP

and

表示以在节点N下以p为根节点的T_p的TQSP对应的半径字松散度，对于给定的查询序列q，则在节点N下以p为根节点的所有的T_p的半径字松散度可表示为

其中S(q，N)表示q和N之间最小的空间距离，且

Lemma 4: Because

Represented at node N p is the root node in a T _p of a radius corresponding to the word TQSP looseness, for a given query sequence q, at the node N p is the radius at the root of all the word loose T _p Degree can be expressed as

Where S(q,N) represents the smallest spatial distance between q and N, and

According to Lemma 2, we get the deletion rule 2, and according to Lemma 4, the deletion rule 3 is obtained to improve the efficiency of the algorithm. The specific deletion rules are as follows:

表示以p为根节点的T_p的TQSP的α-bound on the ranking score。当

时T_p不是我们要查的结果，p可以被删除。 Delete rule 2: For a given query sequence q, θ represents the ranking score of the kth candidate TQSP.

The α-bound on the ranking score of the TQSP representing T _p with p as the root node. when

When T _p is not the result we want to check, p can be deleted.

表示节点N下以p为根节点的T_p的TQSP的α-bound on the ranking score，若

则在N节点下任何节点都不满足条件，N可以被删除。Delete rule 3: For a given query sequence q, θ represents the ranking score of the kth candidate TQSP,

The α-bound on the ranking score of the TQSP representing the T _p at the node N with p as the root node.

Then, under the N node, no node satisfies the condition, and N can be deleted.

The resource description framework query system based on KSP algorithm mainly implements the search of keywords on the graph and the search of keywords on RDF data: due to the friendliness of keyword retrieval, not only users retrieve network data, but also retrieve XML documents. , relational databases, and graphs. Traditionally, the search algorithm converts queries into searches on feature spaces, such as paths, frequent patterns, and sequences. This search algorithm pays more attention to the structure of the graph than to the semantic content of the graph. The query of the keywords on the graph determines a set of densely linked nodes in the graph by utilizing both the content and the link structure. Due to the re-implementation of these two kinds of information, the overall quality of the results can be improved. The search for keywords on RDF data can also provide query efficiency because RDF data is a special type of graph data.

In the description of the present specification, the description with reference to the terms "one embodiment", "some embodiments", "example", "specific example", or "some examples" and the like means a specific feature described in connection with the embodiment or example. A structure, material or feature is included in at least one embodiment or example of the invention. In the present specification, the schematic representation of the above terms is not necessarily directed to the same embodiment or example. Furthermore, the particular features, structures, materials, or characteristics described may be combined in a suitable manner in any one or more embodiments or examples. In addition, various embodiments or examples described in the specification, as well as features of various embodiments or examples, may be combined and combined.

Although the embodiments of the present invention have been shown and described, it is understood that the above-described embodiments are illustrative and are not to be construed as limiting the scope of the invention. The embodiments are subject to variations, modifications, substitutions and variations.

Claims (10)

A resource description framework query method based on KSP algorithm is characterized in that: for searching a semantic position of a query keyword on an RDF graph by using a KSP algorithm, the query method comprises the following steps: Initializing the result function H _k , wherein the result function H _{k is} used to save the conditional semantic position QSP, the qualified semantic position QSP is a subtree containing all the query keywords, and k is the number of eligible semantic positions QSP; According to the preset document inverted index table and the radius word field table corresponding to all the preset query keywords, each keyword in the query keyword input by the user is looped through, and the input query keyword is inverted. Arranging the index table, and obtaining the value corresponding to each keyword, and loading it in the radius word field table corresponding to all the preset query keywords; Constructing a dictionary structure according to the input query keyword and the inverted index table corresponding to the input query keyword, wherein the dictionary structure represents a node containing the input query keyword; Initializing the value θ of the monotonic sort function, wherein the monotonic sort function represents sorting the plurality of most compact and eligible semantic positions searched according to the input query key, the most compact and eligible semantic position being represented by p as the root node The semantic position of the smallest looseness; The root node enters the queue in the preset spatial index, and obtains the location node queue Q; According to the input query keyword and the location node queue Q, traversing the preset spatial index to obtain the node e, and determining the node e; When the node e is a vertex containing the spatial location information, it is determined whether e is a non-conforming conditional node. If e is a non-conforming conditional node, the current loop is terminated, and the next loop is entered, when the node e is a vertex containing the spatial location information, and When it is judged that the node e is not a non-conforming condition node, the function GETSEMANTICPLACE is executed to obtain the looseness value L(T _p ) of the subtree T _p and the subtree T _p of the semantic position that meet the condition, and determine whether it is L(T _p )= = + ∞, if so, the end of this cycle, and if not, calculating bulk value L (T _p) a ranking score f, and the bulk value L (T _p) and inserted into the corresponding ranking score for the result function H f _k and update the value θ of the monotonic sorting function; When the node e is the node N, it loops through each node under the node N, and calculates the looseness value of the radius word corresponding to each node e under N.

And the sorting score of the corresponding radius word

when

And inserting the corresponding node e into the location node queue Q and returning the step of searching for the node e in the preset spatial index according to the input query keyword and the location node queue Q until

The query result is returned to the user according to the stored result function H _k . The query method according to claim 1, wherein the execution function GETSEMANTICPLACE includes: Initializing the subtree T _p , where T _p represents a subtree containing all the query keywords with p as the position vertex; Initializing the looseness value L(T _p ) of the subtree T _p such that L(T _p )=1; The keyword q.ψ of the query is saved to the number set B; The RDF graph is traversed from the position vertex p using the BFS method and the number set B is not empty; BFS way to get added to the subtree of node v T _p to obtain a sub-tree T _p; Finding a query keyword included in the node v in the dictionary structure; Determining whether the intersection of the query key and the number set B included in the node v is empty; If no, the output L(T _p )=+∞ and T _p =NULL; If yes, according to the number of intersection elements of the query keyword and the number set B included in the node v and the distance between the node v and the position vertex p, the looseness value L(T _p ) of the subtree T _p is obtained, and The intersection of the query key and the number set B contained in the node v is deleted from the number set B, and returns to the step of traversing the RDF graph using the BFS method from the position vertex p and the number set B is not empty until the number set B is empty. The output L(T _p )=+∞ and T _p =NULL. Query method according to claim 2, wherein: the sub-tree T _p obtained according to the distance between the node and the number and position of the vertex v p v node contains the intersection query key element of the set B and digital The formula for calculating the looseness value L(T _p ) is as follows: L(T _p )+=|B∩v.ψ _q |×d(p,v); Where |B∩v.ψ _q | represents the number of elements in the intersection of B and v.ψ _q , and d(p, v) is the shortest distance from p to v. The query method according to claim 1, wherein the conditional semantic position QSP in the deposit result function _Hk is sorted according to the sorting score size of the most compact and eligible semantic position. The query method according to claim 1, wherein the query method further comprises the step of: creating a preset spatial index. The method of claim 5, wherein the step of creating a preset spatial index is specifically: The data containing the coordinate information is extracted from the RDF data to obtain a preset spatial index. The query method according to claim 1, wherein the query method further comprises the steps of: creating an inverted index for keywords in a document of each node to obtain a preset inverted index table of documents, and inverting The format of the index table is (keyword, node). The query method according to claim 1, wherein the query method further comprises the following steps: Traversing the RDF graph using the BFS method starting from the position vertex p; When traversing to node v, traverse the keywords in the document of node v, if (t,d(p,v)) does not appear in WN(p), then (t,d(p,v)) Add to the radius word field table corresponding to all the preset query keywords, where WN(p) represents the set of the shortest distance from the position vertex p to each query key t _i {(t _i ,d _g (p, t _i ))}, d _g (p, t _i ) ≤ α represents the shortest distance from the position vertex p to the vertex containing the query key t _i , and (t, d(p, v)) represents the vertex v corresponding Document information, including the query keyword t; After obtaining the radius word fields of all the leaf nodes, the value of WN(N) is calculated in the order from the leaf node to the non-leaf node, and WN(N) represents all the position vertices {p _j } corresponding to the non-leaf node N. The union of WN(p _j ), the non-leaf node N contains a series of position vertices {p _j }; For a non-leaf node N, {e _i } represents a node under N, and WN(N) is initialized to be empty. If (t, d _g (e _i , t)) has no corresponding value in WN(N), then (t , d _g (e _i , t)) is added to the radius word field table corresponding to all the preset query keywords, and if there is a value, the value corresponding to the non-leaf node N in the radius word neighborhood table is updated to min (d _g (N, t), d _g (e _i , t)), where (t, d _g (e _i , t)) is the value corresponding to the keyword t in the radius word neighborhood table. A resource description framework query system based on KSP algorithm is characterized in that: for searching a semantic position of a query keyword on an RDF graph by using a KSP algorithm, the query system comprises: The first initialization module is configured to initialize the storage result function H _k , wherein the storage result function H _{k is} used to save the conditional semantic position QSP, the qualified semantic position QSP is a subtree containing all query keywords, and k is a condition The number of semantic locations QSP; The loop traversal module is configured to cycle through each keyword in the query keyword input by the user according to the preset document inverted index table and the preset radius word domain table corresponding to all the query keywords, and obtain the input Querying the inverted index table corresponding to the keyword, and obtaining the value corresponding to each keyword, and loading the radius word field table corresponding to all the preset query keywords; a building module, configured to construct a dictionary structure according to the input query keyword and the inverted index table corresponding to the input query keyword, wherein the dictionary structure represents a node that includes the input query keyword; a second initialization module for initializing the value θ of the monotonic sort function, wherein the monotonic sort function represents sorting the plurality of most compact and eligible semantic positions searched according to the input query keyword, the most compact and eligible semantic position Expressed as the semantic location with the least looseness of the root node with p as the root; Generating a queue module, the root node for the preset spatial index enters the queue, and obtains the location node queue Q; The lookup loop module is configured to: according to the input query keyword and the location node queue Q, traverse the preset spatial index to obtain the node e and determine the node e; The vertex processing module is configured to determine whether the node e is a non-conforming condition node when the node e is a vertex including the spatial location information, and if the node e is not in the conditional node, the current loop is ended, and the next loop is entered, when the node e For the vertex containing the spatial position information, and the node e is not the non-conforming conditional node, the function GETSEMANTICPLACE is executed to obtain the looseness value L(T _p ) of the subtree T _p and the subtree T _p of the semantic position that meet the condition, and determine whether of _{L (T p) == + ∞} , if so, the end of this cycle, and if not, calculating bulk value L (T _p) sorted fraction F, and the bulk value L (T _p) and the corresponding ordering The score f is inserted into the result function H _k and updates the value θ of the monotonic sort function; The node processing module is configured to cycle through each node under the node N when the node e is the node N, and calculate the looseness value of the radius word corresponding to each node e under N

And the sorting score of the corresponding radius word

when

Then, the corresponding node e is inserted into the location node queue Q and enters the lookup loop module until

The output result module is configured to return a query result to the user according to the stored result function H _k . A computer readable storage medium having stored thereon a computer program, characterized in that the program, when executed by a processor, implements the steps of the method of any of claims 1-8.

Images