Overlap Method

Sorted Runs :
Consider a cuboid on j attributes { }. We use ( ) to denote cuboid sorted in that order. Consider computed using . A sorted run R of S in B is defined as : , where Q is the maximal sequence of tuples t of B such that for each tuple in Q, the first l columns have the same value.

Partitions :
B and S have a common prefix . A partition of a cuboid S in B is a union of sorted runs such that the first l - 1 columns (the common prefix) of all the tuples of the sorted runs have the same value.