DATABASE CONTROLLER, METHOD, AND PROGRAM FOR HANDLING RANGE QUERIES

• US 20140358949A1
• Filed: 05/23/2014
• Published: 12/04/2014
• Est. Priority Date: 05/29/2013
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: HU, Bo, Carvalho, Nuno
• Granted Patent: US 9,852,182 B2
• Time in Patent Office: Days
• US Class Current: 707/754
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data
• CPC Class Codes: G06F 16/2455 Query execution

Abstract

Embodiments of the present invention include a database controller for a database of information encoded as a set of data items distributed among a plurality of storage units distinguishable from one another by respective identifying information and each data item comprising a value of each of two or more data elements, the set of data items having a prescribed order of the two or more data elements of which the first one or two data elements are assigned as a prefix portion. The database controller comprises:

• • a query receiving module configured to receive a range query specifying a value of the or each of one or more data elements as a search prefix portion which each data item returned as a range query result must include in its prefix portion; an ordered list storage module configured to store an ordered list comprising, for each of the data items from the set of data items individually, the identifying information of the storage unit upon which the data item is stored, the order of the identifying information being determined by an ordering metric applied to the prefix portions of the respective data items; a prefix frequency storage module configured to maintain a frequency record, recording the values of the data elements assigned as prefix portions of the set of data items and the number of data items having each prefix portion; a list position calculating module configured to calculate, based on the frequency record, the one or more list positions in the ordered list at which the identifying information of storage units upon which data items including the search prefix portion in their prefix portion are stored; and a result retrieving module configured to request the data items including the search prefix portion in their prefix portion from the storage units identified in the calculated one or more list positions.

Claims

1. A database controller for a database of information encoded as a set of data items distributed among a plurality of storage units distinguishable from one another by respective identifying information and each data item comprising a value of each of two or more data elements, the set of data items having a prescribed order of the two or more data elements of which the first one or two data elements are assigned as a prefix portion, the database controller comprising:

a query receiving module configured to receive a range query specifying a value of the or each of one or more data elements as a search prefix portion which each data item returned as a range query result must include in its prefix portion;

an ordered list storage module configured to store an ordered list comprising, for each of the data items from the set of data items individually, the identifying information of the storage unit upon which the data item is stored, the order of the identifying information being determined by an ordering metric applied to the prefix portions of the respective data items;

a prefix frequency storage module configured to maintain a frequency record, recording the values of the data elements assigned as prefix portions of the set of data items and the number of data items having each prefix portion;

a list position calculating module configured to calculate, based on the frequency record, the one or more list positions in the ordered list at which the identifying information of storage units upon which data items including the search prefix portion in their prefix portion are stored; and

a result retrieving module configured to request the data items including the search prefix portion in their prefix portion from the storage units identified in the calculated one or more list positions.

2. A database controller according to claim 1, wherein the prefix frequency storage module is configured to maintain the frequency record in an order determined by applying the ordering metric to the prefix portions of the data items;

and

the list position calculating module is configured to calculate a start point of the one or more list positions by summing the numbers of data items having prefix portions preceding the search prefix portion in the order determined by the ordering metric, and to calculate the end point of the one or more list positions by adding the number of data items having prefix portions including the search prefix portion to the start point

3. A database controller according to claim 1, wherein the set of data items is duplicated one or more times, with each duplicate set storing the same database of information as the set of data items and having a different fixed order and different one or two data elements assigned as a prefix portion from that of the set of data items;

the ordered list storage module is configured to store an ordered list for each duplicate set, the ordered list comprising, for each of the data items from the duplicate set of data items individually, the identifying information of the storage unit upon which the duplicate data item is stored, the order of the identifying information being determined by an ordering metric applied to the prefix portions of the respective duplicate data items; and

the prefix frequency storage module is configured to maintain a frequency record for each duplicate set, recording the prefix portions of the duplicate set and the number of duplicate data items having each prefix.

