Are joins/pullbacks of bloom filters possible?
Ok, so the short answer to this question seems to be a &quot;yes, but it grows quickly in size&quot;. You can view the bloom filters for each tuple element as vectors of bits. In that case, their tensor product will be a &quot;bloom filter&quot; for the cartesian product, where projection can be done by taking partial traces.
The downside of this is that the number of bits grows exponentially with the size of the tuple. You can mitigate this by maintaining a list of bloom filters for all pairs of tuple elements instead, which is still useful for constraint propagation, and gives projection as the intersection of the projection of each pair filter.