Database Reference
In-Depth Information
the union of two or more sets is trivial, whereas computing the intersection
of two or more sets is difficult (if it is possible at all). The intuition for this
behavior is that all of the following algorithms support adding new elements
to a set. This is equivalent to computing the union of the original set and
the set containing only the new element to be added. However, most of
the algorithms do not support removing the elements from the set, which
would be required to compute the intersection. Additionally, many of the
algorithms support computing the cardinality of the union without having
to explicitly compute a representation of the union, making the calculation
fairly inexpensive.
To compute the cardinality of an intersection of sets requires taking
advantage of the
inclusion-exclusion
principle. The simplest form of this
principle relates the cardinality of the union of two sets with the cardinality
of the intersection:
Essentially, this relationship says that if the cardinality of A and the
cardinality ofBareadded,theelementsintheintersection havebeendouble
counted. To correct for this, subtract the cardinality of the intersection.
Rearranging this equation gives a formula for the size of an intersection:
The same can be done for the intersection of three sets using the same
principle:
Substituting from the first equation to eliminate the other intersections
yields a final equation:
