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)}$

Latest revision as of 15:38, 23 November 2015

Exercises

These are exercises for containment of Conjunctive Queries


Exercise 1

Given the queries

  • $Q_1(x, y) \leftarrow Q(x, a), Q(a, b), Q(b, y)$
  • $Q_2(x, y) \leftarrow Q(x, a), Q(a, b), Q(b, c), Q(c, y)$
  • $Q_3(x, y) \leftarrow Q(x, a), Q(a, 1), Q(1, b), Q(b, y)$
  • $Q_4(x, y) \leftarrow Q(x, y), Q(y, x)$

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:

  • For $Q_1$ path $x \to a \to b \to y$ is of length 3;
  • For $Q_2$ path $x \to a \to b \to c \to y$ is of length 4.
  • $\Rightarrow$ containment doesn't hold. Let's show that formally.


Formal reasoning:

  • [math] D_{Q_1} = \begin{array}{ | l l | } \hline C_x & C_a \\ C_a & C_b \\ C_b & C_c \\ C_c & C_y \\ \hline \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)
  • Evaluate $Q_2(D_{Q_1})$:
  • $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)}$
  • Let's build a candidate substitution. We want this substitution to be a matching.
    • First we map the head of $Q_2$ to associated constants: $x \mapsto C_x, y \mapsto C_y$ (because we want $(C_x, C_y)$ be in $Q_2(D_{Q_1})$)
    • Then we evaluate (1) atom $Q(x, a)$ and map $a \mapsto C_a$
    • For (2) we map $b \mapsto C_b$, for (3) $c \mapsto C_y$, but for (4) we cannot find a tuple $(C_y, ?)$ in $D_{Q_2}$ with $C_y$ in the first position.
    • Therefore this substitution is not a matching.
  • We have constructed a counter-example $\Rightarrow$ $Q_1 \not \subseteq Q_2$


$Q_2 \subseteq Q_1$?

  • [math] D_{Q_2} = \begin{array}{ | l l | } \hline C_x & C_a \\ C_a & C_b \\ C_b & C_y \\ \hline \end{array}[/math]
  • 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)}$
  • For head we map $x \mapsto C_x$, $y \mapsto C_y$, for (1): $a \mapsto C_a$, for (2) $b \mapsto C_b$, for (3) we would have to map $y \mapsto C_c$, but we cannot do it since we already have mapped $y \mapsto C_y$.
  • Therefore, this candidate substitution is not a function and $Q_2 \not \subseteq Q_1$


$Q_1 \subseteq Q_3$?

  • [math] D_{Q_1} = \begin{array}{ | l l | } \hline C_x & C_a \\ C_a & C_b \\ C_b & C_c \\ C_c & C_y \\ \hline \end{array}[/math]
  • 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)}$
  • For head we have $x \mapsto C_x$, $y \mapsto C_y$, for (1) $a \mapsto C_a$, but for (2) there's no tuple $(C_a, 1)$ in $D_{Q_1}$ so we cannot find a matching.
  • Therefore $Q_1 \not \subseteq Q_3$


$Q_3 \subseteq Q_1$?

  • [math] D_{Q_3} = \begin{array}{ | l l | } \hline C_x & C_a \\ C_a & 1 \\ 1 & C_b \\ C_b & C_y \\ \hline \end{array}[/math]
  • 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)}$
  • For head we have $x \mapsto C_x$, $y \mapsto C_y$, for (1) $a \mapsto C_a$, for (2) $b \mapsto C_1$, but for (3) we would have to map $y \mapsto C_b$, and we already established $y \mapsto C_y$
  • Therefore $Q_3 \not \subseteq Q_1$


$Q_1 \subseteq Q_4$?

  • [math] D_{Q_1} = \begin{array}{ | l l | } \hline C_x & C_a \\ C_a & C_b \\ C_b & C_c \\ C_c & C_y \\ \hline \end{array}[/math]
  • Evaluate $Q_4(D_{Q_1})$
  • $Q_4(x, y) \leftarrow \underbrace{Q(x, y)}_{(1)}, \underbrace{Q(y, x)}_{(2)}$
  • For head we have $x \mapsto C_x$, $y \mapsto C_y$, and for (1) we would have to map $y \mapsto C_a$, but we already established $y \mapsto C_y$.
  • Therefore $Q_1 \not \subseteq Q_4$


