Semantics

Answers($Q$, DB) - denotes the answers to RC query $Q$ over DB

1. $S_i$ is a table with arity Cnum($E_i$) and extension Eval($E_i$, DB)
2. $\overline{x}=x_1,\dots ,x_n$

For $R_i/n\in \rho$

1. Relation name: Eval($R_i$, DB) = Answers$(\{(\overline{x})|R_i(\overline{x})\},DB)$ where Cnum($R_i$) = $n$
2. Constant: Eval($c$) = Answers($\{(x)|x=c\}$, DB) where Cnum($R_i$) = 1
3. Selection: Eval(${\sigma }_{\mathrm{\#}i=\mathrm{\#}j}(E_1)$, DB) = Answers($\{(\overline{x})|S_1(\overline{x})\wedge (x_i=x_j)\}$, DB) where Cnum(${\sigma }_{\mathrm{\#}i=\mathrm{\#}j}(E_1)$) = Cnum($E_1$)
4. Projection: Eval(${\pi }_{\mathrm{\#}{i}_1,...,\mathrm{\#}{i}_m}(E_1)$) = Answers($\{(x_{i_1},\dots ,x_{i_m})|\mathrm{\exists }{x}_{i_{m+1}},\dots ,x_{i_n}\}$, DB) where Cnum(${\pi }_{\mathrm{\#}{i}_1,...,\mathrm{\#}{i}_m}(E_1)$) = m
5. Duplicate elimination: Eval(elim $E_1$, DB) = Answers($\{(\overline{x})$|elim $S_1(\overline{x})\}$, DB) where Cnum(elim $E_1$) = Cnum($E_1$)
6. Cross product: Eval($E_1\times E_2$, DB) = Answers($\{(\overline{x},\overline{y})|S_1(\overline{x})\wedge S_2(\overline{y})\},DB$) where Cnum($E_1\times E_2$) = Cnum($E_1$) + Cnum($E_2$)
7. Multiset Union: Eval($E_1\cup E_2$, DB) = Answers($\{(\overline{x})|S_1(\overline{x})\vee S_2(\overline{x})\}$, DB) where Cnum($E_1\cup E_2$) = Cnum($E_1$)
8. Multiset Difference: (Except all) Eval ($E_1-E_2$, DB) = Answers($\{(\overline{x})|S_1(\overline{x})\wedge \mathrm{\neg }{S}_2(\overline{x})\}$, DB) where Cnum(E_1 - E_2) = Cnum($E_1$)
9. Multiset Difference: (Alternative not exists) Eval ($E_1-E_2$, DB) = Answers($\{(\overline{x})|S_1(\overline{x})\wedge \mathrm{\neg }(S_1(\overline{x})\wedge S_2(\overline{x}))\}$, DB) where Cnum(E_1 - E_2) = Cnum($E_1$)