IP Library › Granted Patent US 12,259,889
Granted Patent B2
US 12,259,889 · App. 18/599,389 · Granted Mar 25, 2025

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

Inventors: Naman Shah (Palo Alto, CA); Rakesh Kothari (San Jose, CA); Vaibhav Agarwal (Cupertino, CA)
Assignee: Thoughtspot, Inc.
G06F16/2456G06F16/211G06F16/2246G06F16/2282G06F16/24534
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,259,889
App. No.
18/599,389
Granted
Mar 25, 2025
Kind
B2
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.

Claims (72)

1. A method comprising:

obtaining, by a data analysis system, a database query for obtaining results data, wherein the database query is expressed in accordance with a defined structured data access language implemented by a database, wherein obtaining the database query includes:

automatically generating, by the data analysis system, the database query in accordance with a transformed database agnostic representation of the database query; and

prior to automatically generating the database query, automatically generating, by the data analysis system, the transformed database agnostic representation of the database query by:

obtaining, by the data analysis system, user input data, wherein the results data is responsive to the user input data;

prior to obtaining the user input data, obtaining, by the data analysis system, a join graph, wherein the join graph indicates a first join between a first table stored in the database and a second table stored in the database, wherein relationship data indicating that the first join is a one-to-one join is unavailable from the join graph;

automatically generating, by the data analysis system, in response to the user input data, a database agnostic representation of the database query; and

transforming, by the data analysis system, the database agnostic representation to obtain the transformed database agnostic representation, wherein transforming the database agnostic representation includes:

obtaining, by the data analysis system, from the join graph, a connected subgraph, wherein the connected subgraph includes a first vertex representing the first table, a second vertex representing the second table, and a first unidirectional edge extending from the first vertex to the second vertex representing the first join;

accessing, by the data analysis system, the relationship data;

in response to the relationship data, obtaining, by the data analysis system, a modified subgraph by modifying the connected subgraph, wherein the modified subgraph includes the first vertex representing the first table, the second vertex representing the second table, and a second unidirectional edge extending from the second vertex to the first vertex, and wherein the modified subgraph omits the first unidirectional edge; and

automatically generating, by the data analysis system, in response to the modified subgraph, a query graph including a root vertex corresponding to the database query;

obtaining, by the data analysis system, from the database, the results data, responsive to execution of the database query by the database; and

outputting, by the data analysis system, at least a portion of the results data for presentation to a user.

2. The method of claim 1 , wherein:

the connected subgraph includes a first cardinality of root vertices; and

the modified subgraph includes a second cardinality of root vertices that is less than the first cardinality.

3. The method of claim 1 , wherein:

obtaining the modified subgraph includes determining, by the data analysis system, that the connected subgraph omits an edge representing a many-to-one join between the first table and a fourth table.

4. The method of claim 1 , wherein obtaining the query graph includes including, in the query graph, a non-root vertex representing a database agnostic representation of a second database query that references the second table, wherein the second vertex is a root vertex of the modified subgraph.

5. The method of claim 4 , wherein obtaining the query graph includes automatically generating the database agnostic representation of the second database query.

6. The method of claim 1 , wherein obtaining the query graph includes including, in the query graph, a non-root vertex representing a database agnostic representation of a second database query that references the first table, wherein the first table includes a measure column referenced in the user input data.

7. The method of claim 6 , wherein obtaining the query graph includes automatically generating the database agnostic representation of the second database query.

8. A data analysis system, comprising:

a memory; and

a processor that executes instructions stored in the memory to:

obtain a database query for obtaining results data, wherein the database query is expressed in accordance with a defined structured data access language implemented by a database, wherein to obtain the database query the processor executes the instructions to:

automatically generate the database query in accordance with a transformed database agnostic representation of the database query; and

prior to the generation of the database query, automatically generate the transformed database agnostic representation of the database query, wherein to automatically generate the transformed database agnostic representation of the database query the processor executes the instructions to:

obtain user input data, wherein the results data is responsive to the user input data;

prior to obtaining the user input data, obtain a join graph, wherein the join graph indicates a first join between a first table stored in the database and a second table stored in the database, wherein relationship data that indicates that the first join is a one-to-one join is unavailable from the join graph;

automatically generate, in response to the user input data, a database agnostic representation of the database query; and

