Method and Apparatus for Optimizing Queries over Vertically Stored Database

• US 20090132474A1
• Filed: 11/14/2008
• Published: 05/21/2009
• Est. Priority Date: 11/16/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wang, Chen, Ma, Li, Pan, Yue, Yan, Ying
• Granted Patent: US 7,987,179 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24535 of sub-queries or views

Abstract

A method and device for optimizing queries over a vertically stored database. Items in the database are partitioned into several partitions each having a partition signature. The method includes decomposing a first query received from a user into multiple first subqueries; generating a signature for each first subquery in a way corresponding to the way of generating the partition signature; comparing the signature of each first subquery with partition signatures of all partitions respectively to obtain all partitions matching the first subquery; rewriting a second subquery translated from the first subquery based on the matching partitions to obtain a rewritten second subquery; and composing rewritten second subqueries for all first subqueries to form a second query so that queries are executed over the database using the second query.

Claims

1. A method for optimizing queries over a vertically stored database having items that are partitioned into several partitions each having a partition signature representing items therein, the method comprising:

decomposing a first query received from a user into multiple first subqueries;

generating a signature for each first subquery in a way corresponding to the way of generating the partition signature;

comparing the signature of each first subquery with partition signatures of all partitions, in order to obtain all partitions matching the first subquery;

rewriting a second subquery translated from the first subquery based on the matching partitions, in order to obtain a rewritten second subquery; and

composing rewritten second subqueries for all first subqueries to form a second query so that queries are executed over the database using the second query.

2. The method according to claim 1, wherein the first query and first subqueries are SPARQL queries, and the second subqueries and second query are SQL queries.

3. The method according to claim 1, wherein the database is an RDF store in which each item contains RDF triples, the RDF store contains a subject column whose value represents RDF triple subjects, a property column whose value represents RDF triple properties, and an object column whose value represents RDF triple objects, and the RDF store further contains a unique identifier column whose value represents partitions where corresponding RDF triples are located.

4. The method according to claim 3, wherein all items in the RDF store are mapped to a graph representing all RDF triples, RDF triple subjects are represented by source nodes in the graph, RDF triple objects by sink nodes in the graph, and RDF triple properties by directed connections from source nodes to sink nodes, and the graph is partitioned into several subgraphs each corresponding to a partition.

5. The method according to claim 4, wherein connections within subgraphs are denser, connections between subgraphs are sparser, and for each connection between subgraphs, a copy of the connection is made in each of related subgraphs so that subgraphs can reflect all data relationships in the RDF store after the partition.

6. The method according to claim 1, wherein the partition signature is obtained in such a way that a signature is generated for each item in a partition using hash functions and that an “

OR”

operation is performed on the signature of each item.

7. The method according to claim 1, wherein the decomposing step further comprises:

mapping the first query to a query graph, and

enumerating 2-reachable subgraphs corresponding to a first subquery in the query graph.

8. The method according to claim 1, wherein the signature for each first subquery is generated via the same hash functions as those for generating the partition signature.

9. The method according to claim 8, wherein the hash functions are MD5 hash functions.

10. The method according to claim 9, wherein when positions of 1 in the signature generated for a first subquery are also set to 1 in the signature of a partition, the first subquery matches the partition.

11. The method according to claim 1, wherein the query process ends in advance if no partition matching the first subquery is obtained in the obtaining step.

12. The method according to claim 1, wherein the partition has a unique identifier, and the rewriting step further comprises:

creating a temp table for storing unique identifiers of all partitions matching the first subquery, and

rewriting the second subquery using additional join conditions related to the temp table where unique identifiers are stored.

13. The method according to claim 1, wherein when the number of partitions matching the first subquery is larger than a predetermined value, the rewriting step comprises:

creating a temp table for storing unique identifiers of all partitions matching the first subquery, and

rewriting the second subquery using additional join conditions related to the temp table where unique identifiers are stored; and

when the number of partitions matching the first subquery is less than a predetermined value, the rewriting step comprises;

rewriting the second subquery using additional restraints on partitions matching the subquery.

14. A method for processing a vertically stored database, the method comprising:

partitioning all items in the database into several partitions;

assigning each partition with a unique identifier; and

generating a signature for each partition.

15. The method according to claim 14, wherein the database is an RDF store in which each item contains RDF triples, the RDF store contains a subject column whose value represents RDF triple subjects, a properties column whose value represents RDF triple properties, and an object column whose value represents RDF triple objects, and the RDF store further contains a unique identifier column whose value represents partitions where corresponding RDF triples are located.

16. The method according to claim 15, wherein the partitioning step comprises:

mapping all items in the RDF store to a graph representing all RDF triples, wherein RDF triple subjects are represented by source nodes in the graph, RDF triple objects by sink nodes in the graph, and RDF triple properties by directed connections from source nodes to sink nodes, and

partitioning the graph into several subgraphs each corresponding to a partition.

17. The method according to claim 16, wherein connections within subgraphs are denser, connections between subgraphs are sparser, and for each connection between subgraphs, a copy of the connection is made in each of related subgraphs so that subgraphs can reflect all data relationships in the RDF store after the partition.

18. The method according to claim 14, wherein the partition signature is obtained in such a way that a signature is generated for each item in a partition using hash functions and that an “

OR”

operation is performed on the signature of each item.

19. The method according to claim 18, wherein the hash functions are MD5 hash functions.

20. A device for optimizing queries over a vertically stored database, wherein items in the database are partitioned into several partitions each having a partition signature representing items in it, the device comprising:

decomposing means for decomposing a first query received from a user into multiple first subqueries;

query signature generating means for generating a signature for each first subquery in a way corresponding to the way of generating the partition signature;

partition obtaining means for comparing the signature of each first subquery with partition signatures of all partitions, in order to obtain all partitions matching the first subquery;

query rewriting means for rewriting a second subquery translated from the first subquery based on the matching partitions, in order to obtain a rewritten second subquery; and

query composing means for composing rewritten second subqueries for all first subqueries to form a second query, whereby queries are executed over the database using the second query.

21. A device for processing a vertically stored database, the device comprising:

partitioning means for partitioning all items in the database into several partitions;

assigning means for assigning each partition with a unique identifier; and

partition signature generating means for generating a signature for each partition.