Prefetching RDF triple data

Patent metadata

Field	Value
Publication number	US-10831767-B2
Application number	US-201615350062-A
Country	US
Kind code	B2
Filing date	Nov 13, 2016
Priority date	Nov 29, 2010
Publication date	Nov 10, 2020
Grant date	Nov 10, 2020

Abstract

Query requests for RDF triples are obtained, wherein the query request(s) contain(s) at least one triple pattern; for each triple pattern, the corresponding elementary pattern is determined, and each triple pattern is converted to a weighted elementary pattern. The occurrence frequency of each elementary pattern is computed based on the weighted elementary patterns; at least one elementary pattern is chosen at least according to the occurrence frequency; and the RDF triples corresponding to the chosen at least elementary pattern are prefetched into the buffer. The corresponding apparatus is also provided. With the above method and apparatus, the frequently accessed RDF triples can be determined and prefetched into the buffer, which improves the query efficiency.

First claim

What is claimed is:

1. A method for accelerating queries and reads of Resource Description Framework triples from a Resource Description Framework data storage system, comprising:
obtaining from a user, via a query engine, query requests for the Resource Description Framework triples, wherein the query requests each contain at least one triple pattern of elements including a subject s, a predicate p, and an object o;
determining elementary patterns corresponding to the triple patterns of the query requests, wherein each of the elementary patterns includes one of the elements of a corresponding triple pattern of a query request denoted as a constant and includes remaining ones of the elements denoted as query variables;
obtaining weighted elementary patterns by performing weighting with respect to the triple patterns corresponding to the elementary patterns;
computing occurrence frequency of the elementary patterns in the query requests based on the weighted elementary patterns; and
prefetching, from the Resource Description Framework data storage system into a buffer, those of the Resource Description Framework triples corresponding to the elementary patterns in decreasing order of the occurrence frequency of the elementary patterns of the query requests, wherein a total size of prefetched ones of the triples corresponding to each of the elementary patterns is less than a size of the buffer.

2. The method of claim 1 , wherein obtaining the query requests for the Resource Description Framework triples comprises reading query request records from a query log.

3. The method of claim 1 , wherein the elementary patterns are in a form of <?s :p ?o>, wherein: denotes p as the query constant and ? denotes s and o as the query variables.

4. The method of claim 1 , wherein the weighting comprises setting a weight of a certain triple pattern with respect to a corresponding elementary pattern as the constant.

5. The method of claim 1 , wherein the weighting comprises determining a weight of the at least one triple pattern with respect to a corresponding one of said elementary patterns by referring to Domain statistics and Range statistics in a Resource Description Framework triple data storage system.

6. The method of claim 5 , wherein computing the occurrence frequency of each of the elementary patterns comprises summing up weights of triple patterns that correspond to a same elementary pattern.

7. The method of claim 1 , wherein computing the occurrence frequency of the elementary patterns comprises, computing the occurrence frequency of the elementary patterns corresponding to the Resource Description Framework triple patterns contained in the query requests based on the occurrence frequency of the query requests.

8. The method of claim 1 , wherein prefetching the Resource Description Framework triples corresponding to the elementary patterns into the buffer comprises maximizing the occurrence frequency of the elementary patterns.

9. The method of claim 1 , wherein the elementary patterns are defined by a data feature in a Resource Description Framework triple data storage system and a request feature of the query requests.

10. An apparatus for accelerating queries and reads of Resource Description Framework triples from a Resource Description Framework data storage system, comprising:
a query obtaining unit, configured to obtain from a user, via a query engine, query requests for Resource Description Framework triples, wherein the query requests contain at least one triple pattern of three elements expressed in the form of subject s, predicate p, and object o;
a pattern analyzing unit, configured to determine a corresponding elementary pattern for each of the at least one triple patterns of the query requests, and convert the at least one elementary pattern to at least one weighted elementary pattern, wherein each elementary pattern includes one of the elements of a corresponding triple pattern of a query request denoted as a constant and includes the others of the elements of the corresponding triple pattern denoted as query variables;
a frequency computing unit, configured to compute the occurrence frequency of each of the elementary patterns based on the occurrences of the weighted elementary patterns in the query requests; and
a data prefetching unit, configured to prefetch, from the Resource Description Framework data storage system into a buffer, those of the Resource Description Framework triples corresponding to the elementary patterns in decreasing order of the occurrence frequency of the elementary patterns of the query requests, in case a total size of the triples corresponding to each of the elementary patterns is less than the size of the buffer;
wherein each of the query obtaining unit, the pattern analyzing unit, the frequency computing unit, and the data prefetching unit comprises at least one of:
dedicated hardware; and
software embodied in a tangible non-transitory storage medium, loaded into a hardware memory, and executing on at least one hardware processor coupled to the memory.

11. The apparatus of claim 10 , wherein the query obtaining unit is configured to read query request records from the query log.

12. The apparatus of claim 10 , wherein the elementary patterns are in the form of <?s :p ?o>, wherein: denotes p as the query constant and ? denotes s and o as the query variables.

13. The apparatus of claim 10 , wherein the pattern analyzing unit is configured to set the weight of certain triple patterns with respect to corresponding elementary patterns as a constant.

14. The apparatus of claim 10 , wherein the pattern analyzing unit is configured to determine the weight of the at least one triple pattern with respect to a corresponding one of the elementary patterns by referring to the statistical information in a Resource Description Framework triple data storage system.

15. The apparatus of claim 10 , wherein the frequency computing unit is configured to sum up the weights of triple patterns corresponding to a same elementary pattern as the occurrence frequency of the same elementary pattern.

16. The apparatus of claim 10 , wherein the frequency computing unit is configured to compute the occurrence frequency of the elementary patterns corresponding to the triple patterns contained in the query requests based on the occurrence frequency of the query requests.

17. The apparatus of claim 10 , wherein the data prefetching unit is configured to make the total size of the Resource Description Framework triples corresponding to the elementary patterns not exceed the buffer size, and make the occurrence frequency of the elementary patterns as high as possible.

18. A method for accelerating queries and reads of Resource Description Framework triples from a Resource Description Framework data storage system, comprising:
obtaining from a user, via a query engine, query requests for the Resource Description Framework triples, wherein the query requests each contain at least one triple pattern of elements including a subject s, a predicate p, and an object o;
determining elementary patterns corresponding to the triple patterns of the query requests, wherein each of the elementary patterns includes one of the elements of a corresponding triple pattern of a query request denoted as a constant and includes remaining ones of the elements denoted as query variables;
obtaining weighted elementary patterns by performing weighting with respect to the triple patterns corresponding to the elementary patterns;
computing occurrence frequency of the elementary

Assignees

• IBM

Inventors

• Pan Yue
• Sun Xing Zhi
• Wang Qing Fa
• Wu Shuo
• Xu Lin Hao

Classifications

• G06F16/9574 Primary

  of access to content, e.g. by caching · CPC title

• G06F16/2455

  Query execution · CPC title

• G06F16/24558

  Binary matching operations · CPC title

• G06F16/24578 Primary

  using ranking · CPC title

• G06F16/2458

  Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries · CPC title