transform the database agnostic representation to obtain the transformed database agnostic representation, wherein to transform the database agnostic representation the processor executes the instructions to:

 obtain, from the join graph, a connected subgraph, wherein the connected subgraph includes a first vertex representing the first table, a second vertex representing the second table, and a first unidirectional edge extending from the first vertex to the second vertex representing the first join;

 access the relationship data;

 in response to the relationship data, obtain a modified subgraph by modification of the connected subgraph, wherein the modified subgraph includes the first vertex representing the first table, the second vertex representing the second table, and a second unidirectional edge extending from the second vertex to the first vertex, and wherein the modified subgraph omits the first unidirectional edge; and

 automatically generate, in response to the modified subgraph, a query graph including a root vertex corresponding to the database query;

obtain, from the database, the results data, responsive to execution of the database query by the database; and

output at least a portion of the results data for presentation to a user.

9. The data analysis system of claim 8 , wherein:

the connected subgraph includes a first cardinality of root vertices; and

the modified subgraph includes a second cardinality of root vertices that is less than the first cardinality.

10. The data analysis system of claim 8 , wherein:

to obtain the modified subgraph the processor executes the instructions to determine that the connected subgraph omits an edge representing a many-to-one join between the first table and a fourth table.

11. The data analysis system of claim 8 , wherein to obtain the query graph the processor executes the instructions to include, in the query graph, a non-root vertex representing a database agnostic representation of a second database query that references the second table, wherein the second vertex is a root vertex of the modified subgraph.

12. The data analysis system of claim 11 , wherein to obtain the query graph the processor executes the instructions to automatically generate the database agnostic representation of the second database query.

13. The data analysis system of claim 8 , wherein to obtain the query graph the processor executes the instructions to include, in the query graph, a non-root vertex representing a database agnostic representation of a second database query that references the first table, wherein the first table includes a measure column referenced in the user input data.

14. The data analysis system of claim 13 , wherein to obtain the query graph the processor executes the instructions to automatically generate the database agnostic representation of the second database query.

15. A non-transitory computer-readable storage medium that includes instructions that, when executed by a processor, facilitate performance of operations comprising:

obtaining, by a data analysis system, a database query for obtaining results data, wherein the database query is expressed in accordance with a defined structured data access language implemented by a database, wherein obtaining the database query includes:

automatically generating, by the data analysis system, the database query in accordance with a transformed database agnostic representation of the database query; and

prior to automatically generating the database query, automatically generating, by the data analysis system, the transformed database agnostic representation of the database query by:

obtaining, by the data analysis system, user input data, wherein the results data is responsive to the user input data;

prior to obtaining the user input data, obtaining, by the data analysis system, a join graph, wherein the join graph indicates a first join between a first table stored in the database and a second table stored in the database, wherein relationship data indicating that the first join is a one-to-one join is unavailable from the join graph;

automatically generating, by the data analysis system, in response to the user input data, a database agnostic representation of the database query; and

transforming, by the data analysis system, the database agnostic representation to obtain the transformed database agnostic representation, wherein transforming the database agnostic representation includes:

obtaining, by the data analysis system, from the join graph, a connected subgraph, wherein the connected subgraph includes a first vertex representing the first table, a second vertex representing the second table, and a first unidirectional edge extending from the first vertex to the second vertex representing the first join;

accessing, by the data analysis system, the relationship data;

in response to the relationship data, obtaining, by the data analysis system, a modified subgraph by modifying the connected subgraph, wherein the modified subgraph includes the first vertex representing the first table, the second vertex representing the second table, and a second unidirectional edge extending from the second vertex to the first vertex, and wherein the modified subgraph omits the first unidirectional edge; and

automatically generating, by the data analysis system, in response to the modified subgraph, a query graph including a root vertex corresponding to the database query;

obtaining, by the data analysis system, from the database, the results data, responsive to execution of the database query by the database; and

outputting, by the data analysis system, at least a portion of the results data for presentation to a user.

16. The non-transitory computer-readable storage medium of claim 15 , wherein:

the connected subgraph includes a first cardinality of root vertices; and

the modified subgraph includes a second cardinality of root vertices that is less than the first cardinality.

17. The non-transitory computer-readable storage medium of claim 15 , wherein:

obtaining the modified subgraph includes determining, by the data analysis system, that the connected subgraph omits an edge representing a many-to-one join between the first table and a fourth table.

