Supporting imperative graphic queries on a relational database

1. A method for supporting imperative graphic queries on a relational database, comprising:

parsing an imperative graphic query into operations of execution plans;

translating operations of execution plans which are supported by the relational database into common table expression queries;

executing the translated common table expression queries on the relational database;

building a query tree based on the relational database according to translated queries; and

reconstructing the query tree to reduce a total estimated cost according to estimated cost for each node of the query tree,

wherein the query tree is a Left deep join tree,

each connection father node having two child nodes in the left deep join tree indicates a connection operation between two relational data sets,

each non-connection father node having only one child node and this child node indicate a selection or projection operation for one relational data set, respective nodes of the left deep join tree are numbered in post order traversal, and a leftmost child node has a least number, and

wherein the step of reconstructing the query tree to reduce the total estimated cost according to estimated cost for each node of the query tree includes:

a process on each connection father node sequentially in a number order with the connection father node with the least number as a start, wherein the process on one connection father node includes:

estimating the cost for two child trees connected with the connection father node and the cost for obtaining the connection father node by connecting the two child trees; and

determining whether a left child tree and a right child tree are exchangeable by: estimating the cost for the connection father node after exchanging the left and right child trees; and if the cost after exchanging the left and right child trees is reduced, then exchanging the left and right child trees to rewrite a connection order of the connection father node.

2. The method according to claim 1 , further comprising:

translating operations of execution plans which are not supported by the relational database into user-defined function queries; and

executing translated user-defined function queries on the relational database.

3. The method according to claim 2 , further comprising:

translating particular queries among the translated user-defined function queries into common table expression queries.

4. The method according to claim 2 , further comprising:

translating particular queries among the translated user-defined function queries into stored procedure queries.

5. The method according to claim 1 , further comprising:

translating operations of execution plans which are not supported by the relational database into stored procedure queries; and

executing translated stored procedure queries on the relational database.

6. The method according to claim 5 , further comprising:

translating particular queries among the translated common table expression queries into stored procedure queries.

7. The method according to claim 1 , further comprising:

in response to duplicate common table expression queries existing in the translated common table expression queries, combining the duplicate common table expression queries.

8. The method according to claim 1 , wherein the estimated cost for each node is a number of each data set obtained based on statistics on the relational database.

9. The method according to claim 1 , wherein the operations of the execution plans supported by the relational database include one or more of: graph traversal operation and transformation, filtering, and branching operations of the graph traversal operation; and the operations of the execution plans not supported by the relational database include one or more of: path operation, cycle operation, recursive operation, and addition, deletion and alteration operations on graphic data.

10. A system for supporting imperative graphic queries on a relational database, comprising:

means configured to parse an imperative graphic query into operations of execution plans;

means configured to translate operations of execution plans which are supported by the relational database into common table expression queries;

means configured to execute the translated common table expression queries on the relational database;

means configured to build a query tree based on the relational database according to translated queries; and

means configured to reconstruct the query tree to reduce a total estimated cost according to estimated cost for each node of the query tree, wherein the query tree is a Left deep join tree, each connection father node having two child nodes in the left deep join tree indicates a connection operation between two relational data sets, each non-connection father node having only one child node and this child node indicates a selection or projection operation for one relational data set, respective nodes of the left deep join tree are numbered in post order traversal, and a leftmost child node has a least number,

wherein the means configured to reconstruct the query tree to reduce the total estimated cost according to estimated cost for each node of the query tree is configured to:

carry out a process on each connection father node sequentially in a number order with the connection father node with the least number as a start, wherein the process on one connection father node includes:

estimating the cost for two child trees connected with the connection father node and the cost for obtaining the connection father node by connecting the two child trees; and

determining whether a left child tree and a right child tree are exchangeable by: estimating the cost for the connection father node after exchanging the left and right child trees; and if the cost after exchanging the left and right child trees is reduced, then exchanging the left and right child trees to rewrite a connection order of the connection father node.

11. The system according to claim 10 , further comprising:

means configured to translate operations of execution plans which are not supported by the relational database into user-defined function queries; and

means configured to execute translated user-defined function queries on the relational database.

12. The system according to claim 11 , further comprising:

means configured to further translate particular queries among the translated user-defined function queries into common table expression queries.

13. The system according to claim 11 , further comprising:

means configured to further translate particular queries among the translated user-defined function queries into stored procedure queries.

14. The system according to claim 10 , further comprising:

means configured to translate operations of execution plans which are not supported by the relational database into stored procedure queries; and

means configured to execute translated stored procedure queries on the relational database.

15. The system according to claim 14 , further comprising:

means configured to further translate particular queries among the translated common table expression queries into stored procedure queries.

16. The system according to claim 10 , further comprising:

means configured to in response to duplicate common table expression queries existing in the translated common table expression queries, combine the duplicate common table expression queries.