Skip to content

Performing Queries through Matrix Operations

Jump to bottom
Diego Martín Fernández edited this page Nov 7, 2023 · 6 revisions

Recall from the model description that we are storing values following a Matrix representation. As such, we can make use of Matrix operations for performing the usual queries. This can potentially increase the computational speed. To put it simply, let us see an example continuing with the framework that we introduced in the model description. Note that we will make use of the Subject-Object-Predicate reference system. Since we have to represent the information, a more efficient solution was proposed from the simplest aproach, that will be using three-dimensional matrices:

  • First dimension => rows that will represent the subjects
  • Second dimension => cols that will represent the objects
  • Value of the matrix => the value of matrix[i][j] = x, being x the predicate that relates the subject with the object starting at 1 since 0 is reserved for no relation

Example

Supose the data from the previous example:

Given that we already have represented the information in a bidimensional matrix, we can retrieve the relations like this:

  • Subject = alan = 0 (index of the subjects list)
  • Object = uk = 6 (index of the objects list)
  • Predicate = country = matrix[0][6] = 1 (remember we start at 1, 0 is reserved for no relation)

Select by Subject

What we want to do is to replicate the following SPARQL query using our engine.

PREFIX :  <http://example.org/>
SELECT *
WHERE {
    :alan ?predicate ?object .
}

For us to achieve so, we will make use of Matrix operations. As such, we will have to perform operations over the Axis(0) (recall what we have mentioned earlier). It can be seen that what we want to do is to discard those sub-views where the subject does not correspond to the one we want to query, while preserving (as-is) the ones that hold. Hence, we can apply the multiplicative identity with ones only on the subjects that we want to select.

In the example data using the previous select query we want the resulting matrix (or graph) that has only alan as subject. So we use a trimmed identity matrix (It = Identity trimmed) where It[0][0] = 1 and the rest elements will be 0. Moreover, alan is in index 0 of the subjects list hence It[0][0] = 1. For any other element it will be just to make It[x][x] = 1, being x the index of the subject in the subjects list. In case we wanted to retrieve all the graph, it will just suffice using the identity matrix.

It = Matrix(Predicates x Predicates)
M = Matrix(Subjects x Objects)
It · M = Matrix(Subjects x Objects)

[[1, 0, 0, 0],   [[2, 4, 5, 0, 0, 0, 0, 7, 8],    [[2, 4, 5, 0, 0, 0, 0, 7, 8],
 [0, 0, 0, 0],    [0, 0, 0, 0, 0, 0, 1, 0, 0],     [0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0], .  [0, 0, 0, 0, 0, 5, 1, 0, 0],  =  [0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0],    [0, 6, 0, 3, 5, 0, 0, 0, 0]]     [0, 0, 0, 0, 0, 0, 0, 0, 0]]

Select by Predicate (TO BE FIXED - OUTDATED)

A more complex and interesting example is finding all the triples matching a certain predicate. What we are going to do is to retrieve all the triples where the predicate is :instanceOf. That is, we are willing to replicate the following SPARQL query:

PREFIX :  <http://example.org/>
SELECT *
WHERE {
    ?subject :instanceOf ?object .
}

The way this is achieved using our engine is as follows. Recall the resulting array in the aforementioned example. We want to match the triples where there's a 1 in the 7th row. In a similar manner to what we have described before, if we multiply each Predicate-Object matrix by a diagonal array where we can find a 1 in the 7th row, we will obtain a new matrix where all the elements are discarded except from those in the 7th row. Note that the order in which we compute the product of both factors is crucial. For the case of retrieving the Predicates, we have to put the Predicate-Object matrix as the second factor. To put an example, let us see how this is computed for the Predicate-Object matrix corresponding to the first Subject.

F = Matrix(Predicates x Predicates)
M = Matrix(Predicates x Objects)
F · M = Matrix(Predicates x Objects)

[[0, 0, 0, 0, 0, 0, 0, 0],   [[0, 0, 0, 0, 0, 0, 0, 0, 0],    [[0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],    [0, 0, 0, 0, 0, 0, 0, 0, 0],     [0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],    [0, 0, 0, 0, 0, 0, 0, 0, 0],     [0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0], ·  [0, 0, 0, 0, 0, 0, 0, 0, 0],  =  [0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],    [0, 0, 1, 0, 0, 0, 0, 0, 0],     [0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],    [0, 0, 0, 0, 0, 0, 0, 0, 0],     [0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 0],    [0, 0, 0, 0, 0, 1, 0, 0, 0],     [0, 0, 0, 0, 0, 1, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0]]    [0, 0, 0, 0, 1, 0, 0, 0, 0]]     [0, 0, 0, 0, 0, 0, 0, 0, 0]],

In case we would like to retrieve not just one predicate, but several, as in the following example:

PREFIX :  <http://example.org/>
SELECT *
WHERE {
    ?subject :instanceOf | :country ?object .
}

We could rewrite the factor matrix as the sum of the two factor matrices for each of the queries separate; that is, the sum of the factor matrix for ?subject :instanceOf ?object and ?subject :country ?object. This can be obtained as follows:

F = Matrix(Predicates x Predicates) = (F1 + F2)
M = Matrix(Predicates x Objects)
F · M = Matrix(Predicates x Objects)

F1 = [[0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 1, 0],
      [0, 0, 0, 0, 0, 0, 0, 0]];

F2 = [[0, 0, 0, 0, 0, 0, 0, 0],
      [0, 1, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0]];

F = F1 + F2;

Select by Object

This is a similar aproach as with [Subjects](## Select by Subject) but just changing the order of the multiplication and with a new It such that the number of objects is represented.

PREFIX :  <http://example.org/>
SELECT *
WHERE {
    ?subject ?predicate :human .
}

It = Matrix(Objects x Objects)
M = Matrix(Subjects x Objects)
M · It = Matrix(Subjects x Objects)


				 [[0, 0, 0, 0, 0, 0, 0, 0, 0],
                                  [0, 0, 0, 0, 0, 0, 0, 0, 0],
[[2, 4, 5, 0, 0, 0, 0, 7, 8],     [0, 0, 1, 0, 0, 0, 0, 0, 0], 	    [[0, 0, 5, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 0, 0],  .  [0, 0, 0, 0, 0, 0, 0, 0, 0],  =    [0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 5, 1, 0, 0],     [0, 0, 0, 0, 0, 0, 0, 0, 0],       [0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 6, 0, 3, 5, 0, 0, 0, 0]]     [0, 0, 0, 0, 0, 0, 0, 0, 0],       [0, 0, 0, 0, 0, 0, 0, 0, 0]]
                                  [0, 0, 0, 0, 0, 0, 0, 0, 0],
                                  [0, 0, 0, 0, 0, 0, 0, 0, 0],
                                  [0, 0, 0, 0, 0, 0, 0, 0, 0]]
Clone this wiki locally