Relational Operations on Bags

Section outline

Introduces relations as bags (multisets), which allow duplicate tuples, contrasting them with the set-based model.
Presents motivations for using bags in commercial DBMSs, primarily for efficiency in operations like union and projection, as duplicate elimination is not required.
Explains how bags are necessary for certain aggregate calculations, such as computing a correct average over a column with duplicate values.
Redefines the union, intersection, and difference operations for bags. For a tuple $t$ appearing $n$ times in bag $R$ and $m$ times in bag $S$: it appears $n+m$ times in the bag union $R \cup S$, $min(n, m)$ times in the bag intersection $R \cap S$, and $max(0, n-m)$ times in the bag difference $R - S$.
Details bag projection, where each tuple is processed independently and duplicate tuples in the result are preserved.
Describes bag selection, where a condition is applied to each tuple individually, and duplicates satisfying the condition are kept in the output.
Defines the Cartesian product of bags, where if tuple $r$ appears $m$ times in relation $R$ and tuple $s$ appears $n$ times in relation $S$, the concatenated tuple $rs$ appears $m \times n$ times in the product $R \times S$.
Covers joins of bags (natural and theta-joins), where each pair of tuples is compared and resulting tuples are added to the answer without eliminating duplicates.

#1

read: Section 5.1: Relational Operations on Bags (section)

model: pro
rules: bullet definition math presentation short


Present the following.  Use definition formal definition when it applies.

- Introduces relations as bags (multisets), which allow duplicate tuples, contrasting them with the set-based model.
- Presents motivations for using bags in commercial DBMSs, primarily for efficiency in operations like union and projection, as duplicate elimination is not required.
- Explains how bags are necessary for certain aggregate calculations, such as computing a correct average over a column with duplicate values.
- Redefines the union, intersection, and difference operations for bags. For a tuple $t$ appearing $n$ times in bag $R$ and $m$ times in bag $S$: it appears $n+m$ times in the bag union $R \cup S$, $min(n, m)$ times in the bag intersection $R \cap S$, and $max(0, n-m)$ times in the bag difference $R - S$.
- Details bag projection, where each tuple is processed independently and duplicate tuples in the result are preserved.
- Describes bag selection, where a condition is applied to each tuple individually, and duplicates satisfying the condition are kept in the output.
- Defines the Cartesian product of bags, where if tuple $r$ appears $m$ times in relation $R$ and tuple $s$ appears $n$ times in relation $S$, the concatenated tuple $rs$ appears $m \times n$ times in the product $R \times S$.
- Covers joins of bags (natural and theta-joins), where each pair of tuples is compared and resulting tuples are added to the answer without eliminating duplicates.

Relational Operations on Bags

Relations as Bags (Multisets)

A relation, in practice, is often treated as a bag, or multiset, rather than a set. A bag permits a tuple to appear multiple times. The order of tuples remains immaterial, as in a set. For instance, a relation may contain the tuples (1,2), (3,4), and (1,2), where (1,2) has a multiplicity of two.
Motivation for Using Bags
The use of bags is predicated on two principal considerations:
1. Efficiency: Certain relational operations are more efficient when duplicate elimination is not required. The union of two bags is a simple concatenation of their tuples. Projection is performed on each tuple independently, without the need for comparison against other projected tuples.
2. Aggregate Operations: Queries involving aggregation, such as calculating an average, often necessitate the preservation of duplicate values to produce a correct result. To find the average value of a column, one must sum all values, including any duplicates, and divide by the total count of tuples.
Union, Intersection, and Difference of Bags

The standard set operations are redefined for bags based on tuple multiplicity.
Definition: Bag Union, Intersection, and Difference
Let tuple $t$ appear $n$ times in bag $R$ and $m$ times in bag $S$. The multiplicity of $t$ in the resulting bags is defined as follows:
- Bag Union ($R \cup S$): The tuple $t$ appears $n + m$ times.
- Bag Intersection ($R \cap S$): The tuple $t$ appears $\min(n, m)$ times.
- Bag Difference ($R - S$): The tuple $t$ appears $\max(0, n - m)$ times.
Bag Projection

The bag-projection operator, denoted $\pi_L(R)$, processes each tuple of bag $R$ independently. If multiple distinct tuples in $R$ project to the same tuple on the attribute list $L$, these duplicates are preserved in the result.
Bag Selection

The bag-selection operator, $\sigma_C(R)$, applies the selection condition $C$ to each tuple of bag $R$. Every tuple that satisfies the condition is included in the result. Duplicate tuples that satisfy the condition will appear in the result with their original multiplicity.
Cartesian Product of Bags

The rule for the Cartesian product is a direct extension of the set-based definition, accounting for tuple multiplicities.

Definition: Cartesian Product of Bags

If a tuple $r$ appears $m$ times in relation $R$ and a tuple $s$ appears $n$ times in relation $S$, then the concatenated tuple $rs$ will appear $m \times n$ times in the product $R \times S$.
Joins of Bags

Joins of bags, including natural join ($R \bowtie S$) and theta-join ($R \bowtie_C S$), are computed by comparing each tuple from one relation with each from the other. When a pair of tuples satisfies the join condition, the resulting tuple is added to the output bag. If a tuple $r$ from $R$ appears $m$ times and a tuple $s$ from $S$ appears $n$ times, and $(r, s)$ is a joining pair, their combination will contribute $m \times n$ identical tuples to the result.

gemini-2.5-pro

Version: 2
Model: gemini-2.5-pro
Created: 2025-09-20 11:31:59
Duration: 27.37376618385315
Cummulative cost: $5.56e-02