US 9,852,182 B2 · Database controller, method, and program for handling range queries

Abstract

A database controller for a database of data items distributed across a plurality of storage units. The database controller configured to store an ordered list comprising, for each of the data items individually, the identifying information of the storage unit upon which the data item is stored. The database controller configured to maintain a frequency record, recording the values of prefix portions of the data items and the number of data items having each prefix portion. Wherein, the ordered list and the frequency record are ordered by applying the same ordering metric to the prefix portions. The database controller being configured to receive a range query specifying a search prefix portion, to use the frequency record to calculate where to find in the ordered list the identifying information of storage units storing the data items having the search prefix, and using that identifying information to retrieve query results.

Drawings

Drawings are temporarily unavailable. Open the PDF at USPTO

Drawings

Claims12

Dependent claims

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 computing hardware including a processor and a memory coupled to the processor and storing processing instructions which when executed by the processor cause the processor to execute a process, the process 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;
storing an ordered list comprising, for each of the data items from the set of data items individually, the identifying information of a storage unit upon which the data item is stored, the order of the identifying information being determined by an ordering metric applied to prefix portions of the respective data items;
maintaining a frequency record, recording 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 frequency record being maintained in an order determined by applying the ordering metric to the prefix portion of the data items;
calculating, based on the frequency record, one or more list positions in the ordered list at which the identifying information of the plurality of storage units upon which data items including the search prefix portion in their prefix portion are stored, comprising calculating 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 calculating 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;
and
requesting the data items including the search prefix portion in their prefix portion from the plurality of storage units identified in the calculated one or more list positions, wherein the ordered list is periodically updated based on information received from the plurality of 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
the process further comprises, when a new data item is added to the set of data items or a duplicate set, adding the identifying information of a 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 frequency record, 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.

5 more elements

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 a storage unit upon which the data item is stored, the order of the identifying information being determined by an ordering metric applied to prefixes of the respective data items;
and
a frequency record, recording 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, wherein the frequency record is in an order determined by applying the ordering metric to the prefix portions of the data items;
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 the plurality of storage units upon which data items including the search prefix portion in their prefix portion are stored, comprising calculating 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 calculating 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;
and
requesting data items including the search prefix portion in their prefix portion from the plurality of storage units identified in the calculated one or more list positions, wherein the ordered list is periodically updated based on information received from the plurality of 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
the method further comprises, 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 frequency record, 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.

7 more elements

A non-transitory storage medium storing a computer program which, when executed by one or more computing apparatuses, causes the one or more computing apparatuses to perform 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, wherein the frequency record is in an order determined by applying the ordering metric to the prefix portions of the data items;
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 the plurality of storage units upon which data items including the search prefix portion in their prefix portion are stored, comprising calculating 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 calculating 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;
and
requesting data items including the search prefix portion in their prefix portion from the plurality of storage units identified in the calculated one or more list positions, wherein the ordered list is periodically updated based on information received from the plurality of 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
the method further comprises, when a new data item is added to the set of data items or a duplicate set, adding the identifying information of a 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 frequency record, 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.

7 more elements

Dependencies are inferred from the claim text.

Description10,854 words

Summary5,099 words

#This application claims the benefit of European Application No. 13169786.4, filed May 29, 2013, the disclosure of which is incorporated herein by reference.

#The present invention lies in the field of data storage and data mining. In particular, the invention relates to the handling of range queries submitted to a database of information encoded as a set of data items.

#Distributed data stores, for example, graph databases, have been intensively investigated in the past few years. Leading technical solutions include a variety of data partition approaches and/or the data caching solutions that are tuned against particular representations. Both solutions are not ideal. Data partitioning and/or clustering is intrinsically complex and can be NP-complete in general. When using graph representation for an ontology, it is difficult to maintain data balance and minimum data replication across multiple storage units while at the same time ensuring that no knowledge is lost during the distribution process. Therefore, inter sub-graph reference happens frequently leading to a majority of the graph partition and clustering approaches failing to significantly reduce inter data-node communication. Similarly, the widely used caching algorithms are not designed for graph representation. Such problems are not restricted to graph data, and can also arise in the case of other types of distributed data storage.

Brief description of the drawings3 figures

#Features of the present invention will now be described, purely by way of example, with reference to the accompanying drawings, in which:

#FIG. 1 illustrates a data storage system having a database controller embodying the present invention.

#FIG. 2 illustrates a prefix tree in an invention embodiment;

Detailed description5,697 words

#The data storage system comprises a database controller 10 and a plurality of storage units 30.

#The plurality of storage units 30 are in data communication with one another and with the database controller via a wired or wireless network, illustrated as a bus on FIG. 1 for representative purposes. Data connections within the database controller 10 are not illustrated since it is assumed that the individual modules are configured to exchange data as and when they require in performing their functions. The application 20 may be considered as exterior or interior to the data storage system, and is significant as being the source of a range query. It may be that the application 20 is a functional layer operating within the data storage system, for example, a SPARQL query interface, which receives queries from external applications and processes them into a form suitable for forwarding to the query receiving module 12.

#The database controller 10 is a functional entity which is connectable to the storage units storing the encoded database information. In the description of the particular embodiments the database of information is graph data and the data items are triples, which may specifically be RDF triples. The database controller 10 is configured to handle range queries. It may be that other entities are responsible for other database control functions, for example, insertion of new data and data updates, and handling access for applications, so that the database controller 10 embodying the present invention does not necessarily have exclusive control over the database, merely control over some functionality. The database controller 10 may be realized as a dedicated hardware device or by software running on one or more computers, which one or more computers may include servers having storage units storing the triples. The database controller may be a functional module running on a master server or some other centralized device having responsibility for controlling the storage units 30.

Database controller, method, and program for handling range queries

Life of this patent

Database controller, method, and program for handling range queries

Life of this patent

Life of this patent

Abstract

Drawings

Drawings

Claims12

Description10,854 words

Drawings

Classification3 codes

Life of this patent

Description10,854 words