Query generation based on a logical data model with one-to-one joins

Patent metadata

Field	Value
Publication number	US-11928114-B2
Application number	US-202016854219-A
Country	US
Kind code	B2
Filing date	Apr 21, 2020
Priority date	Apr 23, 2019
Publication date	Mar 12, 2024
Grant date	Mar 12, 2024

Abstract

Systems and methods for query generation based on a logical data model with one-to-one joins are described. For example, methods may include accessing a join graph representing tables in a database; receiving a first query; selecting a connected subgraph of the join graph that includes the two or more tables referenced in the first query; accessing an indication that a directed edge of the connected subgraph corresponds to a one-to-one join; modifying the connected subgraph based on the indication to obtain a modified subgraph; generating one or more leaf queries based on the modified subgraph; generating a query graph that specifies joining of results from queries based on the one or more leaf queries; invoking a transformed query on the database that is based on the query graph and the queries based on the one or more leaf queries.

First claim

What is claimed is:

1. A method comprising:
accessing a first join graph representing tables in a database, wherein the first join graph has vertices corresponding to respective tables in the database and directed edges corresponding to join relationships, wherein the directed edges are unidirectional;
receiving a first query that references data in two or more of the tables of the database;
selecting a connected subgraph of the first join graph that includes the two or more tables referenced in the first query;
accessing an indication that a directed edge of the connected subgraph corresponds to a one-to-one join;
modifying the connected subgraph based on the indication to obtain a modified subgraph, wherein the modified subgraph has less root tables than the connected subgraph;
generating one or more queries that reference respective subject tables that are each a root table of the modified subgraph or a table including a measure referenced in the first query;
generating a query graph that specifies joining of results based on the one or more queries to obtain a transformed query result for the first query, wherein the query graph has a single root node corresponding to the transformed query result;
invoking a transformed query on the database that is based on the query graph and the one or more queries to obtain the transformed query result; and
presenting data based on the transformed query result.

2. The method of claim 1 , wherein modifying the connected subgraph based on the indication to obtain the modified subgraph comprises:
reversing the direction of the directed edge identified by the indication.

3. The method of claim 1 , wherein modifying the connected subgraph based on the indication to obtain the modified subgraph comprises:
selecting, based on the indication, a second connected subgraph of the connected subgraph that includes only edges that correspond to a one-to-one join; and
iteratively reversing one or more directed edges of the second connected subgraph, including the directed edge identified by the indication, to reduce a number of root tables in the second connected subgraph.

4. The method of claim 1 , wherein modifying the connected subgraph based on the indication to obtain the modified subgraph comprises:
identifying, based on the indication, one or more reversible join paths in the connected subgraph, wherein the one or more reversible joins paths each connect a source vertex corresponding to a root table of the connected subgraph to a destination vertex corresponding to a shared dimension table of the connected subgraph that is shared with another root table of the connected subgraph; and
reversing the direction of at least one of the one or more reversible join paths by reversing one or more directed edges of the connected subgraph that are identified by the indication as corresponding to a one-to-one join.

5. The method of claim 4 , wherein reversing the direction of the at least one of the one or more reversible join paths comprises:
checking that the root table of the at least one of the one or more reversible join paths is still a root table of the modified subgraph; and
checking that the shared dimension table corresponding to the destination vertex of the at least one of the one or more reversible join paths would not become a root table of the modified subgraph.

6. The method of claim 1 , wherein modifying the connected subgraph based on the indication to obtain the modified subgraph comprises:
merging two vertices of the connected subgraph that are connected by the directed edge identified by the indication.

7. The method of claim 1 , wherein the indication includes a data structure in a data model representing tables in the database.

8. The method of claim 1 , wherein the indication includes a data structure in a schema of the database.

9. A system, comprising:
a network interface,
a processor, and
a memory, wherein the memory stores instructions executable by the processor to:
access a first join graph representing tables in a database, wherein the first join graph has vertices corresponding to respective tables in the database and directed edges corresponding to join relationships, wherein the directed edges are unidirectional;
receive a first query that references data in two or more of the tables of the database;
select a connected subgraph of the first join graph that includes the two or more tables referenced in the first query;
access an indication that a directed edge of the connected subgraph corresponds to a one-to-one join;
modify the connected subgraph based on the indication to obtain a modified subgraph;
generate one or more queries that reference respective subject tables that are each a root table of the modified subgraph or a table including a measure referenced in the first query;
generate a query graph that specifies joining of results based on the one or more queries to obtain a transformed query result for the first query, wherein the query graph has a single root node corresponding to the transformed query result; and
invoke a transformed query on the database that is based on the query graph and the one or more queries to obtain the transformed query result.

10. The system of claim 9 , wherein the memory stores instructions executable by the processor to modify the connected subgraph based on the indication to obtain the modified subgraph by performing operations including:
reversing the direction of the directed edge identified by the indication.

11. The system of claim 9 , wherein the memory stores instructions executable by the processor to modify the connected subgraph based on the indication to obtain the modified subgraph by performing operations including:
selecting, based on the indication, a second connected subgraph of the connected subgraph that includes only edges that correspond to a one-to-one join; and
iteratively reversing one or more directed edges of the second connected subgraph, including the directed edge identified by the indication, to reduce a number of root tables in the second connected subgraph.

12. The system of claim 9 , wherein the memory stores instructions executable by the processor to modify the connected subgraph based on the indication to obtain the modified subgraph by performing operations including:
identifying, based on the indication, one or more reversible join paths in the connected subgraph, wherein the one or more reversible joins paths each connect a source vertex corresponding to a root table of the connected subgraph to a destination vertex corresponding to a shared dimension table of the connected subgraph that is shared with another root table of the connected subgraph; and
reversing the direction of at least one of the one or more reversible join paths by reversing one or more directed edges of the connected subgraph that are identified by the indication as corresponding to a one-to-one join.

13. The system of claim 12 , wherein the memory stores instructions executable by the processor to reverse the direction of the at least one of the one or more reversible join paths by performing operations including:
checking that the root table of the at least one of the one or more reversible join paths is still a root table of the modified subgraph; and
checking that the shared dimension table corresponding to the destination vertex of the at least one of the one or more reversible join paths would not become a root table of the modified subgraph.

14. The system of claim 9 , wherein the memory stores instructions executable by the processor to modify the connected subgraph based on th

Assignees

• Thoughtspot Inc

Inventors

• Shah Naman
• Kothari Rakesh
• Agarwal Vaibhav

Classifications

• G06F16/2456 Primary

  Join operations · CPC title

• G06F16/211

  Schema design and management · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title

• G06F16/24534 Primary

  Query rewriting; Transformation · CPC title