I think the specification is missing a few things like the example could be improved.

I don't think, It is very clear what "match" means in the following paragraph:

(nstore-from transaction nstore pattern [config]) → generator

Return a generator of bindings where variables (in the sense of nstore-var?) of PATTERN are bound against one or more matching tuples from the store associated with TRANSACTION.

Similarly nstore-where re-use "match" without defining it:

(nstore-where transaction nstore pattern) → procedure → generator

Return a procedure that takes a generator of bindings as argument and returns a generator of bindings where variables of PATTERN are bound to one or more matching tuples from the store associated with TRANSACTION.

That said the sample implementation should make things more clear. But I think that could use some improvement.

Will step-by-step example be enough to complete the specification of "match"?

What do you think?