# ML Wiki

## 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')$