# Rohit Agarwal's Notes

## Sparse matrix multiplication using SQL

07 Jun 2013

`a` and `b` are two sparse matrices. We want to perform `a * b` as shown below:

``````0   1   0   0   9                1   0   0                0   0   0
0   0   3   0   0       \ /      0   0   0      -----     0  21   0
0   0   0   2   0        *       0   7   0      -----     0   0   4
0   0   0   0   0       / \      0   0   2                0   0   0
0   0   0
``````

We can represent a sparse matrix in a relational database as a table `matrix_name(row_num, col_num, value)`. Each non-zero cell in the matrix is represnted as a record (i, j, value) in the table.

Here’s how to do the multiplication. First, create the tables:

``````CREATE TABLE a (
row_num INT,
col_num INT,
value INT,
PRIMARY KEY(row_num, col_num)
);

CREATE TABLE b (
row_num INT,
col_num INT,
value INT,
PRIMARY KEY(row_num, col_num)
);
``````

Next, insert values into the tables:

``````INSERT INTO a VALUES
(1, 2, 1),
(1, 5, 9),
(2, 3, 3),
(3, 4, 2);

INSERT INTO b VALUES
(1, 1, 1),
(3, 2, 7),
(4, 3, 2);
``````

Finally, perform the multiplication using the following query:

``````SELECT a.row_num, b.col_num, SUM(a.value*b.value)
FROM a, b
WHERE a.col_num = b.row_num
GROUP BY a.row_num, b.col_num;

2|2|21
3|3|4
``````

To see how this query works, remember the formula for cell (i,j) of the product. It is the sum of a(i,k)*b(k,j) for all k. The `JOIN` condition `a.col_num = b.row_num` makes sure that both `a.value` and `b.value` has the same k. The `GROUP BY` clause makes sure that we sum over all k’s.