Matching

Aka 'where exists'

Signature

matching(left: Relation, right: Relation) -> Relation

Examples

matching(suppliers, shipments)

Try it!

Description

Computes a relation as a subset of left tuples for which at least one right tuple would join on common attributes.

This operator, also known as semi-join, can be explained through the definition below. As shown, it consists in joining left and right relations and projecting the result back on left attributes.

def matching(left, right)
  project(join(left, right), left.attr_list)
end
matching(suppliers, shipments)

Try it!

Or, in SQL terms:

SELECT left.* FROM left NATURAL JOIN right

The synonym 'where exists' comes from the fact that, since right attributes are projected away, it may seem more intuitive to think about this operator as filtering tuples from left where there exists some tuple at right that would join. In SQL terms:

SELECT * FROM left WHERE EXISTS (SELECT * FROM right WHERE [join condition])

Implementation notes

As for (natural) join, you must take care of ensuring that the list of common attributes on which the matching applies corresponds to what you want. Renamings and projections are worth having at hand when using matching. Alternatively, shortcuts can be considered. A (advanced) example below:

# Same as matching(left, right) except that only attributes in `wish`
# are take into account in matching.
def matching_on(left, right, wish)
  matching(left, project(right, wish))
end

# observe here how part names have been discarded to avoid matching them
# with supplier names (empty result guaranteed)
matching_on(suppliers, parts, [:city])

Try it!