18. The non-transitory computer-readable storage medium of claim 15 , wherein obtaining the query graph includes including, in the query graph, a non-root vertex representing a database agnostic representation of a second database query that references the second table, wherein the second vertex is a root vertex of the modified subgraph.

19. The non-transitory computer-readable storage medium of claim 18 , wherein obtaining the query graph includes automatically generating the database agnostic representation of the second database query.

20. The non-transitory computer-readable storage medium of claim 15 , wherein obtaining the query graph includes:

including, in the query graph, a non-root vertex representing a database agnostic representation of a second database query that references the first table, wherein the first table includes a measure column referenced in the user input data; and

automatically generating the database agnostic representation of the second database query.

Assignments (2)
SECURITY INTEREST Recorded Mar 7, 2025
From: THOUGHTSPOT, INC.; THOUGHTSPOT, LLC
To: TRIPLEPOINT CAPITAL LLC
Reel/Frame 070442/0499 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Mar 8, 2024
From: SHAH, NAMAN; KOTHARI, RAKESH; AGARWAL, VAIBHAV
To: THOUGHTSPOT, INC.
Reel/Frame 066692/0232 →
Continuity (3)
Continuation 16854219 · Apr 21, 2020
Provisional Application 62837426 · Apr 23, 2019
Related Publication 20240211479A1 · Jun 27, 2024
References Cited (60)
US 5649591A · Green · 1997 [cited by applicant]
US 6449605B1 · Witkowski · 2002 [cited by applicant]
US 8577913B1 · Hansson et al. · 2013 [cited by applicant]
US 9275132B2 · Roberts et al. · 2016 [cited by applicant]
US 9405794B2 · Prakash et al. · 2016 [cited by applicant]
US 11409744B2 · Shah et al. · 2022 [cited by applicant]
US 20030182310A1 · Charnock et al. · 2003 [cited by applicant]
US 20040267730A1 · Dumais et al. · 2004 [cited by applicant]
US 20050027717A1 · Koudas et al. · 2005 [cited by applicant]
US 20050289124A1 · Kaiser et al. · 2005 [cited by applicant]
US 20060167865A1 · Andrei · 2006 [cited by applicant]
US 20070038618A1 · Kosciusko et al. · 2007 [cited by applicant]
US 20070185833A1 · Turkel et al. · 2007 [cited by applicant]
US 20070192300A1 · Reuther et al. · 2007 [cited by applicant]
US 20070219974A1 · Chickering et al. · 2007 [cited by applicant]
US 20080109422A1 · Dedhia · 2008 [cited by applicant]
US 20080262999A1 · Helsen et al. · 2008 [cited by applicant]
US 20090019019A1 · Jones et al. · 2009 [cited by applicant]
US 20090019022A1 · Schallert et al. · 2009 [cited by applicant]
US 20100017395A1 · Wayn et al. · 2010 [cited by applicant]
US 20100161651A1 · Cras et al. · 2010 [cited by applicant]
US 20110113048A1 · Njemanze · 2011 [cited by applicant]
US 20110282864A1 · Collins et al. · 2011 [cited by applicant]
US 20120066206A1 · Chappell et al. · 2012 [cited by applicant]
US 20120066217A1 · Eder · 2012 [cited by applicant]
US 20120254251A1 · Barbosa et al. · 2012 [cited by applicant]
US 20130339370A1 · Holstege et al. · 2013 [cited by applicant]
US 20140172914A1 · Elnikety et al. · 2014 [cited by applicant]
US 20140201241A1 · Wood et al. · 2014 [cited by applicant]
US 20140337371A1 · Li · 2014 [cited by applicant]
US 20160171050A1 · Das · 2016 [cited by applicant]
US 20170270159A1 · Wang et al. · 2017 [cited by applicant]
US 20190026337A1 · Aksman · 2019 [cited by applicant]
US 20200341978A1 · Shah et al. · 2020 [cited by applicant]
EP 268367A2 · 1988 [cited by applicant]
EP 1587011A1 · 2005 [cited by applicant]
EP 2202658A2 · 2010 [cited by applicant]
EP 2207106A2 · 2010 [cited by applicant]
WO 0141002A1 · 2001 [cited by applicant]
WO 2015009353A1 · 2015 [cited by applicant]
Sayyadian et al., “Efficient Keyword Search Across Heterogeneous Relational Databases”, 2007, IEEE, 346-355 (10 pp). [cited by applicant]
Wu et al: “Towards Keyword-Driven Analytical Processing”, Proceedings of the 2007 ACM Sigmod International Conference on Management of Data, Sigmo '07, Jun. 12, 2007, (12 pp). [cited by applicant]
Shi et al.: “50x Faster: Speeding Up an SQL-Based Legacy System With Few Changes”, Oct. 4, 2011 Retrieved from Internet: URL: http://www.user.tu-berline.de/komm/CD/paper/040221.pdf [retrieved on Jun. 11, 2014]. (12 pp). [cited by applicant]
Blunschi et al: “SODA: Generating SQL for Business Users”, Proceedings of the VLDB Endowment, vol. 5, No. 10, Aug. 27, 2012 pp. 932-935 (12 pp). [cited by applicant]
Baid et al: “Toward Scalable Keyword Search over Relational Data”, Proceedings of the VLDS Endowment, vol. 3, No. 1-2, Sep. 1, 2010, pp. 140-149 (10 pp). [cited by applicant]
Jajodia et al., “Flexible Support for Multiple Access Control Policies”, ACM Transactions on Database Systems, ACM New York, NY, USA, vol. 26, No. 2, Jun. 1, 2001, pp. 217-228 (48 pp). [cited by applicant]
International Search Report and Written Opinion for PCT/US14/39230; Date of mailing Nov. 24, 2014 (16 pp). [cited by applicant]
Anonymous: “File System Permission—Wikipedia, The Free Encyclopedia.” Jun. 11, 2013 (Jun. 11, 2013); URL: http://en.wikipedia.org/w/index/php?title.sub.--File.sub.-- system.sub.--p-ermissionsoldid=559455322 [retrieved o… [cited by applicant]
Li et al: “Efficient Type-Ahead Search on Relational Data: a TASTIER Approach”, Sigmod-Pods '09: Compilation Proceedings of the International Conference on Management Data 28th Symposium on Principles of Database System… [cited by applicant]
Anonymous, “Natural Language Processing”, Wikipedia, Downloaded Jan. 30, 2019, https://en.wikipedia.org/wiki/Natural_language_processing, (8 pp). [cited by applicant]
Seif, G., “An Easy Introduction to Natural Language Processing—Using Computers to Understand Human Language”, Oct. 1, 2018 (Downloaded Jan. 30, 2019), https://towardsdatascience.com/an-easy-introduction-to-natural-langu… [cited by applicant]
Avrach, A., thoughtspot.com, “What the Bleep is a Chasm Trap?”, https://www.thoughtspot.com/fact-and-dimension/what-bleep-chasm-trap 9/, Date Unknown, Downloaded Apr. 2, 2019 (9 pp). [cited by applicant]
Sisense, “Chasm and Fan Traps”, https://documentation.sisense.com/latest/managing-data/working-with-data/chasm-fan-traps.htm, Date Unknown, Downloaded Apr. 2, 2019 (8 pp). [cited by applicant]
Thoughtspot, “Chasm Traps”, https://docs.thoughtspot.com/4.4/admin/loading/chasm-trap.html, Version 4.4 Guides, Date Unknown, Downloaded Apr. 2, 2019 (4 pp). [cited by applicant]
Extended European Search Report received in co-pending Application No. EP 19160657.3 dated Apr. 4, 2019 (11 pp). [cited by applicant]
Eades, Peter, et al., “A Fast & Effective Heuristic for the Feedback Arc Set Problem,” Information Processing Letters, vol. 47, Issue 6, Oct. 18, 1993, pp. 319-323. [cited by applicant]
Wikipedia, “Dijkstra's algorithm”, Date Unknown, downloaded Jul. 16, 2019, https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm (11 pp). [cited by applicant]
Wikipedia, “Consistent hashing”, https://en.wikipedia.org/wiki/Consistent_hashing, Date Unknown, Downloaded Aug. 15, 2019, (5 pp). [cited by applicant]
Morton, K., et al., “Dynamic Workload Driven Data Integration in Tableau”, Proceedings of the 2012 International Conference on Management of Data, SIGMOD '12, Jan. 1, 2012, p. 807 (9 pp). [cited by applicant]
Extended European Search Report dated Jul. 26, 2019, issued in co-pending EP Application No. 19166422.6 (11 pp). [cited by applicant]