Query

Given a database signature $\rho =(R_1/k_1,\dots ,R_n/k_n)$ and a set of constants ${c_1, c_2, …}

Expression $E$

• $R_i$
• $c_j$
• ${\sigma }_{\mathrm{\#}i=\mathrm{\#}j}(E_1)$
• ${\pi }_{\mathrm{\#}{i}_1,...,\mathrm{\#}{i}_m}(E_1)$
• elim $E_1$
• $E_1\times E_2$
• $E_1\cup E_2$
• $E_1-E_2$

→ Eval($E$, DB) denotes table computed by evaluating RA query $E$
→ Cnum($E$) denotes the arity (number of columns)