US2012136875A1PendingUtilityA1
Prefetching rdf triple data
Est. expiryNov 29, 2030(~4.4 yrs left)· nominal 20-yr term from priority
G06F 16/9574G06F 16/24558G06F 16/24578G06F 16/2455G06F 16/2458G06F 16/953G06F 16/24539
49
PatentIndex Score
0
Cited by
0
References
0
Claims
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.
Claims
exact text as granted — not AI-modified1 . A method for processing RDF triples, comprising:
obtaining query requests for RDF 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 RDF triples corresponding to said elementary patterns into a buffer if the occurrence frequency of said elementary patterns meets at least one predetermined condition.
2 . The method of claim 1 , wherein obtaining the query requests for the RDF triples comprises reading query request records from a query log.
3 . The method of claim 1 , wherein said elementary patterns are in a form of <?s :p ?o>.
4 . The method of claim 1 , wherein said weighting comprises setting the weight of a certain triple pattern with respect to a corresponding elementary pattern as a constant.
5 . The method of claim 1 , 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 RDF triple data storage system.
6 . The method of claim 5 , 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 RDF triple data storage system.
7 . The method of claim 5 , 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 RDF triple data storage system.
8 . The method of claim 1 , wherein computing the occurrence frequency of said elementary patterns comprises summing up the weights of the same elementary pattern as the occurrence frequency of said elementary pattern.
9 . The method of any one of claim 1 , wherein computing the occurrence frequency of said elementary patterns comprises, computing the occurrence frequency of the elementary patterns corresponding to the triple patterns contained in said query requests based on the occurrence frequency of said query requests.
10 . The method of claim 1 , wherein prefetching the RDF triples corresponding to said elementary patterns into the buffer if the occurrence frequency of said elementary patterns meets at least one predetermined condition comprises making the total size of the RDF triples corresponding to said elementary patterns not exceed the buffer size, and making the occurrence frequency of said elementary patterns as high as possible.
11 . An apparatus for processing RDF triples, comprising:
a query obtaining unit, configured to obtain the query requests for RDF 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 RDF 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.
12 . The apparatus of claim 11 , wherein said query obtaining unit is configured to read query request records from the query log.
13 . The apparatus of claim 11 , wherein said elementary patterns are in the form of <?s :p ?o>.
14 . The apparatus of claim 11 , wherein said pattern analyzing unit is configured to set the weight of certain triple patterns with respect to corresponding elementary patterns as a constant.
15 . The apparatus of claim 11 , 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 RDF triple data storage system.
16 . The apparatus of claim 15 , 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 p and subject s, FACT(p) denotes the number of all triples with predicate p in said RDF triple data storage system.
17 . The apparatus of claim 15 , 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
)
=
MIN
(
DOM
(
p
)
,
DOM
(
o
)
)
FACT
(
p
)
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
)
=
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 RDF triple data storage system.
18 . The apparatus of claim 11 , wherein said frequency computing unit is configured to sum up the weights of the same elementary pattern as the occurrence frequency of said elementary pattern.
19 . The apparatus of claim 11 , wherein said frequency computing unit is configured to compute the occurrence frequency of the elementary patterns corresponding to the triple patterns contained in said query requests based on the occurrence frequency of said query requests.
20 . The apparatus of claim 11 , wherein said data prefetching unit is configured to make the total size of the RDF triples corresponding to said elementary patterns not exceed the buffer size, and make the occurrence frequency of said elementary patterns as high as possible.Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.