US 9,317,557 B2Granted

Answering relational database queries using graph exploration

AssigneeMicrosoft Technology Licensing, LLC

InventorsBin Shao, Haixun Wang, Wei Fang

Life of this patent

Estimating the term…

Loading patent…

Abstract

Embodiments are directed to processing queries using schema graph traversal and to establishing a schema graph that allows queries to be answered by traversing graph nodes. In one scenario, a computer system receives a query which specifies relational tables and corresponding relationships that are to be retrieved from a relational database. The computer system accesses a schema graph that includes graph nodes representing relational tables, as well as edges that identify relationships between the relational tables. The graph nodes include relational data that was loaded from one storage area (e.g. a non-volatile storage area), and the schema graph is stored in a second storage area (e.g. a volatile storage area). The computer system then traverses the schema graph, beginning at a set of graph nodes and continuing along the edges to other graph nodes until the query has been satisfied, and then reports the results of the graph traversal.

Claims24

Dependent claims

A computer system comprising the following:

one or more processors;
one or more computer-readable storage media having stored thereon computer-executable instructions that, when executed by the one or more processors, cause the computing system to execute a method for processing a query using schema graph traversal, the method comprising the following:
an act of receiving a query at the computer system from a query sender, the query specifying one or more relational tables and their relationships that are to be retrieved from a relational database;
an act of creating a schema graph comprising one or more graph nodes representing relational tables and one or more edges that identify relationships between the relational tables, the graph nodes including relational data that was loaded from a first storage area, the schema graph itself being stored in a second storage area, wherein the creating the schema graph includes at least the following:
accessing a plurality of relational tables;
generating a plurality of graph nodes, with a separate graph node for each of the plurality of relational tables represented by the schema graph;
generating a plurality of edges between different graph nodes that define the relationships between the relational tables, at least a first edge of the plurality of edges and a second edge of the plurality of edges define different relationship attributes, such that nodes connected by the first edge have at least one of a different type or a different quantity of relationships than different nodes that are connected by the second edge;
and
visually representing the schema graph with the plurality of nodes and the plurality of edges, wherein the first and second edges are represented as separate lines with different display attributes, the different display attributes corresponding to different relationship attributes between different nodes;
an act of traversing the schema graph, beginning at a set of graph nodes and continuing along the edges to one or more other graph nodes until the query has been satisfied;
and
an act of reporting the results of the graph traversal.

9 more elements

A computer system comprising the following:

one or more processors;
system memory;
one or more computer-readable storage media having stored thereon computer-executable instructions that, when executed by the one or more processors, cause the computing system to execute a method for establishing a schema graph that allows queries to be answered by traversing graph nodes, the method comprising the following:
an act of accessing a relational database comprising one or more database tables in a first data storage area that stores relational data;
an act of extracting a schema graph from the accessed relational database, the schema graph comprising graph nodes representing the accessed database tables, the schema graph further comprising edges, which are displayed as corresponding lines and that visually represent relationships between the graph nodes, wherein at least two edges are represented as separate lines with different display attributes, the different display attributes corresponding to different relationship attributes between different nodes, the schema graph being stored in a second, different storage area;
an act of associating one or more relational tables with the graph nodes of the schema graph, such that both the relational tables and the relational tables' corresponding relationships are accessible via the schema graph;
an act of receiving a query at the computer system, the query specifying one or more relational tables and their relationships that are to be retrieved from the relational database;
and
an act of traversing the edges connecting the graph nodes of the schema graph to execute the received query.

6 more elements

Dependencies are inferred from the claim text.