[20 Points] Not all laws and identities that hold for sets hold for bags as well. For each of the following claims that are true for sets, determine if it is true for bags. If true, prove your claim; otherwise give a counter-example.

(a) $R \cup R = R$ (the idempotent law for union)

This is false for bags:
$R \cup R = 2R$, in general
we can find Counterexample.

Let $R = \{ a , b \} $

so

$R \cup R = \{a,a,b,b\} \neq \{a, b\} = R$.

Thus $R \cup R = R$ is false for bags.

(b) $R \cap R = R$ (idempotent law for intersection)

This is true for bags: \[ m_{R \cap R}(x) = \min(m_R(x), m_R(x)) = m_R(x). \] For example, Let R = {a,b}
$m_{R \cap R}(a) = \min(1, 1) =1.$
$m_{R \cap R}(b) = \min(1, 1) =1.$
so
$R \cap R =\{a,b\}= R$

Therefore $R \cap R = R$ is true for bags.

(c) $R - R = \varnothing$(the idempotent law for union)

This is true for bags: \[ m_{R - R}(x) = \max(m_R(x) - m_R(x), 0) = \max(0, 0) = 0. \] So every element has multiplicity $0$ in $R - R$, which means $R - R$ is the empty bag: \[ R - R = \varnothing. \] for example, Let R = {a,b} \[ m_{R - R}(a) = \max(1 - 1, 0) = 0. \] \[ m_{R - R}(b) = \max(1 - 1, 0) = 0. \]

Therefore $R - R = \varnothing$ is true for bags.

(d) $R \cup (S \cap T) = (R \cup S) \cap (R \cup T)$ (distribution of union over intersection)

This is true for bags:
We can prove using explicit bag examples 

Let:
    R={a,b}

    S={a}

    T={a,a,b}

Left-hand side: \[ m_{S \cap T}(a) = \min(1, 2)=1, \] then \[ m_{R \cup (S \cap T)}(q) = 1 + \min(1, 2)=2. \] \[ m_{R \cup (S \cap T)}(b) = 1 + \min(0, 1)=1. \] so = {a,a,b}

Right-hand side: \[ m_{R \cup S}(a) = 1 + 1, \qquad m_{R \cup T}(a) = 1 + 2, \] so \[ \mu_{(R \cup S) \cap (R \cup T)}(a) = \min(1 + 1,\, 1 + 2)= 2 \] same for b: \[ \mu_{(R \cup S) \cap (R \cup T)}(b) = \min(1 + 0,\, 1 + 1)= 1 \] then = {a,a,b}

So the two bags are equal, and the distributive law \[ R \cup (S \cap T) = (R \cup S) \cap (R \cup T) \] is true for bags.

[10 Points] The following question is concerned about commutative property of some operations. Consider the given identities below for relational algebra operations on a relation R(a,b). For each one, either prove it or give a counter-example.

Let the relation \(R(a,b)\)={(1,5),(2,5),(2,1)}:

ab
15
25
21

\[(a) \gamma_{\min(a)\rightarrow y,\,x} \bigl(\gamma_{a,\,\mathrm{SUM}(b)\rightarrow x}(R)\bigr) \;=\; \gamma_{y,\,\mathrm{SUM}(b)\rightarrow x} \bigl(\gamma_{\min(a)\rightarrow y,\,b}(R)\bigr) \]

Lefthand side

  1. Inner: \[ \gamma_{a,\,\mathrm{SUM}(b)\rightarrow x}(R) \] Group by \(a\):
    • \(a=1\): \(b\) values \(5 \Rightarrow x = 5 = 5\)
    • \(a=2\): \(b\) value \(5,1 \Rightarrow x = 6\)
    Result: \[ \{(a=1,x=5),\ (a=2,x=6)\} \]
  2. Outer : \[ \gamma_{\min(a)\rightarrow y,\,x}() \] Group by \(x\), compute \(\min(a)\rightarrow y\):
    • \(x=5\): \(a=1 \Rightarrow y=5\)
    • \(x=6\): \(a=2 \Rightarrow y=6\)
    So \[ \text{Left} = \{(x=3,y=1),\ (x=1,y=2)\}. \]

Righthand side

  1. Inner: \[ \gamma_{\min(a)\rightarrow y,\,b}(R) \] Group by \(b\):
    • \(b=5\): tuples \((1,5),(2,5)\Rightarrow y=1\)
    • \(b=1\): tuple \((2,1)\Rightarrow y=2\)
    Result: \[ \{(b=5,y=1),\ (b=1,y=2)\} \]
  2. Outer: \[ \gamma_{y,\,\mathrm{SUM}(b)\rightarrow x}() \] Group by \(y\):
    • \(y=1\): \(b\) values \(5 \Rightarrow x = 5\)
    • \(y=2\): \(b\) values \(1 \Rightarrow x = 5\)
    So \[ \text{Right} = \{(x=5,y=1),\ (x=1,y=2)\}. \]

Therefore \[\{(x=5,y=1),(x=6,y=2)\} \neq \{(x=5,y=1),(x=1,y=2)\}, \] so identity (a) is false.

\[(b) \gamma_{\min(a)\rightarrow y,\,x} \bigl(\gamma_{a,\,\max(b)\rightarrow x}(R)\bigr) \;=\; \gamma_{y,\,\max(b)\rightarrow x} \bigl(\gamma_{\min(a)\rightarrow y,\,b}(R)\bigr) \]

Lefthand side

  1. Inner: \[ \gamma_{a,\,\max(b)\rightarrow x}(R) \] Group by \(a\):
    • \(a=1\): \(b\) values \(5 \Rightarrow x =5\)
    • \(a=2\): \(b\) value \(5,1 \Rightarrow x = 5\)
    Result: \[ \{(a=1,x=5),\ (a=2,x=5)\} \]
  2. Outer: \[ \gamma_{\min(a)\rightarrow y,\,x}() \] Group by \(x\):
    • \(x=5\): \(a=1 \Rightarrow y=1\)
    So \[ \text{Left} = \{(x=5,y=1)\}. \]

Righthand side

1. inner part : \[ \{(b=5,y=1),\ (b=1,y=2)\}. \]

  1. Outer: \[ \gamma_{y,\,\max(b)\rightarrow x}() \] Group by \(y\):
    • \(y=1\): \(b\) values \(5 \Rightarrow x =5\)
    • \(y=2\): \(b\) values \(1 \Rightarrow x =1\)
    So \[ \text{Right} = \{(y=1,x=5),(x=1,y=2)\}. \]

Therefore \[ \text{Right} = \{(x=5,y=1),(x=1,y=2)\} \neq \{(x=5,y=1)\} = \text{Left}, \] so identity (b) is false.