In a previous post, we extracted information about foreign keys in the AdventureWorks database from SQL Server and plotted them in a multigraph in Mathematica. This gives us a high level perspective of the relationships between all the tables in a database. A lot of information is abstracted out but those details are easily found by including certain parameters in the Mathematica commands we’ve run or by using the usual database diagramming tools (SSMS or Visio for example).

Picking up where we left off, we just created a multigraph of the foreign keys in AdventureWorks that looked like this:

The next thing that we’d like to be able to do is take this graph and make it something that we can perform further operations on to gain a deeper understanding of our database structure. To start, we need Mathematica to be able to create a graph object out of the result set. This means the graph must no longer have parallel lines. It must be a simple graph. The simple way to do this, especially since we no longer need the foreign key names is to massage the query a little bit:

SELECT DISTINCT OBJECT_NAME(f.parent_object_id) AS TableName,

OBJECT_NAME (f.referenced_object_id) AS ReferenceTableName

FROM sys.foreign_keys AS f

INNER JOIN sys.foreign_key_columns AS fc

ON f.OBJECT_ID = fc.constraint_object_id

By doing this, all the duplicate rows will be removed.

A quick scan and comparison of the two queries will confirm that the total number of repeated tables in the first query was five and that the duplicates have been removed. I would love, love, love to craft a query that returns distinct pairs of values along with columns with duplicate information but I don’t have the requisite skill to craft that query in an acceptable amount of time. I intend to fix that. It’s an interesting problem. Now that the duplicate values have been removed, we may perform the typical operations that we used before. To begin, we open up the notebook we created before or input and execute the commands as shown below:

Once completed, the next step is to create the substitution function in Mathematica. To make the undirected edge symbol in Mathematica, hit the ESC key, type, “ue” and hit ESC again. <-> suffices as well if you like ugly.

And, of course, apply to the result set from SQL Server:

The set up is complete, next we will just apply Graph[] to the modified list:

The first question we may get the answer to now that the foreign key relationships in AdventureWorks are represented in a simple graph is what is the maximum minimum number of joins one must perform to join any one table in the database with another? What about the minimum maximum? To do this, we will want to calculate the graph diameter and graph radius of the graph, respectively. The answer turns out to be nine and five. Who knew?

What about knowing which tables have the most or least amount of graph eccentricity? Very easy to answer:

The central most tables in AdventureWorks are Document, PurchaseOrderHeader, and SalesOrderDetail while the most isolated tables are CountryRegionCurrency, PhoneNumberType, Illustration, Culture, ProductDescription, and SalesTaxRate. It certainly beats trying to figure it by looking at the diagram snippet below and trying to figure it out.

What’s the real world consequence of this? Using Mathematica in this respect can reduce the amount of time it takes to understand the high level structure of your database. Specifically, some poorly running queries may be associated with extensive use of joins. In his paper, “Query Optimization“, Yannis Ioannidis asserts,

“The memory requirements and running time of dynamic programming grow exponentially with query size (i.e., number of joins) in the worst case since all viable partial plans generated in each step must be stored to be used in the next one. In fact, many modern systems place a limit on the size of queries that can be submitted (usually around fifteen joins), because for larger queries the optimizer crashes due to its very high memory requirements. Nevertheless, most queries seen in practice involve less than ten joins, and the algorithm has proved to be very effective in such contexts” (referring to dynamic programming algorithms).

It’s worth noting that the paper was written in 1996 so many things have changed but the fundamental issue of joins being costly will remain true, especially as we continue to experience the explosive data growth that we have. Performing these analytical steps is no silver bullet. Much of performance tuning is correlating information from a variety of sources to understand what database users are looking for and how SQL Server is trying to respond to it.