4. A database controller according to claim 3, wherein there are one or two duplicate data item sets, the set of data items and the one or two duplicate sets have different data elements from one another in each position of the respective fixed orders of data elements.

5. A database controller according to claim 3, wherein the list position calculating module is configured to select the frequency record for one of the set of data items or the one or more duplicate sets such that the data elements of which values are recorded in the selected frequency record are the same data elements for which values are specified in the search prefix portion.

6. A database controller according to claim 1, wherein the frequency storage module is configured to store, for each of the one or more frequency records, a prefix search trie for one of the data elements of which values are recorded included in the prefix portions of the frequency record, and for each prefix search trie, a table corresponding to each leaf;

the prefix search trie having a common root for all different values of the data element and a leaf corresponding to each different value of the data element appearing in the data item set or duplicate set;

each leaf stores a number representing the number of data items in the set of data items set or duplicate set having the corresponding value of the data element; and

the table corresponding to each leaf stores a record of values of the other data element in the prefix portion with which the value corresponding to the leaf appears, and for each value of the other data element, a co-occurrence number representing the number of data items in the set of data items or duplicate set having a prefix portion comprising the value corresponding to the leaf and the value of the other data element.

7. A database controller according to claim 6, wherein the table corresponding to each leaf is a hash table.

8. A database controller according to claim 1, wherein the ordered list is periodically updated based on information received from the storage units, and, after each update, each occupied list position in the ordered list is succeeded by a predetermined number of vacant list positions;

and

when a new data item is added to the set of data items or a duplicate set, adding the identifying information of the storage unit upon which the new data item is stored to a vacant list position in the respective ordered list, the vacant list position being determined by applying the ordering metric to the prefix portion of the new data item in relation to the prefix portions of the respective occupied list positions by referring to the prefix frequency storage module, such that the immediately preceding occupied list position stores the identifying information of a data item having a prefix preceding or equal to the prefix of the new data item according to the ordering metric, and the immediately following occupied list position stores the identifying information of a data item having a prefix following or equal to the prefix of the new data item according to the ordering metric.

9. A database controller according to claim 1, further comprising:

an adaptive locator configured to control allocation of data items to storage units, and to update the allocation of data items to storage units; and

an updating module configured to update the one or more ordered lists and the one or more frequency records to reflect the periodical update performed by the adaptive locator.

10. A database controller according to claim 1, wherein the prefix portion is the first two of the three data elements, and the search prefix portion is one or two specified data elements.

11. A database controller according to claim 1, wherein the database of information is a graph database and the set of data items encoding the graph database is a set of triples each comprising a value of each of three triple elements.

12. A data storage system comprising a database controller according to claim 1, and the plurality of storage units.

15. A computer program which, when executed by one or more computing apparatuses, causes the one or more computing apparatuses to function as the database controller according to claim 1.

13. A method for obtaining range query results from a database of information encoded as a set of data items distributed among a plurality of storage units distinguishable from one another by respective identifying information and each data item comprising a value of each of three data elements, the set of data items having a prescribed order of the three data elements of which the first one or two data elements are assigned as a prefix portion, the plurality of storage units being connected to a database controller storing:

an ordered list comprising, for each of the data items from the set of data items individually, the identifying information of the storage unit upon which the data item is stored, the order of the identifying information being determined by an ordering metric applied to the prefixes of the respective data items; and

a frequency record, recording the values of the data elements assigned as prefix portions of the set of data items and the number of data items having each prefix portion;

the method comprising;

receiving a range query specifying a value of the or each of one or more data elements as a search prefix portion which each data item returned as a range query result must include in its prefix portion;

calculating, based on a frequency record, the one or more list positions in the ordered list at which the storage unit IDs of storage units upon which data items including the search prefix portion in their prefix portion are stored; and

requesting data items including the search prefix portion in their prefix portion from the storage units identified in the calculated one or more list positions.

14. A computer program which, when executed by one or more computing apparatuses, causes the one or more computing apparatuses to perform the method according to claim 13.