## Foreign Keys as an Incidence Matrix: A High Level Look

July 23, 2011

In a previous post, we took a multigraph of foreign keys in the AdventureWorks database in SQL Server 2008 and manipulated it into a simple graph. This yielded a high level view of the foreign keys in a database. A perfect supplementary diagram to any database diagram. We were also able to derive some interesting and potentially useful facts regarding foreign keys in the database such as the graph center and graph periphery.

The graph from our previous post is below:

It really is a pretty constellation of vertices and edges. It’s possible to go a few steps further and manipulate this captured information in other ways. For example, one could create an incidence matrix of the graph. An incidence matrix where the columns are the edges and the rows are the vertices of a graph. If a vertex i is connected to an edge j, then the i,j entry of the incidence matrix is 1, otherwise, it’s marked 0.

In our previous example, we created a graph named fkgraph by executing:

fkgraph = Graph[querygraph]

To retrieve an incidence matrix from this graph, we may use the IncidenceMatrix function in Mathematica. Once executed, we may execute:

IncidenceMatrix[fkgraph]//MatrixForm.

If we do not utilize the PostFix function (//) to format IncidenceMatrix function with the function MatrixForm, we will get a sparse array like below.

A partial output of the desired output is captured below:

If we look above at the SparseArray output, we can immediately see that the number of rows of the incidence matrix is sixty-seven. That is, there are sixty-seven points in the graph. Consequentially, we know that there are sixty-seven tables with foreign key relationships in the AdventureWorks database as each point represents a table. There are simpler ways of deriving that information but as one proceeds to more abstract layers, it’s good to remember what one is actually working with.

What about the matrix itself? What is the rank of the matrix? To understand the rank of this matrix, we will use the Mathematica function MatrixRank.

MatrixRank[IncidenceMatrix[fkgraph]]

The output is:

Sixty-seven. Who knew? It’s a well known fact that the column rank and the row rank of a matrix are equal. Sixty-seven is the number of rows (points) in the matrix and eighty-six is the number of columns (edges). This would imply that the difference between total columns and the size of the column space is the number of dependent columns. Dependent columns are, in this representation, different choices one could make to JOIN one table with another.

The matrix itself is rather overwhelming. To get a better at a glance view of what the matrix looks like, we can use the MatrixPlot function.

The orange squares represent the value of one and the white of zero. In this sense, we have a rough understanding of the dispersion of ones and zeroes throughout the matrix.

I hope I’ve introduced enough tools in Mathematica to get one started with manipulating datasets and beginning to derive a deeper understanding regarding their properties. The topic is very deep and there’s much to learn and discover.

## Using Mathematica to Understand Foreign Key Relationships in a Database

June 24, 2011

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.

## Graphing Foreign Keys in SQL Server Using Mathematica

Foreign keys in any relational database form a cornerstone of a well-structured database. One of the challenges with any database diagramming tool is that the output will not be a mathematically manipulatable object. Certain attributes such as graph diameter or graph distance are not readily calculable. If one employs Mathematica, it’s possible to get a high level understanding of the foreign key relationships in a SQL Server database. Our goal is to take this:

And turn it into something that looks like this:

The challenge is to extract a result set that will give us what we need. Fortunately for us, great minds can show us the way. Pinal Dave (SQLAuthority.com) whipped up a tidy query that forms the basis of what we will use. The query we will use has some slight modifications from the original on Mr. Dave’s blog:

SELECT OBJECT_NAME(f.parent_object_id) AS TableName

,OBJECT_NAME (f.referenced_object_id) AS ReferenceTableName

,f.name AS ForeignKey

FROM sys.foreign_keys AS f

INNER JOIN sys.foreign_key_columns AS fc

ON f.OBJECT_ID = fc.constraint_object_id

The result set for AdventureWorks2008R2 should appear akin to what is below:

Next, let’s get this all into Mathematica. Make sure to set up the notebook file to connect to SQL Server like so:

Add in the query typed out above:

The output should look like the partial results below:

The Mathematica function we intend to use to visualize the foreign keys in the AdventureWorks2008R2 database is GraphPlot[]. Like TreePlot [], a function we used in a similar post, we will need to massage the result set into something Mathematica can use. If we wish to label the edges with the names of the foreign keys then GraphPlot will need to see entries akin to {u -> v, “w”}. To do this, we will use the Function[] ummmm function.

Once that is done, we will need to apply the function to the result set from SQL Server.

At this point, we’re ready to graph the foreign keys using GraphPlot.

It’s worth noting that the resulting multigraph is very, very busy. Here’s a screenshot of the graph expanded and a corner zoomed in on.

It’s possible to vertex label as well but imagine how cluttered the graph will be. Perhaps we want to abstract out the labels and just see the general structure of foreign keys in the database. We merely need to built a new function that does not have edge labeling and use that one instead.

When the function is applied to the result set, we get a flat table of relationships perfect for GraphPlot.

Once that is passed to GraphPlot, the resulting graph ensues:

There it is! All the foreign keys in the AdventureWorks2008R2 database seen from a bird’s eye view. So what next? Are we able to perform any mathematical manipulation on this? We’ll investigate that in part two. Thanks for reading!

« Previous PageNext Page »