Explanation of the formula 2ⁿ - 1 for the number of groups

           List all of the range variables. Mark each range variable as either P or - (present or not present). There are 2ⁿ such assignments. Subtract off the assignment of all -'s. Then each of the remaining assignments (2ⁿ - 1) correspond to a group in the of a fully expanded memo structure for a query which is the join of n relations. (This does not exclude Cartesian products or bushy join trees -- all possible join orders -- i.e. query trees are considered).