It is not clear at all how to test the existence of a solution to this query in
time linear in the size of the database. The problem is similar to the one of
finding a triangle in a graph, for which the best know algorithm has complexity
even slightly worse than matrix multiplication [1]}.
If the degree of the input structure is bounded by a constant \(d\) , we can test the
existence of a solution in linear time by the following algorithm. We first go
through all edges \((x,y)\)  of the database and add \(y\)  to a list associated to
\(x\)  and \(x\)  to a list associated to \(y\) . It remains now to go through all
nodes \(y\)  of the database, consider all pairs \((x,z)\)  of nodes in the
associated list (the number of such pairs is bounded by \(d^2\) ) and then test
whether there is an edge between \(x\)  and \(z\)  (by testing whether \(x\)  is in the
list associated to \(z\) ).
