Selection on Bags / Product of Bags / Joins of Bags

Selection on Bags / Product of Bags / Joins of Bags

Selection on Bags

To apply a selection to a bag, we apply the selection condition to each tuple separately. As always with bags, we do not remove duplicate tuples in the result.

Example (a) : If R is the bag


then the result of the bag-selection  is

Algebraic Laws for Bags



That is, all but the first tuple meets the selection condition. The last two tuples, which are duplicates in R, are each included in the result.

Product of Bags

The rule for the Cartesian product of bags is the expected one. Each tuple of one relation is paired with each tuple of the other, regardless of whether it is a duplicate or not. As a result, if a tuple r appears in a relation R m times and tuple s appears n times in relation S, then in the product R x S, the tuple rs will appear mn times.

Example (b) : Let R and S be the bags shown in Figure A. Then the product R x S consists of six tuples, as shown in Figure A-(c). Note that the normal convention regarding attribute names that we developed for set-relations applies equally well to bags. In this way, the attribute B, which belongs to both relations R and S, appears twice in the product, each time prefixed by one of the relation names.

Computing the product of bags

Joins of Bags

Joining bags also presents no surprises. We compare each tuple of one relation with each tuple of the other, decide whether or not this pair of tuples joins successfully, and if so we put the resulting tuple in the answer. When constructing the answer, we do not remove duplicate tuples.

Example (c) : The natural join R ⋈ S of the relations R and S seen in Figure A is        



That is, tuple (1, 2) of R joins with (2, 3) of S. Since there are two copies of (1, 2) in R and one copy of (2, 3) in S, there are two pairs of tuples that join to give the tuple (1, 2, 3). No other tuples from R and S join successfully.

As another example on the same relations R and S, the theta-join



produces the bag


The computation of the join is as follows. Tuple (1, 2) from R and (4, 5) from S meet the join condition. Since each appears twice in its relation, the number of times the joined tuple appears in the result is 2 x 2 or 4. The other possible join of tuples - (1, 2) from R with (2, 3) from S - fails to meet the join condition, so this combination does not appear in the result.



Tags