Prefetching RDF triple data

Patent metadata

Field	Value
Publication number	US-9495423-B2
Application number	US-201314049753-A
Country	US
Kind code	B2
Filing date	Oct 9, 2013
Priority date	Nov 29, 2010
Publication date	Nov 15, 2016
Grant date	Nov 15, 2016

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 processing Resource Description Framework triples, comprising:
obtaining query requests for Resource Description Framework triples, wherein said query requests each contain at least one triple pattern;
determining elementary patterns corresponding to said triple patterns;
performing weighting with respect to said corresponding elementary patterns to weighted elementary patterns;
computing occurrence frequency of said elementary patterns based on the weighted elementary patterns; and
prefetching those of the Resource Description Framework triples corresponding to said elementary patterns into a buffer if the occurrence frequency of said elementary patterns meets at least one predetermined condition;
wherein said weighting comprises determining weight of said at least one triple pattern with respect to a corresponding one of said elementary patterns by referring to statistical information in an Resource Description Framework triple data storage system; and
wherein said weighting comprises:
setting the weight w (p, o) of triple patterns in <?s :p :o> form with respect to elementary patterns in <?s :p ?o> form as: w(p,o)=Num(p,o)/FACT(p),
setting the weight w (s, p) of triple patterns in <:s :p ?o> form with respect to elementary patterns in <?s :p ?o> form as: w(s,p)=Num(s,p)/FACT(p),
wherein Num(p,o) denotes the number of all triples with predicate p and object o, Num(s,p) denotes the number of all triples with predicate p and subject s, FACT(p) denotes the number of all triples with predicate p in said Resource Description Framework triple data storage system.

2. A method for processing Resource Description Framework triples, comprising:
obtaining query requests for Resource Description Framework triples, wherein said query requests each contain at least one triple pattern;
determining elementary patterns corresponding to said triple patterns;
performing weighting with respect to said corresponding elementary patterns to weighted elementary patterns;
computing occurrence frequency of said elementary patterns based on the weighted elementary patterns; and
prefetching those of the Resource Description Framework triples corresponding to said elementary patterns into a buffer if the occurrence frequency of said elementary patterns meets at least one predetermined condition;
wherein said weighting comprises determining weight of said at least one triple pattern with respect to a corresponding one of said elementary patterns by referring to statistical information in an Resource Description Framework triple data storage system; and
wherein said weighting comprises:
setting the weight w (p, o) of triple patterns in <?s :p :o> form with respect to elementary patterns in <?s :p ?o> form as:

w
⁡

(

p
,
o

)

=

MIN
⁡

(

DOM
⁡

(
p
)

,

DOM
⁡

(
o
)

)

FACT
⁡

(
p
)

setting the weight w (s, p) of triple patterns in <:s :p ?o> form with respect to elementary patterns in <?s :p ?o> form as:

w
⁡

(

s
,
p

)

=

MIN
⁡

(

RNG
⁡

(
s
)

,

RNG
⁡

(
p
)

)

FACT
⁡

(
p
)

wherein DOM (p) denotes the number of different subjects with predicate p;
DOM (o) denotes the number of different subjects with object o;
RNG(s) denotes the number of different objects with subject s;
RNG(p) denotes the number of different objects with predicate p; and FACT (p) denotes the number of all triples with predicate p in said Resource Description Framework triple data storage system.

3. An apparatus for processing Resource Description Framework triples, comprising:
a query obtaining unit, configured to obtain the query requests for Resource Description Framework triples, wherein said query requests contain at least one triple pattern;
a pattern analyzing unit, configured to convert said at least one triple pattern to a weighted elementary pattern;
a frequency computing unit, configured to compute the occurrence frequency of said elementary patterns based on the weighted elementary patterns; and
a data prefetching unit, configured to prefetch the Resource Description Framework triples corresponding to said elementary patterns into the buffer if the occurrence frequency of said elementary patterns meets certain condition;
wherein each of said query obtaining unit, said pattern analyzing unit, said frequency computing unit, and said data prefetching unit comprises at least one of:
dedicated hardware; and
software tangibly embodied in a non-transitory storage medium, loaded into a hardware memory, and executing on at least one hardware processor coupled to the memory;
wherein said pattern analyzing unit is configured to, determine the weight of said at least one triple pattern with respect to a corresponding one of said elementary patterns by referring to the statistical information in an Resource Description Framework triple data storage system; and
wherein said pattern analyzing unit is configured to:
set the weight w (p, o) of triple patterns in <?s :p :o> form with respect to elementary patterns in <?s :p ?o> form as: w(p,o)=Num(p,o)/FACT(p), and
set the weight w (s, p) of triple patterns in <:s :p ?o> form with respect to elementary patterns in <?s :p ?o> form as: w(s,p)=Num(s,p)/FACT(p),
wherein Num(p,o) denotes the number of all triples with predicate p and object o, Num(s,p) denotes the number of all triples with predicate

Assignees

• IBM

Inventors

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

Classifications

• G06F17/30533

  Physics · mapped topic

• G06F17/3053 Primary

  Physics · mapped topic

• G06F17/30902

  Physics · mapped topic

• G06F16/9574 Primary

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

• G06F16/2458

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