$Q_4 \subseteq Q_1$?

  • [math]D_{Q_4} = \begin{array}{ | l l | } \hline C_x & C_y \\ C_y & C_x \\ \hline \end{array}[/math]
  • 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)}$
  • For head we have $x \mapsto C_x$, $y \mapsto C_y$, for (1) $a \mapsto C_y$, for (2) $b \mapsto C_x$ and atom (3) matches tuple $(C_x, C_y)$.
  • Our candidate substitution $x \mapsto C_x, y \mapsto C_y, a \mapsto C_y, b \mapsto C_x$ is a matching and therefore $Q_4 \subseteq Q_1$.


$Q_2 \subseteq Q_3$?

  • [math]D_{Q_2} = \begin{array}{ | l l | } \hline C_x & C_a \\ C_a & C_b \\ C_b & C_y \\ \hline \end{array}[/math]
  • 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)}$
  • For head we have $x \mapsto C_x$, $y \mapsto C_y$, for (1) $a \mapsto C_a$, but for (2) there's no tuple $(C_a, 1)$ in $D_{Q_2}$, so there's no matching.
  • $\Rightarrow Q_2 \not \subseteq Q_3$


$Q_3 \subseteq Q_2$?

  • [math]D_{Q_3} = \begin{array}{ | l l | } \hline C_x & C_a \\ C_a & 1 \\ 1 & C_b \\ C_b & C_y \\ \hline \end{array}[/math]
  • 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)}$
  • For head we have $x \mapsto C_x$, $y \mapsto C_y$, for (1) $a \mapsto C_a$, for (2), $b \mapsto 1$, for (3) $c \mapsto C_b$, and atom (4) matches tuple $(C_b, C_y)$
  • Our candidate substitution $x \mapsto C_x, y \mapsto C_y, a \mapsto C_a, b \mapsto 1, c \mapsto C_b$ is a matching and therefore $Q_3 \subseteq Q_2$.


$Q_2 \subseteq Q_4$?

  • [math]D_{Q_2} = \begin{array}{ | l l | } \hline C_x & C_a \\ C_a & C_b \\ C_b & C_y \\ \hline \end{array}[/math]
  • Evaluate $Q_4(D_{Q_2})$
  • $Q_4(x, y) \leftarrow \underbrace{Q(x, y)}_{(1)}, \underbrace{Q(y, x)}_{(2)}$
  • For head we have $x \mapsto C_x$, $y \mapsto C_y$, for (1) we would have to map $y \mapsto C_a$, but we've already established $y \mapsto C_y$.
  • $Q_2 \not \subseteq Q_4$


$Q_4 \subseteq Q_2$?

  • [math]D_{Q_4} = \begin{array}{ | l l | } \hline C_x & C_y \\ C_y & C_x \\ \hline \end{array}[/math]
  • 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)}$
  • For head we have $x \mapsto C_x$, $y \mapsto C_y$, for (1) $a \mapsto C_y$, for (2) $b \mapsto C_x$, for (3) $c \mapsto C_y$, but for (4) there's no tuple $(C_y, C_y)$ in $D_{Q_4}$.
  • Therefore $Q_4 \not \subseteq Q_2$


$Q_3 \subseteq Q_4$?

  • [math]D_{Q_3} = \begin{array}{ | l l | } \hline C_x & C_a \\ C_a & 1 \\ 1 & C_b \\ C_b & C_y \\ \hline \end{array}[/math]
  • Evaluate $Q_4(D_{Q_3})$
  • $Q_4(x, y) \leftarrow \underbrace{Q(x, y)}_{(1)}, \underbrace{Q(y, x)}_{(2)}$
  • For head we have $x \mapsto C_x$, $y \mapsto C_y$, for (1) we would have to map $y \mapsto C_a$, but we've already established $y \mapsto C_y$.
  • $Q_3 \not \subseteq Q_4$


$Q_4 \subseteq Q_3$?

  • [math]D_{Q_4} = \begin{array}{ | l l | } \hline C_x & C_y \\ C_y & C_x \\ \hline \end{array}[/math]
  • 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)}$
  • For head we have $x \mapsto C_x$, $y \mapsto C_y$, for (1) $a \mapsto C_y$, but for (2) there's no tuple $(C_y, 1)$ in $D_{Q_4}$.
  • $Q_4 \not \subseteq Q_3$


Recap: $Q_4 \subseteq Q_1$, $Q_3 \subseteq Q_2$, no equivalent queries


See Also

Sources