http://mlwiki.org/index.php?title=Minicon_Algorithm&feed=atom&action=historyMinicon Algorithm - Revision history2024-03-29T10:31:50ZRevision history for this page on the wikiMediaWiki 1.25.3http://mlwiki.org/index.php?title=Minicon_Algorithm&diff=698&oldid=prevAlexey: /* Sources */2015-11-23T13:10:33Z<p><span dir="auto"><span class="autocomment">Sources</span></span></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 13:10, 23 November 2015</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L102" >Line 102:</td>
<td colspan="2" class="diff-lineno">Line 102:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>== Sources ==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>== Sources ==</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Web Data Management book <del class="diffchange diffchange-inline">[http://webdam.inria.fr/Jorge</del>]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* <ins class="diffchange diffchange-inline">[[</ins>Web Data Management <ins class="diffchange diffchange-inline">(</ins>book<ins class="diffchange diffchange-inline">)]</ins>]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Data Integration]]</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Data Integration]]</div></td></tr>
</table>Alexeyhttp://mlwiki.org/index.php?title=Minicon_Algorithm&diff=403&oldid=prevAlexey at 20:19, 4 May 20142014-05-04T20:19:53Z<p></p>
<p><b>New page</b></p><div>== Minicon Algorithm ==<br />
This is an approach for query rewriting used in [[LAV Mediation]]<br />
<br />
=== Overview ===<br />
An optimized version of the [[Bucket Algorithm (Data Integration)|Bucket Algorithm]]<br />
* avoids the last step: verification<br />
* idea: not to put atoms that will generate invalid rewritings <br />
* an atom can be useless if its binding of variables doesn't match the bindings of other occurrences of this variable<br />
** recall ([[Bucket Algorithm (Data Integration)#Validation Example]] - this is the reason why $r_1$ didn't validate)<br />
<br />
<br />
So, steps are<br />
* creating MCDs (corresponds to the Bucket creation step)<br />
* combining MCDs (the second step)<br />
* where MCDs are ''Minicon Descriptions'' - instead of buckets<br />
<br />
<br />
=== Example ===<br />
The algorithm will be explained by this example<br />
<br />
Consider this global query<br />
* $Q(x) \leftarrow U(y,z), R(x,z), T(z,y), R(y',x)$<br />
<br />
<br />
And two LAV mappings<br />
* $V_1(u,v) \subseteq T(w,u), U(v,w), R(v,u)$<br />
* $V_2(u,v,v') \subseteq T(w,u), U(v,w), R(v',w)$<br />
<br />
<br />
== Step 1: Creating MCDs ==<br />
In this step<br />
* for each atom $A_i$ of the query $Q$<br />
* for each LAV mapping $V_i$ <br />
* determine the relevance of $V_i$ w.r.t. rewriting $A_i$ <br />
<br />
<br />
=== Illustration of Step 1 ===<br />
Consider first atom $U(y, z)$ of $Q$:<br />
<br />
<br />
Vs [[Bucket Algorithm (Data Integration)|Bucket]]:<br />
* Bucket would put $V_1(v_1, y)$ to $\text{Bucket} \Big( U(y, z) \Big)$<br />
* because we have mapping $v \mapsto y, w \mapsto z \ \ (*)$<br />
* $(*)$ allows the match between atom $U(y, z)$ and atom $U(v, w)$ from the body of $V_1(v_1, y)$ <br />
<br />
But here we don't consider $U(v, w) \in V_1(v_1, y)$ in isolation<br />
* since $w$ there is existential and $w \mapsto z$<br />
** need to check that $(*)$ covers all <u>query</u> atoms ($\in Q$) that involve $z$<br />
* i.e. also need to check query atoms $R(x, {\color{blue}{z}})$ and $T({\color{blue}{z}}, y)$<br />
* it's the only way to enforce that all occurrences of $z$ are mapped to the same variable $w$<br />
<br />
For this example ($U(y, z)$ vs $V_1(u, v)$)<br />
* can we map $R(x, z) \in Q \mapsto R(_, w) \in V_1$? (i.e. try to expand $(*)$)<br />
* no we can't: there doesn't exist such atom in $V_1$<br />
* so no MCD is created from $V_1$<br />
<br />
<br />
Now try to match $U(y, z)$ with $V_2(u, v, v')$<br />
* we can match $U(y, z) \in Q$ to $U(v, w) \in V_2(u, v, v')$<br />
* mapping is $v \mapsto y, w \mapsto z \ \ (**)$<br />
* ${\color{blue}{z}}$ is existential, so check query atoms $R(x, {\color{blue}{z}})$ and $T({\color{blue}{z}}, y)$<br />
** $R(v', w) \mapsto R(x, {\color{blue}{z}})$ by adding $v' \mapsto x$<br />
** $T(w, u) \mapsto T({\color{blue}{z}}, y)$ by adding $u \mapsto y$<br />
* so an MCD is created for $V_2(u, v, v')$ <br />
* $\text{MCD}_1 = \Big( V_2(u, v, v'), \{1,2,3\} \Big)$<br />
** we also write the positions of the query atoms that this MCD covers ($\{1,2,3\}$) <br />
* since $\text{MCD}_1$ covers $\{1,2,3\}$, only atoms in $\{4\}$ remain uncovered, so need to cover them<br />
<br />
<br />
Consider 4th query atom $R(y', x)$<br />
* for $V_1$ we match with atom $R(v, u)$<br />
** mapping $v \mapsto y', u \mapsto x$<br />
** $x$ is a distinguished variable in $Q$, and $u$ is a distinguished variable in $V_1$ <br />
** existential variable $y'$ has only single occurrence, so we can add it<br />
* so we have the following MCD:<br />
** $\text{MCD}_2 = \Big( V_1(x, y'), \{ 4 \} \Big)$<br />
* for $R(v', w) \in V_2$ no MCD is created<br />
** mapping $v' \mapsto y', w \mapsto x$<br />
** but $w$ is existential in $V_2$, and $x$ is distinguished in $Q$<br />
** so no MCD<br />
<br />
<br />
<br />
== Step 2: Combining MCDs ==<br />
Combining step<br />
* At this step we combine MCDs that cover mutually disjoint subsets of the atoms of query $Q$<br />
** (these subsets should together cover the entire $Q$)<br />
* this way we obtain rewritings of the query $Q$ <br />
* the rewriting are guaranteed to be valid - so no checking <br />
<br />
So, a rewriting for $Q(x)$ is <br />
* $R(x) \leftarrow V_2(y, y, x), V_1(x, y')$<br />
<br />
<br />
== See Also ==<br />
* [[Data Integration]]<br />
* [[Mediator (Data Integration)]]<br />
* [[GAV Mediation]]<br />
* [[Bucket Algorithm (Data Integration)]]<br />
* [[Inverse-Rules Algorithm]]<br />
<br />
<br />
== Sources ==<br />
* Web Data Management book [http://webdam.inria.fr/Jorge]<br />
<br />
[[Category:Data Integration]]</div>Alexey