Matrix Multiplication Using SQL

This week I found out how to perform matrix multiplication using SQL. I don’t think I’ve touched matrix multiplication since university so first I gave myself a quick refresher in the mathematics.


To multiply two matrices (A x B), e.g.
1 orig_matrix_input
First, determine the size of the resulting matrix which will have the same number of rows as matrix A & the same number of columns as matrix B.
2 orig_matrix_output
To get each result, find the row from A & column from B that overlap at the result cell. Therefore, to get the upper left result, use row 1 (A) & column 1 (B). To calculate the result, sum the product of each matching pair.
3 matrix_input_row1_col1

(1 * 2) + (2 * 1) + (3 * 3) = 13

Likewise, to get the upper middle result, use row 1 (A) & column 2 (B).
4 matrix_input_row1_col2

(1 * 4) + (2 * 5) + (3 * 6) = 32

To get upper right result, use row 1 (A) & column 3 (B).
5 matrix_input_row1_col3

(1 * 8) + (2 * 10) + (3 * 9) = 55

To get lower left result, use row 2 (A) & column 1 (B).
6 matrix_input_row2_col1

(2 * 2) + (5 * 1) + (7 * 3) = 30

To get lower middle result, use row 2 (A) & column 2 (B).
7 matrix_input_row2_col2

(2 * 4) + (5 * 5) + (7 * 6) = 75

To get lower right result, use row 2 (A) & column 3 (B).
8 matrix_input_row2_col3

(2 * 8) + (5 * 10) + (7 * 9) = 129

These calculations give the resulting matrix.
9 final_matrix_output
If you want to check your results, the matrix multiplication calculator at WolframAlpha is a good option: http://www.wolframalpha.com/input/?i=matrix+multiplication+calculator


To perform this matrix multiplication using T-SQL, create two tables to hold the matrix data.

IF EXISTS (SELECT * FROM sys.tables WHERE name = 'matrixA')
   DROP TABLE matrixA;
GO
CREATE TABLE matrixA (
   row_num TINYINT,
   col_num TINYINT,
   value TINYINT
);
GO
IF EXISTS (SELECT * FROM sys.tables WHERE name = 'matrixB')
   DROP TABLE matrixB;
GO
CREATE TABLE matrixB (
   row_num TINYINT,
   col_num TINYINT,
   value TINYINT
);
GO

In this schema, row_num corresponds to the row of the matrix, col_num corresponds to the column of the matrix & value is the value held at this cell.
Populate the tables with the data from matrices A & B.

<code
INSERT INTO matrixA (
row_num,
col_num,
value
)
VALUES
(1, 1, 1),
(1, 2, 2),
(1, 3, 3),
(2, 1, 2),
(2, 2, 5),
(2, 3, 7);

INSERT INTO matrixB (
row_num,
col_num,
value
)
VALUES
(1, 1, 2),
(1, 2, 4),
(1, 3, 8),
(2, 1, 1),
(2, 2, 5),
(2, 3, 10),
(3, 1, 3),
(3, 2, 6),
(3, 3, 9);


To multiply the two matrices, join the tables matching col_num (A) to row_num (B), group by row_num (A) & col_num (B) & sum the product of the values.

SELECT A.row_num,
   B.col_num,
   SUM(A.value * B.value) AS value
FROM matrixA A
INNER JOIN matrixB B
ON A.col_num = B.row_num
GROUP BY A.row_num, B.col_num;

10 sql_matrix_output
If you want to determine the value for a specific point on the result matrix, add a WHERE clause, e.g.

SELECT A.row_num,
   B.col_num,
   SUM(A.value * B.value) AS result
FROM matrixA A
INNER JOIN matrixB B
ON A.col_num = B.row_num
WHERE A.row_num = 2
   AND B.col_num = 3
GROUP BY A.row_num, B.col_num;

Matrix multiplication using SQL is particularly useful for sparse matrices (where many of the values are zero) as you only need to store the non-zero valued entries in the tables.


One application for sparse matrix multiplication is to determine similarity patterns, e.g. in shopping lists so that that a retailer (like Amazon) can highlight on a product page what other products have been bought by customers who also bought this particular product.
To do this, create another table to hold a matrix, e.g.

IF EXISTS (SELECT * FROM sys.tables WHERE name = 'ShoppingFrequency')
   DROP TABLE ShoppingFrequency;
GO
CREATE TABLE ShoppingFrequency (
   Product VARCHAR(10),
   Customer VARCHAR(10),
   PurchaseCount TINYINT
);

Populate it with Products that Customers have bought & the number of times they have bought them from this retailer (the PurchaseCount).

INSERT INTO ShoppingFrequency (
   Product,
   Customer,
   PurchaseCount
)
VALUES
   ('Hat', 'Alice', 2),
   ('Mittens', 'Alice', 1),
   ('Gloves', 'Alice', 1),
   ('Scarf', 'Alice', 1),
   ('Hat', 'Bob', 1),
   ('Scarf', 'Bob', 1),
   ('Hat', 'Chloe', 1),
   ('Gloves', 'Chloe', 2),
   ('Scarf', 'Debbie', 2),
   ('Gloves', 'Debbie', 2),
   ('Mittens', 'Debbie', 3),
   ('Boots', 'Debbie', 1),
   ('Scarf', 'Debbie', 1);

To find what other Products have been bought by Customers who have also bought Hats (and how popular those other Products are), use the following query.

SELECT B.Product,
   SUM(A.PurchaseCount * B.PurchaseCount) AS Popularity
FROM ShoppingFrequency A
INNER JOIN ShoppingFrequency B
ON A.Customer = B.Customer
   AND A.Product <> B.Product
WHERE A.Product = 'Hat'
GROUP BY B.Product
ORDER BY Popularity DESC;

11 sql_hat_products
Likewise if, a customer was searching for Gloves & Mittens to maximise their chances of finding the best Product to keep their hands warm, you could create a view with the data from ShoppingFrequency & a dummy “Search” Customer corresponding to the Product search terms “Gloves” & “Mittens” to find which Product is most popular.

IF EXISTS (SELECT * FROM sys.views WHERE name = 'ShoppingFrequencySearch')
   DROP VIEW ShoppingFrequencySearch;
GO
CREATE VIEW ShoppingFrequencySearch
AS
SELECT Product, Customer, PurchaseCount FROM ShoppingFrequency
UNION
SELECT 'Gloves' AS Product, 'Search' AS Customer, 1 AS PurchaseCount
UNION
SELECT 'Mittens' AS Product, 'Search' AS Customer, 1 AS PurchaseCount;
GO
SELECT B.Product,
   SUM(A.PurchaseCount * B.PurchaseCount) AS Popularity
FROM ShoppingFrequencySearch A
INNER JOIN ShoppingFrequency B
ON A.Product = B.Product
WHERE A.Customer = 'Search'
GROUP BY B.Product
ORDER BY Popularity DESC;

12 sql_gloves_mittens

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Kevin Kline

Career and Technical Advice for the IT Professional

TroubleshootingSQL

Explaining the bits and bytes of SQL Server and Azure

SQL Authority with Pinal Dave

SQL Server Performance Tuning Expert

Powershellshocked

A blog about PowerShell and general Windows sysadmin stuff

Simon Learning SQL Server

I'm trying to become "better" at SQL Server and data - here's how I'm doing it!

%d bloggers like this: