Line 22: | Line 22: | ||
Formal reasoning: | Formal reasoning: | ||
− | * | + | * <math> |
D_{Q_1} = | D_{Q_1} = | ||
\begin{array}{ | l l | } | \begin{array}{ | l l | } | ||
Line 31: | Line 31: | ||
C_c & C_y \\ | C_c & C_y \\ | ||
\hline | \hline | ||
− | \end{array} | + | \end{array}</math> |
** note that instead of creating a database with the body of $Q_1$, we created constant that correspond to the variables (to avoid confusion) | ** note that instead of creating a database with the body of $Q_1$, we created constant that correspond to the variables (to avoid confusion) | ||
* Evaluate $Q_2(D_{Q_1})$: | * Evaluate $Q_2(D_{Q_1})$: | ||
Line 44: | Line 44: | ||
$Q_2 \subseteq Q_1$? | $Q_2 \subseteq Q_1$? | ||
− | * | + | * <math> |
D_{Q_2} = | D_{Q_2} = | ||
\begin{array}{ | l l | } | \begin{array}{ | l l | } | ||
Line 52: | Line 52: | ||
C_b & C_y \\ | C_b & C_y \\ | ||
\hline | \hline | ||
− | \end{array} | + | \end{array}</math> |
* Evaluate $Q_1(D_{Q_2})$ | * Evaluate $Q_1(D_{Q_2})$ | ||
* $Q_1(x, y) \leftarrow \underbrace{Q(x, a)}_{(1)}, \underbrace{Q(a, b)}_{(2)}, \underbrace{Q(b, y)}_{(3)}$ | * $Q_1(x, y) \leftarrow \underbrace{Q(x, a)}_{(1)}, \underbrace{Q(a, b)}_{(2)}, \underbrace{Q(b, y)}_{(3)}$ | ||
Line 60: | Line 60: | ||
$Q_1 \subseteq Q_3$? | $Q_1 \subseteq Q_3$? | ||
− | * | + | * <math> |
D_{Q_1} = | D_{Q_1} = | ||
\begin{array}{ | l l | } | \begin{array}{ | l l | } | ||
Line 69: | Line 69: | ||
C_c & C_y \\ | C_c & C_y \\ | ||
\hline | \hline | ||
− | \end{array} | + | \end{array}</math> |
− | + | ||
* We evaluate $Q_3(D_{Q_1})$ | * We evaluate $Q_3(D_{Q_1})$ | ||
* $Q_3(x, y) \leftarrow \underbrace{Q(x, a)}_{(1)}, \underbrace{Q(a, 1)}_{(2)}, \underbrace{Q(1, b)}_{(3)}, \underbrace{Q(b, y)}_{(4)}$ | * $Q_3(x, y) \leftarrow \underbrace{Q(x, a)}_{(1)}, \underbrace{Q(a, 1)}_{(2)}, \underbrace{Q(1, b)}_{(3)}, \underbrace{Q(b, y)}_{(4)}$ | ||
Line 78: | Line 77: | ||
$Q_3 \subseteq Q_1$? | $Q_3 \subseteq Q_1$? | ||
− | * | + | * <math> |
D_{Q_3} = | D_{Q_3} = | ||
\begin{array}{ | l l | } | \begin{array}{ | l l | } | ||
Line 87: | Line 86: | ||
C_b & C_y \\ | C_b & C_y \\ | ||
\hline | \hline | ||
− | \end{array} | + | \end{array}</math> |
− | + | ||
* We evaluate $Q_1(D_{Q_3})$ | * We evaluate $Q_1(D_{Q_3})$ | ||
* $Q_1(x, y) \leftarrow \underbrace{Q(x, a)}_{(1)}, \underbrace{Q(a, b)}_{(2)}, \underbrace{Q(b, y)}_{(3)}$ | * $Q_1(x, y) \leftarrow \underbrace{Q(x, a)}_{(1)}, \underbrace{Q(a, b)}_{(2)}, \underbrace{Q(b, y)}_{(3)}$ | ||
Line 96: | Line 94: | ||
$Q_1 \subseteq Q_4$? | $Q_1 \subseteq Q_4$? | ||
− | * | + | * <math> |
D_{Q_1} = | D_{Q_1} = | ||
\begin{array}{ | l l | } | \begin{array}{ | l l | } | ||
Line 105: | Line 103: | ||
C_c & C_y \\ | C_c & C_y \\ | ||
\hline | \hline | ||
− | \end{array} | + | \end{array}</math> |
− | + | ||
* Evaluate $Q_4(D_{Q_1})$ | * Evaluate $Q_4(D_{Q_1})$ | ||
* $Q_4(x, y) \leftarrow \underbrace{Q(x, y)}_{(1)}, \underbrace{Q(y, x)}_{(2)}$ | * $Q_4(x, y) \leftarrow \underbrace{Q(x, y)}_{(1)}, \underbrace{Q(y, x)}_{(2)}$ | ||
Line 114: | Line 111: | ||
$Q_4 \subseteq Q_1$? | $Q_4 \subseteq Q_1$? | ||
− | * | + | * <math>D_{Q_4} = |
− | D_{Q_4} = | + | |
\begin{array}{ | l l | } | \begin{array}{ | l l | } | ||
\hline | \hline | ||
Line 121: | Line 117: | ||
C_y & C_x \\ | C_y & C_x \\ | ||
\hline | \hline | ||
− | \end{array} | + | \end{array}</math> |
* Evaluate $Q_1(D_{Q_4})$ | * Evaluate $Q_1(D_{Q_4})$ | ||
* $Q_1(x, y) \leftarrow \underbrace{Q(x, a)}_{(1)}, \underbrace{Q(a, b)}_{(2)}, \underbrace{Q(b, y)}_{(3)}$ | * $Q_1(x, y) \leftarrow \underbrace{Q(x, a)}_{(1)}, \underbrace{Q(a, b)}_{(2)}, \underbrace{Q(b, y)}_{(3)}$ | ||
Line 129: | Line 125: | ||
$Q_2 \subseteq Q_3$? | $Q_2 \subseteq Q_3$? | ||
− | * | + | * <math>D_{Q_2} = |
− | D_{Q_2} = | + | |
\begin{array}{ | l l | } | \begin{array}{ | l l | } | ||
\hline | \hline | ||
Line 137: | Line 132: | ||
C_b & C_y \\ | C_b & C_y \\ | ||
\hline | \hline | ||
− | \end{array} | + | \end{array}</math> |
* Evaluate $Q_3(D_{Q_2})$ | * Evaluate $Q_3(D_{Q_2})$ | ||
* $Q_3(x, y) \leftarrow \underbrace{Q(x, a)}_{(1)}, \underbrace{Q(a, 1)}_{(2)}, \underbrace{Q(1, b)}_{(3)}, \underbrace{Q(b, y)}_{(4)}$ | * $Q_3(x, y) \leftarrow \underbrace{Q(x, a)}_{(1)}, \underbrace{Q(a, 1)}_{(2)}, \underbrace{Q(1, b)}_{(3)}, \underbrace{Q(b, y)}_{(4)}$ | ||
Line 145: | Line 140: | ||
$Q_3 \subseteq Q_2$? | $Q_3 \subseteq Q_2$? | ||
− | * | + | * <math>D_{Q_3} = |
− | D_{Q_3} = | + | |
\begin{array}{ | l l | } | \begin{array}{ | l l | } | ||
\hline | \hline | ||
Line 154: | Line 148: | ||
C_b & C_y \\ | C_b & C_y \\ | ||
\hline | \hline | ||
− | \end{array} | + | \end{array}</math> |
* Evaluate $Q_2(D_{Q_3})$ | * Evaluate $Q_2(D_{Q_3})$ | ||
* $Q_2(x, y) \leftarrow \underbrace{Q(x, a)}_{(1)}, \underbrace{Q(a, b)}_{(2)}, \underbrace{Q(b, c)}_{(3)}, \underbrace{Q(c, y)}_{(4)}$ | * $Q_2(x, y) \leftarrow \underbrace{Q(x, a)}_{(1)}, \underbrace{Q(a, b)}_{(2)}, \underbrace{Q(b, c)}_{(3)}, \underbrace{Q(c, y)}_{(4)}$ | ||
Line 162: | Line 156: | ||
$Q_2 \subseteq Q_4$? | $Q_2 \subseteq Q_4$? | ||
− | * | + | * <math>D_{Q_2} = |
− | D_{Q_2} = | + | |
\begin{array}{ | l l | } | \begin{array}{ | l l | } | ||
\hline | \hline | ||
Line 170: | Line 163: | ||
C_b & C_y \\ | C_b & C_y \\ | ||
\hline | \hline | ||
− | \end{array} | + | \end{array}</math> |
* Evaluate $Q_4(D_{Q_2})$ | * Evaluate $Q_4(D_{Q_2})$ | ||
* $Q_4(x, y) \leftarrow \underbrace{Q(x, y)}_{(1)}, \underbrace{Q(y, x)}_{(2)}$ | * $Q_4(x, y) \leftarrow \underbrace{Q(x, y)}_{(1)}, \underbrace{Q(y, x)}_{(2)}$ | ||
Line 178: | Line 171: | ||
$Q_4 \subseteq Q_2$? | $Q_4 \subseteq Q_2$? | ||
− | * | + | * <math>D_{Q_4} = |
− | D_{Q_4} = | + | |
\begin{array}{ | l l | } | \begin{array}{ | l l | } | ||
\hline | \hline | ||
Line 185: | Line 177: | ||
C_y & C_x \\ | C_y & C_x \\ | ||
\hline | \hline | ||
− | \end{array} | + | \end{array}</math> |
* Evaluate $Q_2(D_{Q_4})$ | * Evaluate $Q_2(D_{Q_4})$ | ||
* $Q_2(x, y) \leftarrow \underbrace{Q(x, a)}_{(1)}, \underbrace{Q(a, b)}_{(2)}, \underbrace{Q(b, c)}_{(3)}, \underbrace{Q(c, y)}_{(4)}$ | * $Q_2(x, y) \leftarrow \underbrace{Q(x, a)}_{(1)}, \underbrace{Q(a, b)}_{(2)}, \underbrace{Q(b, c)}_{(3)}, \underbrace{Q(c, y)}_{(4)}$ | ||
Line 193: | Line 185: | ||
$Q_3 \subseteq Q_4$? | $Q_3 \subseteq Q_4$? | ||
− | * | + | * <math>D_{Q_3} = |
− | D_{Q_3} = | + | |
\begin{array}{ | l l | } | \begin{array}{ | l l | } | ||
\hline | \hline | ||
Line 202: | Line 193: | ||
C_b & C_y \\ | C_b & C_y \\ | ||
\hline | \hline | ||
− | \end{array} | + | \end{array}</math> |
* Evaluate $Q_4(D_{Q_3})$ | * Evaluate $Q_4(D_{Q_3})$ | ||
* $Q_4(x, y) \leftarrow \underbrace{Q(x, y)}_{(1)}, \underbrace{Q(y, x)}_{(2)}$ | * $Q_4(x, y) \leftarrow \underbrace{Q(x, y)}_{(1)}, \underbrace{Q(y, x)}_{(2)}$ | ||
Line 210: | Line 201: | ||
$Q_4 \subseteq Q_3$? | $Q_4 \subseteq Q_3$? | ||
− | * | + | * <math>D_{Q_4} = |
− | D_{Q_4} = | + | |
\begin{array}{ | l l | } | \begin{array}{ | l l | } | ||
\hline | \hline | ||
Line 217: | Line 207: | ||
C_y & C_x \\ | C_y & C_x \\ | ||
\hline | \hline | ||
− | \end{array} | + | \end{array}</math> |
* Evaluate $Q_3(D_{Q_4})$ | * Evaluate $Q_3(D_{Q_4})$ | ||
* $Q_3(x, y) \leftarrow \underbrace{Q(x, a)}_{(1)}, \underbrace{Q(a, 1)}_{(2)}, \underbrace{Q(1, b)}_{(3)}, \underbrace{Q(b, y)}_{(4)}$ | * $Q_3(x, y) \leftarrow \underbrace{Q(x, a)}_{(1)}, \underbrace{Q(a, 1)}_{(2)}, \underbrace{Q(1, b)}_{(3)}, \underbrace{Q(b, y)}_{(4)}$ |
These are exercises for containment of Conjunctive Queries
Given the queries
Find all pairs $(Q_i, Q_j)$ s.t. $Q_i \subseteq Q_j$. Are there any equivalent queries?
$Q_1 \subseteq Q_2$?
Informal reasoning:
Formal reasoning:
$Q_2 \subseteq Q_1$?
$Q_1 \subseteq Q_3$?
$Q_3 \subseteq Q_1$?
$Q_1 \subseteq Q_4$?
$Q_4 \subseteq Q_1$?
$Q_2 \subseteq Q_3$?
$Q_3 \subseteq Q_2$?
$Q_2 \subseteq Q_4$?
$Q_4 \subseteq Q_2$?
$Q_3 \subseteq Q_4$?
$Q_4 \subseteq Q_3$?
Recap: $Q_4 \subseteq Q_1$, $Q_3 \subseteq Q_2$, no equivalent queries