Minicon Algorithm

This is an approach for query rewriting used in LAV Mediation

Overview

An optimized version of the Bucket Algorithm

  • avoids the last step: verification
  • idea: not to put atoms that will generate invalid rewritings
  • an atom can be useless if its binding of variables doesn't match the bindings of other occurrences of this variable


So, steps are

  • creating MCDs (corresponds to the Bucket creation step)
  • combining MCDs (the second step)
  • where MCDs are Minicon Descriptions - instead of buckets


Example

The algorithm will be explained by this example

Consider this global query

  • $Q(x) \leftarrow U(y,z), R(x,z), T(z,y), R(y',x)$


And two LAV mappings

  • $V_1(u,v) \subseteq T(w,u), U(v,w), R(v,u)$
  • $V_2(u,v,v') \subseteq T(w,u), U(v,w), R(v',w)$


Step 1: Creating MCDs

In this step

  • for each atom $A_i$ of the query $Q$
  • for each LAV mapping $V_i$
  • determine the relevance of $V_i$ w.r.t. rewriting $A_i$


Illustration of Step 1

Consider first atom $U(y, z)$ of $Q$:


Vs Bucket:

  • Bucket would put $V_1(v_1, y)$ to $\text{Bucket} \Big( U(y, z) \Big)$
  • because we have mapping $v \mapsto y, w \mapsto z \ \ (*)$
  • $(*)$ allows the match between atom $U(y, z)$ and atom $U(v, w)$ from the body of $V_1(v_1, y)$

But here we don't consider $U(v, w) \in V_1(v_1, y)$ in isolation

  • since $w$ there is existential and $w \mapsto z$
    • need to check that $(*)$ covers all query atoms ($\in Q$) that involve $z$
  • i.e. also need to check query atoms $R(x, {\color{blue}{z}})$ and $T({\color{blue}{z}}, y)$
  • it's the only way to enforce that all occurrences of $z$ are mapped to the same variable $w$

For this example ($U(y, z)$ vs $V_1(u, v)$)

  • can we map $R(x, z) \in Q \mapsto R(_, w) \in V_1$? (i.e. try to expand $(*)$)
  • no we can't: there doesn't exist such atom in $V_1$
  • so no MCD is created from $V_1$


Now try to match $U(y, z)$ with $V_2(u, v, v')$

  • we can match $U(y, z) \in Q$ to $U(v, w) \in V_2(u, v, v')$
  • mapping is $v \mapsto y, w \mapsto z \ \ (**)$
  • ${\color{blue}{z}}$ is existential, so check query atoms $R(x, {\color{blue}{z}})$ and $T({\color{blue}{z}}, y)$
    • $R(v', w) \mapsto R(x, {\color{blue}{z}})$ by adding $v' \mapsto x$
    • $T(w, u) \mapsto T({\color{blue}{z}}, y)$ by adding $u \mapsto y$
  • so an MCD is created for $V_2(u, v, v')$
  • $\text{MCD}_1 = \Big( V_2(u, v, v'), \{1,2,3\} \Big)$
    • we also write the positions of the query atoms that this MCD covers ($\{1,2,3\}$)
  • since $\text{MCD}_1$ covers $\{1,2,3\}$, only atoms in $\{4\}$ remain uncovered, so need to cover them


Consider 4th query atom $R(y', x)$

  • for $V_1$ we match with atom $R(v, u)$
    • mapping $v \mapsto y', u \mapsto x$
    • $x$ is a distinguished variable in $Q$, and $u$ is a distinguished variable in $V_1$
    • existential variable $y'$ has only single occurrence, so we can add it
  • so we have the following MCD:
    • $\text{MCD}_2 = \Big( V_1(x, y'), \{ 4 \} \Big)$
  • for $R(v', w) \in V_2$ no MCD is created
    • mapping $v' \mapsto y', w \mapsto x$
    • but $w$ is existential in $V_2$, and $x$ is distinguished in $Q$
    • so no MCD


Step 2: Combining MCDs

Combining step

  • At this step we combine MCDs that cover mutually disjoint subsets of the atoms of query $Q$
    • (these subsets should together cover the entire $Q$)
  • this way we obtain rewritings of the query $Q$
  • the rewriting are guaranteed to be valid - so no checking

So, a rewriting for $Q(x)$ is

  • $R(x) \leftarrow V_2(y, y, x), V_1(x, y')$


See Also


Sources