Vimos que em Álgebra relacional 101 o padrão é pensar em bags, não em conjuntos. Eles são construtos matemáticos distintos entre si. Mas, será que são tão distintos assim?

Bags como conjuntos?

Entrar aqui em uma pequena sidequest: provar que bags são abstrações que podem ser reduzidas a conjuntos. E existem duas maneiras de se fazer isso.

O primeiro modelo: seja uma bag $B$, e seu conjunto equivalente $C$. Todo elemento em $C$ é uma tupla que satisfaça a seguinte propriedade:

$\forall b \in B: C \ni (n, b), n \gt 0, n = m_B(b)\\ \forall (n, b) \in C: B \ni b \land m_B\left(b\right) = n$

Onde a função $m_B(e)$ conta a multiplicidade do elemento $e$ na bag $B$, tal qual fizemos em Álgebra relacional 101. Assim, $n$ representa a quantidade de vezes que o valor $b$ aparece na bag $B$.

O primeiro ponto é em cima da operação de adicionar um elemento a uma bag. E isso tem ainda 2 desdobramentos:

• quando já existia um elemento equivalente na bag (ie, $m_B(b) \gt 0$)
• quando o elemento não existia anteriormente na bag (ie, $m_B(b) = 0$)

Bem, vamos lá. No caso de que já tem elementos, vamos fazer uma simples manobra:

$B + \left\{b\right\} \therefore C \setminus xxx \cup yyy$

Onde iremos remover um elemento no conjunto $C$ e adicionar outro. O elemento a ser removido? Bem, se $C$ é o equivalente de $B$, então vamos ter que $(n, b) \in C$, logo iremos remover esse elemento. E adicionar? Bem, como $n = m_B(b)$, e após a adição de $b$ na bag ele aumenta em 1 a multiplicidade, vou adicionar $(n+1, b)$:

$B + \left\{b\right\} \therefore C \setminus (n, b) \cup (n+1, b), n = m_B(b)$

E no caso da adição de elementos que não existem? Bem, nesse caso, vamos só adicionar o novo elemento:

$B + \left\{b\right\} \therefore C \cup (1, b)$

A operação de remoção é o inverso: se $m_B(b) = 1$, então eu só removo $(1, b)$ do conjunto, caso contrário removo $(n, b)$ e acrescento $(n-1, b)$.

Conjuntos como bags?

Ok, e agora, em relação a conjuntos, como faremos? A priori, um conjunto pode ser modelado como uma bag, uma bag muito específica! Todo elemento tem multiplicidade 1!

$\forall c \in C, c \in B \land m_B(c) = 1\\ \forall c \in B, c \in C$

Mas como podemos fazer um mapeamento da adição de elementos em conjuntos na bag? Bem, vamos ver aqui…

Ao adicionar um elemento em um conjunto, temos duas opções:

• o elemento já pertence ao conjunto
• o elemento não pertence ao conjunto

Para o caso em que o elemento já pertencer ao conjunto, acontece uma particularidade muito interessante:

$c \in C \implies C \cup \left\{c\right\} = C$

Ou seja, nessa situação, eu preciso manter a bag intacta. Agora, no caso de não existir? Nesse caso, o conjunto muda:

$c \not\in C \implies C \cup \left\{c\right\} \not= C$

Nesse caso, uma “soma” simples na bag funciona, pois fazendo isso a multiplicidade de $c$ vai sair de 0 para 1.

Função de mapeamento

De conjuntos para bags:

$bagificar(C) = B, \forall c \in C, c \in B, m_B(c) = 1$

De bags para conjuntos:

$setificar(B) = C, \forall b \in B \land m_B(b) = n \not= 0, (n, b) \in C$